Anything in the review queue?

[Don]

dsimcha wrote:
> == Quote from Don (nospam at nospam.com)'s article
>> 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.
> 
> That's ok.  Rational was a very small side project for me.  I didn't have tons of
> time invested in it or anything (probably an order of magnitude less than
> std.parallelism).  I do think it's interesting to decouple the Rational
> representation from the underlying integer type.  Whether it's practical and
> warrants inclusion in Phobos is a different question.
> 
> As far as BinaryGCD, would that be efficiently implementable using only the public
> interface of BigInt?  If not, it might make sense to change the public interface
> of BigInt to make it implementable.  (Or it might not.  I have no idea what's
> involved here.  Please comment.)

ExtendedGCD should be a part of the BigInt internals. (The other missing 
low-level BigInt function is square root). These functions should take 
care of switching algorithms from the naive version to ones with better 
big-O performance but large overheads, when the length is long.
I had planned to implement it, but then got distracted by fixing 
compiler bugs. I've been distracted for a long time <g>.