Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: √ ∞ ≠ ≤ ≥ ≈ ⇒ ∈ Δ θ ∴ ∑ ∫ π -

Login

Username

Password

Not registered yet?

#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

Offline

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.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
 

#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

Offline

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.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
 

#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

Offline

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.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
 

Board footer

Powered by FluxBB