Re: Fun with Unbounded Rational Numbers

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On 2017-04-08 12:37, Jeffrey R. Carter 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.

To use unbounded rational numbers should have the purpose of having 
exact computations <=> both absolutely accurate and absolutely precise. 
Otherwise, if accuracy is not absolute, you are allowed to choose from a 
set of rational numbers within the accuracy interval. Doing so you can 
take one with a less demanding representation, i.e. you are fiddling 
with the precision. And conversely for any algorithm involving 
irrational numbers you can always find an approximation requiring 
however much memory to waste.

In short unbounded rational numbers is *always* bad idea unless proven 
otherwise.

For transferring algorithms from real to unbounded rational numbers one 
could consider rounding the results within the accuracy constraint to 
some simpler (shorter) number. OK, this is what the floating-point 
arithmetic does already, right? (:-))

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de