dsimcha wrote:
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.
From the BigInt side, the only real change is the addition of gcd and
gcdExtended.
(gcdExtended returns x, y such that a*x + b*y = gcd(a, b) ).
I believe that is the only low-level algorithm which is missing; pretty
much everything else remains unchanged.
However, the other case which is interesting is when BigInt is replaced
with FixedInt!n (maybe someone can come up with a better name for this?)
-- an integer with a length of a fixed number of ints.
Unlike BigInt, this has basically the same semantics as built-in integer
types. In fact, FixedInt!1 == int, FixedInt!2 == long, FixedInt!4 == cent.
This is possibly even more relevant for Rational. I haven't thought much
about the implications though.
BTW, does BigInt over-allocate initially to allow certain operations
(like +=) to be done in-place more frequently?
No, it doesn't. As long as it uses copy-on-write, there's no benefit to
doing so.
Reference counting would clearly be superior for FixedInt, but I'm not
at all sure that it would be a win for BigInt. But of course FixedInt
wouldn't need to over-allocate.
Using TempAlloc would have a far greater effect on performance.
