Re: [boost] Interest in an arbitrary precision library?

From: Andras Erdei (aerdei_at_[hidden])
Date: 2005-09-14 03:11:34

On 9/11/05, Joel Eidsath <jeidsath_at_[hidden]> wrote:

> I don't even know why I need to say this. For one thing, just look the 
> GCD call at the creation of every boost::rational. You must understand 
> the costs involved there when numbers get big.

just for fun, let's first compare [built-in] floating point
and [boost::]rational:

creating a floating point number from a numerator and a 
denominator requires an O( log n ) division

creating a rational representation from a numerator and a
denominator requires an O( log n ) normalization

this means the speed difference is not theoretical, it is practical:

- the current boost::rational implementation is not using the
binary gcd algorithm, so the constant multiplier is fairly big

- for floats initialized with compile-time constants the calculation
is done at compile time -- this may be emulated for rationals
with some inconvenience for the user, using template trickery

- what remains is due to the fact that we are comapring a hw
and a sw implementation

so construction is not a good example, addition would be
much better -- there we do have different O() complexity

let's then compare arbirary-precision user-defined radix and
rational arithmetic in general:

what imho misleads you is that some operators (+,-) have
lower time complexity for radix representations, and the
rest (*,/,%) may have lower constant factors -- that is
true, but on the other hand (imo) in many application areas
you will get more accurate results using 64 bit rational
arithmetic than using 1024 bit radix arithmetic, so in
practice the latter can be faster

afaik we are not using floats because they are good and
fast (as a matter of fact, we know that they are bad), 
but for historical reasons; when they were introduced,
they were a natural next step after fixed point, we did
not yet know how bad they are, but we did know how to
implement them efficiently (in hw). since then, we are stuck
with them the same way as we are stuck with the QWERTY
keyboard: we know that there are better solutions (in
every sense of better), but the enormous amount of
existing implementations makes it impossible to change

when we implement and use our own arbitrary precision 
arithmetic, we make a compromise between speed and 
accuracy, and it is not as trivial as you seem to
think that radix representation is the best of those
compromises

br,
andras