On 9/11/05, Joel Eidsath <jeidsath@gmail.com> 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