1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556 |
- #!/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
|