Re: Fun with Unbounded Rational Numbers

[Robert Eachus <rieachus@comcast.net>]

On Saturday, April 8, 2017 at 6:37:48 AM UTC-4, 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.

Sigh! You are running through a minefield.  Slowing to a walk will keep you alive a few minutes longer, but to survive you have to take each step very carefully.

First, you are trying to calculate an approximation to an irrational number.  The algorithm promises AT LEAST quadratic convergence which means that there will be at least twice as many bits/digits/words to store at each step.

But that is only half the story.  Your approximation will be a rational number. (Add, subtract, multiply, divide on rationals result in rationals.) The difference between your estimate and the actual irrational number is also an irrational number.  So when you test to a tolerance that subtraction should always raise Storage_Error.  But you did not say what you are using as an approximation of sqrt(2) for testing.  I suspect you are squaring your approximate value and testing that.  Sounds good, but...

For some reason you are using decimal limits.  These can not be represented accurately in binary, but using a rational package they will be represented by two numbers, with the divisor being a power of ten.  How do you compare two numbers stored as the ratio of integers? A/B ? C/D evaluate A*D ? B*C both integers, so now compare.  The rational arithmetic package will do those two multiplications, then throw the results away.  Unfortunately, the fragments left on the heap will be too small for any of the results in the next iteration.  This is probably what is running you out of memory.

You could try increasing the heap size.  Set your paging file to some large number, and try again with heap size set approximately to your main memory size.  You do not want to actually use that pagefile, set it to 3x you main memory size just to avoid system crashes.  On Windows, allowing the system to grow the pagefile, or putting it on C: are both bad news.  A cheap thumb drive will do nicely, and you don't have to worry about backing it up.

A much better idea is to throw away the limit, and have your program print the approximation at every step.  I don't know what you are looking for here, but a dozen iterations should give you all the accuracy you might need. (Even if you are measuring a diagonal brace for a house the size of the universe.)