
Boost : 
From: Andras Erdei (aerdei_at_[hidden])
Date: 20050914 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 [builtin] 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 compiletime 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 arbiraryprecision userdefined 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk