Re: Fun with Unbounded Rational Numbers

[Paul Rubin <no.email@nospam.invalid>]

"Jeffrey R. Carter" <spam.jrcarter.not@spam.not.acm.org> writes:
> For example, trying to calculate sqrt(2)...
> taking a Long Time (it does conclude eventually).

Something seems wrong with that calculation or implementation.  I did
a simple Haskell version and it did 10 iterations (resulting in numbers
of around 750 digits) in almost no time:

    {-# LANGUAGE BangPatterns #-}
    import Data.Ratio
    type RI = Ratio Integer

    msqrt :: RI -> RI
    msqrt x = go (3/2) 10 where
      go g 0 = g
      go !g fuel =
        let y = g*g - x in
        go (g - y/(2*g)) (fuel-1)

    main = print . msqrt $ 2

("fuel" is the number of iterations).  With 5 iterations it gets the
more manageable ratio:

  1572584048032918633353217 % 1111984844349868137938112

which is approximately: x = 1.414213562373095
where |x*x - 2| is about 4.44e-16.

did you remember to recompute Y in your loop?  i.e.

         M := Two * X;
         Y = X * X - 2     -- <---- this might have been missing?
         X := X - Y / M;