Brain Teasers
Square Root of 2
An iterative equation is one where an initial value is put into the equation to obtain a result, which is in turn put back into the equation as an input and the process is repeated for either a fixed number of times or until a final value is achieved (where you get the same number out as you put in).
For example, if you start with the iterative equation,
A{n+1} = 1/A{n} + 1
And you put in an initial value of 1, you would get 2 as the result. Put the 2 back in as the input and you would get 1.5, and so on.
There is a simple iterative equation which, when repeated just five times, will give you a very good approximation of the square root of two (accurate to three decimal places, or less than 0.1%). What's more, you can put in any positive (and almost any negative) initial value into the equation (even zero) and you will end up at the same answer. This equation does not contain any square root expressions; just single-order algebra. Can you figure it out?
For example, if you start with the iterative equation,
A{n+1} = 1/A{n} + 1
And you put in an initial value of 1, you would get 2 as the result. Put the 2 back in as the input and you would get 1.5, and so on.
There is a simple iterative equation which, when repeated just five times, will give you a very good approximation of the square root of two (accurate to three decimal places, or less than 0.1%). What's more, you can put in any positive (and almost any negative) initial value into the equation (even zero) and you will end up at the same answer. This equation does not contain any square root expressions; just single-order algebra. Can you figure it out?
Show Hint Show Answer
What Next?
View a Similar Brain Teaser...
If you become a registered user you can vote on this brain teaser, keep track of which ones you have seen, and even make your own.
Solve a Puzzle
Comments
huh?! what in the heck do u mean? i am only in sixth grade!!!!!!!!!
How about A{n+1}=1/(A{n}+1) +1
nice try tommo... BUT those are actually equivalent expressions. substituting 'x' for'A{n}' you get: 1/(x+1)+1 = 1/(x+1) + (x+1)/(x+1) = [1+(x+1)]/(x+1) = (x+1)/(x+1)!!!
oops, that last one should read (x+2)/(x+1)
I'm in the 10th grade and I still don't know what you mean...
There is quicker method, which works for the square root of any number, and which third-graders understand, after they are told that the a number is equal to its square root multiplied by itself (for example the square root of 9 is 3 because 3x3=9) -------
Take half of the number N of which you want to find the square root. Divide that by your guess (a). Add half your guess. What you get is your next guess (b) and you do the same thing with it. -----
The formula is b = (N/2a) + a/2 -----
then your next approximation is c = (N/2b) + b/2 -----
you keep doing this, to get d, e, and so on as far as you care to go.
Take half of the number N of which you want to find the square root. Divide that by your guess (a). Add half your guess. What you get is your next guess (b) and you do the same thing with it. -----
The formula is b = (N/2a) + a/2 -----
then your next approximation is c = (N/2b) + b/2 -----
you keep doing this, to get d, e, and so on as far as you care to go.
Apply the quick method to the teaser. N is 2. So each approximation a will be followed by the much closer approximation b = 1/a + a/2. -----
Since 1x1=1 and 2x2=4, the square root of 2 must be between 1 and 2. Let's take 1.5 as our first guess. Use a calculator to find: -----
1/1.5 = 0.66666 -----
1.5/2 = 0.75 -----
add them, you get 1.416666 -----
The square of that is 2.0069444 -----
If that is not close enough for you, go on to step 2: -----
1/1.416666 + 1.416666/2 = 1.414215686 -----
The square of that is 2.000006 which is probably more accurate than you need. But if not, you can keep going.
Since 1x1=1 and 2x2=4, the square root of 2 must be between 1 and 2. Let's take 1.5 as our first guess. Use a calculator to find: -----
1/1.5 = 0.66666 -----
1.5/2 = 0.75 -----
add them, you get 1.416666 -----
The square of that is 2.0069444 -----
If that is not close enough for you, go on to step 2: -----
1/1.416666 + 1.416666/2 = 1.414215686 -----
The square of that is 2.000006 which is probably more accurate than you need. But if not, you can keep going.
Compare with the method given in the answer to the teaser. Start with the same 1.5 as a first guess. -----
The next approximation is 3.5/2.5 = 1.4 of which the square is 1.96, almost 6 times less accurate than by the quick method. -----
Then 3.4/2.4 = 1.4166666, finding in two steps what the quick method found in one. And the square of that is 2.0069444, which is 1156 times less accurate than the 2nd step of the quick method.
The next approximation is 3.5/2.5 = 1.4 of which the square is 1.96, almost 6 times less accurate than by the quick method. -----
Then 3.4/2.4 = 1.4166666, finding in two steps what the quick method found in one. And the square of that is 2.0069444, which is 1156 times less accurate than the 2nd step of the quick method.
Wow, too hard for me 
When I see these sorts of teasers, my brain just sort of zones off...
When I see these sorts of teasers, my brain just sort of zones off... 
At first this looked like it was going to be difficult, but it turned out to be quite simple--in fact the first function I tried was correct!
This was in part because the only approach I could think of to reduce the magnitude of any value quickly was to construct a fraction x/y where x was a little bigger than y.
I've seen canu's approach before for quick approximation, but the interesting thing about the solution for this teaser was that any value can be plugged in and still quickly zero in. Canu's approach won't do so well if a wildly inaccurate first guess is fed to it.
Nice teaser!
BTW, here's one to stick in your bag or tricks:
A quick approximation of 2^(1/5n) (the 5nth root of 2) that's fairly accurate is (n*7+1)/(n*7). For 10th roots of 2 and higher the error is less than 1%.
This was in part because the only approach I could think of to reduce the magnitude of any value quickly was to construct a fraction x/y where x was a little bigger than y.
I've seen canu's approach before for quick approximation, but the interesting thing about the solution for this teaser was that any value can be plugged in and still quickly zero in. Canu's approach won't do so well if a wildly inaccurate first guess is fed to it.
Nice teaser!
BTW, here's one to stick in your bag or tricks:
A quick approximation of 2^(1/5n) (the 5nth root of 2) that's fairly accurate is (n*7+1)/(n*7). For 10th roots of 2 and higher the error is less than 1%.
Newton's Method for approximation of roots tells us that x(n+1) = x(n) - F(x)/F'(x).
To solve for x^2 = 2 construct the function F(x) = x^2 - 2 = 0. Then F'(x) = 2x.
Thus for this case:
x(n+1) = x(n) - [x(n)^2 - 2]/2*x(n).
This will converge for any (positive) value of x(n) initially although the closer to root 2 , the quicker it will get there.
Example: take initially x(1) = 4 x(2) = 4 - 14/8 = 9/4
x(3) = 9/4 - [81/16 - 2]/9/2 = 1.569 after only 2 iterations.
To solve for x^2 = 2 construct the function F(x) = x^2 - 2 = 0. Then F'(x) = 2x.
Thus for this case:
x(n+1) = x(n) - [x(n)^2 - 2]/2*x(n).
This will converge for any (positive) value of x(n) initially although the closer to root 2 , the quicker it will get there.
Example: take initially x(1) = 4 x(2) = 4 - 14/8 = 9/4
x(3) = 9/4 - [81/16 - 2]/9/2 = 1.569 after only 2 iterations.
Follow Braingle!