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

From: Andras Erdei (aerdei_at_[hidden])
Date: 2005-09-15 03:01:33

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

> Given n bits one can only represent 2^n numbers at most. (In 
> the case of boost::rational, substantially less, since 1/2 = 4/8 and so 
> on.) 

substantially less is not as bad as one might think, the 
loss is about 1 bit, depending on n (but always less than two bits)

> That simply translates to a set of points on the number line. If 
> one were to choose a random real number, which would be less on average: 
> its distance to the nearest boost:rational representation or its 
> distance to the nearest n-bit floating point representation? Since the 
> n-bit floats are equally spaced

[i think fixed point and fixed slash are (asimptotically) 
uniformly distributed, and floating point and floating slash 
are (asimptotically) log uniformly distributed]

> and all representations are unique, the 
> answer is that with n-bits, you can get closer to an arbitrary real 
> number with a floating point representation than with boost::rational.

the distribution of numbers representable with num/den
pairs is arithmetic friendly, and of those representable
as floating point is arithmetic unfriendly, but the 
explanation is very long and math intensive, so i am 
cornered

the best i can offer here is an autoritarian "proof" of
one particular difference; you were referring to knuth, 
so let's quote him:

"For example, suppose we are doing [fixed precision rational
arithmetic] so that the representable numbers (u/u') have -128
< u < 128 and 0 <= u' < 255. This isn't much precision,
but it is enough to give us a feel [] Suppose we have a
calculation that would take the overall form 22/7 = 314/159 + 1300
/ 1113 if we were working in exact rational arithmetic, but the
intermediate quantities have had to be rounded to representable
numbers. In this case 314/159 would round to (79/40) and 1300/1113
would round to (7/6). The rounded terms sum to 79/40 + 7/6 =
377/120, which rounds to (22/7); so we have obtained the correct
answer even though three roundings were required. This example was
not specially contrived. When the answer to a problem is a simple
fraction [fixed precision rational arithmetic] tends to make the
intermediate rounding errors cancel out."

D.E. Knuth: The Art of Computer Programming, Volume 2, Chapter 4.5.1

(in contrast, floating point tends to accumulate rounding errors)

> Getting to the issue of CPU cycles. Your previous email has several 
> problems. For one thing, arbitrary floating points are not constructed 
> with a numerator and denominator. You can construct them with a string 
> of digits, for example. 

[to my understanding you were referring to the boost::rational
ctor that takes a num and a den, so i compared that kind of
initialisation, but]

in theory, if a float or a rational is constructed using a
num and a den, both takes O( log n ) steps; if they are
constructed using a string of digits, still both takes
O( log n ) steps; if the float is constructed using a
precalculated float representation and a rational using a
precalculated normalized num and den, both takes O( 1 )

the practical difference is that for built-in floats you
have compiler and hw support, and it happens in compile-time, 
and for user-defined rationals you do no not, and it happens 
at run-time, in sw

to an extent, the compiler support can be emulated; but
we are unlikely to ever have hw support for rationals
(there are several articles about efficient hw implementation
of rationals, but i don't know about any PCs shipped
with such hw :O)

> Further, you neglect the fact that gcd calls 
> have to be made after every arithmetical operation, not simply on 
> construction. This represents a huge effciency hit, not a small 
> effciency hit. 

that's why i said you should have compared addition, not
construction, as that is the operation that really have
different time complexity (and also reciprocate, in the
opposite direction)

but there are other considerations: users may be happier 
with getting the correct result slightly slower than getting 
a bad answer a bit faster

> Lastly, you didn't compare worst cases.

?

> 1) It takes more memory on average.

or less

> 2) It's not just a little slower, it's far slower,

addition is the only operation with worse time-complexity
(i assume "far slower" means that), and i think it is up
to the user whether he can live with that compromise

> and worst case quickly gets uncomputable.

?

> 3) And most importantly: It's nearly useless for science and 
> engineering because you cannot use infinite series functions like sin, 
> sqrt, and so on. (You can hack it with series approximations, but you 
> wind up redoing all the work of an arbitrary float class.)

swap the words float and rational and the above sentence still stands :O)

> It is quite true that there is a problem space where boost::rational is 
> the most appropriate solution. It's just not as big as you seem to 
> think it is.

that could be right

br,
andras