sidef-scripts/Math/sqrt_convergents.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 28 March 2018
# https://github.com/trizen

# Efficient algorithm for finding the square root convergents for a given non-square integer.

func sqrt_convergents (n, callback, count=10) {

    var x = n.isqrt
    var y = x
    var z = 1

    var r = x+x

    var (e1, e2) = (1, 0)
    var (f1, f2) = (0, 1)

    count.times {

        y = (r*z - y)
        z = ((n - y*y) / z)
        r = ((x + y)  // z)                  #/

        callback(e2 + x*f2, f2)

        (f1, f2) = (f2, r*f2 + f1)
        (e1, e2) = (e2, r*e2 + e1)
    }
}

sqrt_convergents(23, {|n,d| printf("%20s / %-20s =~ %s\n", n, d, n/d) }, 20)

__END__
                   4 / 1                    =~ 4
                   5 / 1                    =~ 5
                  19 / 4                    =~ 4.75
                  24 / 5                    =~ 4.8
                 211 / 44                   =~ 4.79545454545454545454545454545454545454545454545
                 235 / 49                   =~ 4.79591836734693877551020408163265306122448979592
                 916 / 191                  =~ 4.79581151832460732984293193717277486910994764398
                1151 / 240                  =~ 4.79583333333333333333333333333333333333333333333
               10124 / 2111                 =~ 4.79583135954523922311700615821885362387494078636
               11275 / 2351                 =~ 4.79583156103785623139089749042960442364951084645
               43949 / 9164                 =~ 4.79583151462243561763422086425141859450021824531
               55224 / 11515                =~ 4.79583152409900130264871906209292227529309596179
              485741 / 101284               =~ 4.79583152324157813672445795979621657912404723352
              540965 / 112799               =~ 4.79583152332910752754900309399906027535705103769
             2108636 / 439681               =~ 4.79583152330894443926392088809841680673033403763
             2649601 / 552480               =~ 4.79583152331306110628439038517231392991601505937
            23305444 / 4859521              =~ 4.79583152331268863741920242756436282506033002018
            25955045 / 5412001              =~ 4.79583152331272666061961185890394329195430673424
           101170579 / 21095524             =~ 4.79583152331271790167430778206789269609989303892
           127125624 / 26507525             =~ 4.7958315233127196899748279026427401275675492148