square_root_good_rational_approximations.sf

#!/usr/bin/ruby

# Formula for computing good rational approximations to the square root of n.

func f (N) {

    var (m, R) = isqrtrem(N)

    var x = 0
    var y = 1

    (m, R, {
        (x,y) = (y, (2*m*y + R*x))
        (x,y)
    })
}

var (m, R, g) = f(42)        # approximations for sqrt(42)

for n in (1..20) {
    var (x,y) = g()
    var t = (m + R*(x/y))
    printf("%20s / %-20s =~ %s\n", t.nude, t.as_dec)
}

__END__
                  13 / 2                    =~ 6.5
                 162 / 25                   =~ 6.48
                 337 / 52                   =~ 6.48076923076923076923076923076923076923076923077
                4206 / 649                  =~ 6.4807395993836671802773497688751926040061633282
                8749 / 1350                 =~ 6.48074074074074074074074074074074074074074074074
              109194 / 16849                =~ 6.48074069677725681049320434447148198706154667933
              227137 / 35048                =~ 6.48074069847066879707829262725405158639580004565
             2834838 / 437425               =~ 6.48074069840544093273132537006343944676230210893
             5896813 / 909898               =~ 6.48074069840795341895465205990121969715286768407
            73596594 / 11356201             =~ 6.48074069840785664149480975195842341994475088984
           153090001 / 23622300             =~ 6.48074069840786036922738260033950970057953713229
          1910676606 / 294823801            =~ 6.48074069840786022564033084967926317454946590286
          3974443213 / 613269902            =~ 6.48074069840786023117110351846355570862500928669
         49603995162 / 7654062625           =~ 6.48074069840786023095806588073219481921863684777
        103182433537 / 15921395152          =~ 6.48074069840786023096627179296328540743952512133
       1287793197606 / 198710804449         =~ 6.48074069840786023096595571268629100309943559792
       2678768828749 / 413343004050         =~ 6.48074069840786023096596788765705492772086993787
      33433019142594 / 5158826853049        =~ 6.48074069840786023096596741869418729190366661501
      69544807113937 / 10730996710148       =~ 6.48074069840786023096596743675798189852951866938
     867970704509838 / 133930787374825      =~ 6.4807406984078602309659674360621897620745685787