Thread: Square Root as a fraction?

All right this question has been bothering me, I sort of stumbled upon it myself and have tried it once before but with no success, it is the reason I signed up for this forum. I apologise if this question has been posted in the wrong section of this forum, it doesnt really have a place to go.

Example using numbers:

If you want the square root of 20 then you 'guess' the value as being 4 and the process to solve the square root is as follows.

(4+20/4)/2 = (36/4)/2 = 36/8 = 9/2 --> This is our first approximation.

Next we use the first approximation as our guess and continue with the same process:

(9/2 + 20 / (9/2) ) / 2 = (161/18)/2 = 161/36 ---> this is our second approximation.

Continuing with this pattern for infinite terms will yield exactly the sqare root of 20, our second approximation is already close:

161/36 = 4.472222222...
root20 = 4.4721359549996

If we generalise this process and call our starting 'guess' number as A and the number we are trying to square root as X then the n+1 term can be written in terms of the nth term.

T(n+1) = (T(n) + X/T(n)) / 2

My question is, and the question ive been trying to solve for a while now is how can I express the nth term relative to the first term? Is it even possible? I want something along the lines of:

T(n) = some formula involving T(1)

This is the Heron square root extraction method.

And your question is not possible, because it would mean it is possible to compute a arbitrarily precise square root in only one operation (take the greatest possible).

I'm sorry, it is impossible to express in function of in a simple and easy-to-compute manner.

You ain't cheatin' teh square roots

Originally Posted by Corpsecreate

All right this question has been bothering me, I sort of stumbled upon it myself and have tried it once before but with no success, it is the reason I signed up for this forum. I apologise if this question has been posted in the wrong section of this forum, it doesnt really have a place to go.

Example using numbers:

If you want the square root of 20 then you 'guess' the value as being 4 and the process to solve the square root is as follows.

(4+20/4)/2 = (36/4)/2 = 36/8 = 9/2 --> This is our first approximation.

Next we use the first approximation as our guess and continue with the same process:

(9/2 + 20 / (9/2) ) / 2 = (161/18)/2 = 161/36 ---> this is our second approximation.

Continuing with this pattern for infinite terms will yield exactly the sqare root of 20, our second approximation is already close:

161/36 = 4.472222222...
root20 = 4.4721359549996

If we generalise this process and call our starting 'guess' number as A and the number we are trying to square root as X then the n+1 term can be written in terms of the nth term.

T(n+1) = (T(n) + X/T(n)) / 2

My question is, and the question ive been trying to solve for a while now is how can I express the nth term relative to the first term? Is it even possible? I want something along the lines of:

T(n) = some formula involving T(1)

I'm not sure but I think it can't be done: just do evaluate in terms of and you'll get a rther nasty expression...and that's just with n = 3!

Tonio

No it can't be done because it would mean that the algorithmic complexity of computing any square root would be , which has (yet) been revealed impossible.

I'm not sure the situation is quite so clear cut as the other replies on this topic make out.
Suppose I want to calculate the square root of 2. Then there is a sequence of rational approximations S(n) that can be found using a sequence similar to the Fibonacci sequence, which begins 1/0,1/1,3/2,7/5,17/12,41/29.
If S(n) is a/b then S(n+1) is (2b+a)/(a+b).
I think this sequence essentially lists all the solutions in N of . Because the integers appearing as the numerators and denominators of this sequence can be written to form simple difference equations one can find a closed form expression for both integers appearing in the nth term in the sequence, and hence the ratio. However, that still does not really help you calculate the square root of 2, because the expression will surely involve , and in fact would constitute a proof that the sequence does converge to
My sequence is much less general than the one discussed by the original poster, but is related to lots of interesting number theory I think. There are certainly analogous sequences for other rational numbers: I guess one would use continued fractions to find them. My sequence also converges rather slowly to the square root of 2, though it has the nice property that adjacent terms bracket the root.
Nevertheless it is probably quite a good way of calculating root 2 to arbitrary precision, as one can continue as long as one likes using only integer addition, which is much easier and faster than multiplication. Then one just needs to do one long division to find a very good approximation to .