Anything in the review queue?

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Mon Mar 21 17:33:10 PDT 2011


On 3/21/11 12:18 PM, dsimcha wrote:
> == Quote from Don (nospam at nospam.com)'s article
>>> Ok, I don't know much about how BigInts work under the hood.  I used a
>>> fairly simple implementation of Euler's algorithm here.  Is there
>>> something much more efficient for BigInts?
>> Yes. Euler's algorithm performs very poorly for BigInts. In fact, you
>> probably want to use the BinaryGCD algorithm even for builtins.
>> There is a sub-quadratic algorithm for GCD, but it's very complicated.
>> (It's not the one Kenny posted).
>>>> I guess the primary question is:
>>>> If there were a BigRational type, would you still want rational?
>>>> Ie, are there use cases for rational over built-in types (rather than it
>>>> just being a workaround for a lack of a BigRational type)?
>>>
>>> My thoughts were that Rational would be **primarily** used with BigInt,
>>> but occasionally, if you really know what you're doing with regard to
>>> overflow, you could used fixed width as an optimization.
>> This isn't sounding so promising.
>> I hate to be saying that.
>
> I've thought about this some more.  The following **may** be a good way to
> proceed.  I'd like Don's input, since I don't know in detail what he was planning.
>
> 1.  Review the design of my rational lib with a focus on whether sufficient
> infrastructure for creating specializations without introducing breaking changes
> is available.
>
> 2.  If no issues not related to the lack of specialization for BigInt are raised,
> accept Rational into Phobos for now.
>
> 3.  At his leisure, Don can write a specialization of Rational specifically for
> BigInt (or even just a specialization of gcd, if that's all that's needed).  Once
> this is done, we include it as an optimization, but without changes to the
> interface.  Every integer type except BigInt still uses the generic implementation.
>
> 4.  Maybe we provide hooks for specializing certain performance-critical things
> like GCD, in case someone wants to use their own custom BigInt type with Rational
> without having to modify the code for Phobos.  For example, a BigInt type might
> optionally define a gcd() method.  Rational would look for this and use it if it
> exists, or use the generic fallback algorithm otherwise.

I think by and large failure to define rational for BigInt in a way that 
has many commonalities with rational for built-in integrals reflects a 
failure of BigInt. By its very design, BigInt is supposed to 
transparently replace integers. If this is largely the case, the design 
has succeeded. If the design of anything must be reworked essentially 
from scratch to work with BigInt instead of int et al, then the 
abstraction may be too porous to be useful.

There are a few approaches we can take from here. One is to define 
certain traits that differentiate BigInt from other integrals (e.g. 
preferAdditionToMultiplication or whatnot), and then design Rational to 
use those traits. Another is of course to specialize the entire Rational 
on BigInt. Third would be to specialize certain core routines (gcd and 
friends) for BigInt and keep Rational agnostic.

Anyhow, BigInt should be cheap to copy (i.e. use refcounting). If there 
are good reasons for which that's impossible, we should give up on the 
dream of enacting that assumption throughout Phobos. Don?


Andrei


More information about the Digitalmars-d mailing list