Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**mathsyperson****Moderator**- Registered: 2005-06-22
- Posts: 4,900

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.

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

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

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 108,666

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

Offline

**soroban****Member**- Registered: 2007-03-09
- Posts: 452

. . .

. . .

. .

. .

. . . . . .

. .

. . . . . .

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

. .

.

Offline

**mathsyperson****Moderator**- Registered: 2005-06-22
- Posts: 4,900

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.

Offline

**integer****Member**- Registered: 2008-02-21
- Posts: 79

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

Offline

**mathsyperson****Moderator**- Registered: 2005-06-22
- Posts: 4,900

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.

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 108,666

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

Offline

**integer****Member**- Registered: 2008-02-21
- Posts: 79

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

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 108,666

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

Offline

Pages: **1**