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.
