You are not logged in.
#1 2009-06-27 07:57:13
- mathsyperson
- Moderator
Offline
Calculating square roots
I came across this interesting method the other day, but I have no idea how it works. It does seem reliable though.
Here is a way of computing √(n)
Start with the double (5n,5), and put it iteratively through the following function:
(a,b) -> (a-b,b+10) , if a≥b
(100a,10b-45) , if a<b
So if n=2, then the sequence would start like this:
(10,5)
(5,15)
(500,105)
(395,115)
(280,125)
(155,135)
(20,145)
(2000,1405)
(595,1415)
(59500,14105)
...
The digits of b (excluding the final two) are the first digits of the square root you want.
Continuing this sequence lets you get arbitrarily many decimal places.
Why did the vector cross the road?
It wanted to be normal.
#2 2009-06-27 10:01:34
- Ricky
- Moderator
Offline
Re: Calculating square roots
Figuring out why a method works is interesting, just remember that nothing works as fast as Newton's method. (Actually I'm using Newton's method right now to calculate the initial conditions for a pde that models heat/gas mixture in an engine)
"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."
#3 2009-06-27 11:06:38
- bobbym
- Administrator
Online
Re: Calculating square roots
Hi,
The oddity of that method is that the digits appear in b as an integer.
Last edited by bobbym (2009-06-27 11:37:28)
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#4 2009-06-29 11:06:31
- soroban
- Power Member
Offline
Re: Calculating square roots
. . .
. . .
. .
. .
. . . . . .
. .
. . . . . .
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
. .
.
#5 2009-06-29 20:48:08
- mathsyperson
- Moderator
Offline
Re: Calculating square roots
This is a specific case of Newton's method, which takes an approximation a and puts it through
a -> a - f(x)/f'(x).
, where f(x) is a function that you are trying to find a root of. Here, f(x) = x² - N, and so the iterative map is
a -> a - (a² - N)/2a.
Manipulating the RHS gets the same expression as above.
One of the reasons I like the method I posted is that it doesn't need any division.
If you wanted to use Newton's method to find something to 1000 decimal places, then eventually you would have to be dividing one ~900 digit number by another, which as far as I know is computationally taxing.
The method above only uses addition and subtraction, so calculating the nth decimal place (given all the previous ones) will only take O(n) time.
Why did the vector cross the road?
It wanted to be normal.
#6 2009-06-29 23:23:55
- integer
- Full Member
Offline
Re: Calculating square roots
mathsyperson wrote:
I came across this interesting method the other day, but I have no idea how it works. It does seem reliable though.
Here is a way of computing √(n)
Start with the double (5n,5), and put it iteratively through the following function:
(a,b) -> (a-b,b+10) , if a≥b
(100a,10b-45) , if a<b
...
mathsyperson could you furnish the reference where you found this method.
It looks like a modified version of the method that used to be taught
in middle school, the paper & pencil square root routine which is based on:
(guess + small error)
The intermediate values are iterated with this
(2x(base)+e)e
if you are in base 10 (the decimal system) then
with x representing all of the previous digits (estimates)
The series of e's are the sucessive digits of the
square root of the number, until you reach the desired
tolerance wanted. For each iteration e will produce a digit
of the square root of n.
If in base 10 the first digit or initial x is
#7 2009-06-30 03:20:44
- mathsyperson
- Moderator
Offline
Re: Calculating square roots
I was just shown that method by a friend who thought it was cool.
I managed to find this though, which is probably more the kind of thing you want.
Why did the vector cross the road?
It wanted to be normal.
#8 2009-06-30 03:43:39
- bobbym
- Administrator
Online
Re: Calculating square roots
Hi Integer;
Also as per the techniques of error analysis you can drop the e^2 because it is essentially 0. Now if you solve for e you will get a form of newtons.
Last edited by bobbym (2009-06-30 04:44:16)
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#9 2009-06-30 06:23:30
- integer
- Full Member
Offline
Re: Calculating square roots
Thanks, mathsyperson
Frazer Jarvis's paper explains it.
bobbym
The pencil & paper method produces 1 digit per iteration,
whereas the newton method is quadratic and the more itereations
the more correct digits you get per each.
However,
without a calculator the pen/paper method is quicker (at least for me).
#10 2009-06-30 06:35:57
- bobbym
- Administrator
Online
Re: Calculating square roots
Hi integer;
What I am saying is that your form can also get newtons:
Now drop the e^2 because it is much smaller than the e. You are left with
Solve for e
This has quadratic convergence and as mathsyperson explains above is a variant of newtons. Actually your whole method starting with
is the error analysis way to derive newtons iteration.
Last edited by bobbym (2009-06-30 06:50:45)
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.