Algorithm for making fraction of root?
The algorithm to calculate the square root of a number a
r(n+1) = (r(n) + a/r(n))/2 can be developed to manage fractions:
p(n+1)/q(n+1) = (p(n)/q(n) + a*q(n)/p(n))/2 =>
p(n+1)/q(n+1) = (p(n)^2 + a*q(n)^2) / (2*p(n)*q(n)) =>
p(n+1) = p(n)^2 + a*q(n)^2
q(n+1) = 2*p(n)*q(n)
From that we can get the root of two as a fraction (it seems you should always start with 1:1):
and so on
That fraction development is actually the same as that you get when you use continued fraction, and that method creates as accurate fractions as possible for the size of them (I guess?)
However, that is not the case for square roots of other numbers, for example if we are going to calculate the square root of 3 that way:
4:2 (already here 2 becomes a comon divisor)
28:16 (Here the gcd is 4)
1552:896 (Here it is 16!)
As you see, gcd is groving fast!
Is there any other way to get rid of the gcd than calculating it and dividing by it?