On 3/22/2011 1:25 AM, Don wrote:
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.
You're missing something important here. Rational big integers are a
very well defined area of research, with its own set of algorithms.
Although you can pretend a BigInt behaves as an int, and make a rational
type, the performance will be pathetic, and everyone will laugh at you.
I fully understand this based on your previous posts. I therefore agree
that Rational doesn't belong in Phobos exactly as-is. I'm trying to
understand which of the following scenarios is true, though:
Scenario A: Making BigInt efficient would require changes only in a few
small places, like GCD. If we provide hooks for arbitrary precision
types to specialize these, and provide specializations for
std.bigint.BigInt, all will be well.
Scenario B: Making BigInt efficient would have ripple effects all over
the implementation, require rethinking of every operation, etc., but in
a way that wouldn't bleed out into the interface. It might make sense
to get the interface and a generic implementation right first, then
specialize it to improve performance later.
Scenario C: Making BigInt efficient would have ripple effects for both
the interface and the implementation. In this case, we probably
shouldn't provide a generic implementation because the arbitrary
precision one is much more generally useful and the fixed width one
would mostly add clutter.
BTW, does BigInt over-allocate initially to allow certain operations
(like +=) to be done in-place more frequently?
