Anything in the review queue?

[Don]

dsimcha wrote:
> On 3/21/2011 3:59 AM, Don wrote:
>> The original plan for BigInt was to have a BigRational type. Suppose
>> that such a thing existed -- would it affect plans for this library?
>>
>> I'm not sure that it is realistic to have a single templated type that
>> does both BigInt rationals, together with rationals based on built-in
>> integral types. The algorithms are different in a few respects:
>> (1) copying built-ins is practically zero cost;
> 
> Doesn't BigInt use COW rather than eager copying?

Yes, but it operations which create temporaries are still expensive.

> 
>> (2) operations on BigInts depend on the size of the number (whereas for
>> builtins, all operations are O(1));
> 
> I don't understand how this is relevant.

With a built-in type, multiplication and addition are equally cheap - eg 
on x86, multiply is only about half as slow as an addition.
For BigInt, addition is O(N) while multiplication is O(N^^2) decreasing 
to say O(N^^1.5) for large numbers. This means that you really want to 
avoid multiplication with BigInts. Interestingly, division of builtins 
is really slow (~20 * multiply), but division of a BigInt is only a few 
times slower than a multiply.

> 
>> (3) BigInts cannot overflow.
>> In particular, gcd algorithms for arbitrary precision types are quite
>> different to gcd for built-ins.
> 
> 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.