Math Is Fun Forum

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

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.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

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..."

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

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-26 13:37:28)

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

soroban

Member

Registered: 2007-03-09

Posts: 452

Re: Calculating square roots

. . .

. . .

. .

. .

. . . . . .

. .

. . . . . .

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

. .

.

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

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.

integer

Member

Registered: 2008-02-21

Posts: 79

Re: 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
...

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

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

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.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

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-29 06:44:16)

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

integer

Member

Registered: 2008-02-21

Posts: 79

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).

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

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-29 08:50:45)

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.