== Quote from Don (nos...@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.)
