Re: Fun with Unbounded Rational Numbers

[antispam@math.uni.wroc.pl]

Jeffrey R. Carter <spam.jrcarter.not@spam.not.acm.org> wrote:
> I decided to see what happens when you calculate square roots using Newton's 
> method and the unbounded rational numbers in PragmARC.Rational_Numbers. Some 
> interesting things happen.
> 
> For example, trying to calculate sqrt(2) to a small enough accuracy (0.000001 
> will do it) results in the calculation of the next estimate
> 
>          M := Two * X;
>          X := X - Y / M;
> 
> taking a Long Time (it does conclude eventually).
> 
> More alarming, though, is that for some values, even a fairly large accuracy 
> will quickly result in Storage_Error. For example, sqrt(1.28) to an accuracy of 
> 0.01 will do it.
> 
> I realize that square roots are often irrational, but the accuracies seem so 
> large that I didn't anticipate consuming GB of memory. Just naive, I guess.

There is somthing wrong with your code (or less likely with
PragmARC.Rational_Numbers).  Using computer algebra system
FriCAS and the following naive code:

newton(y : Fraction(Integer), eps : Fraction(Integer)) : Fraction(Integer) ==
    x : Fraction(Integer) := 1
    while abs(y - x^2) >= eps repeat
        x := (x + y/x)/2
    x

I can compute newton(2, 1/10^10000) with almost no time.  More
precisely time for actual computation is of order of timing resolution,
that is 10ms, while time needed to print result (that is binary to
decimal convertion) is of order 20ms.  The result has 12544 characters.

FriCAS after each rational operation cancels common factors between
numerator and denominator, this limits growth of numbers and is crucial
for bigger calculations.  But even without canceling common factors
your computation should work.  Namely size of numbers after
each operation is approximately sum of sizes of arguments.  Since
y above does not change size of y/x is bounded by size of x plus
a constant.  So in iteration n + 1 size of x is bounded by two
times size of x in iteration n plus a constant.  Each iteration
of Newton iteration approximately doubles accuracy.  The total
effect is that size of final result is proportional to accuracy,
and low accuracy (relatively large eps) result should be small.

-- 
                              Waldek Hebisch