mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   "ODD" Square root Algorithm (https://www.mersenneforum.org/showthread.php?t=10061)

 petrw1 2008-03-06 22:18

"ODD" Square root Algorithm

Odd to me anyway ... some of you may be familiar with it or why it works.

[url]http://pullmoll.stop1984.com/sqrt.html[/url]

 m_f_h 2008-03-08 20:45

[quote=petrw1;127976]Odd to me anyway ... some of you may be familiar with it or why it works.

[URL]http://pullmoll.stop1984.com/sqrt.html[/URL][/quote]
Did you read at the end of the page:

After asking on the usenet group [B]sci.math.num-analysis[/B] I was pointed in the right direction and was told, that the algorithm was known and used in mechanical calculators ("Friede desk calculator") in the early 60s at Boeing already. Later Hewlett Packard sold calculators such as the HP9100, which used a similiar or identical algorithm utilizing BCD (binary coded decimals).
I found this [URL="http://www.ulib.org/webRoot/Books/Saving_Bell_Books/SBN%20Computer%20Strucutres/csp0815.htm"]reference[/URL] to the inner workings of the HP Model 9100A and the mathematical background for the algorithm. The background is that:
n
Σ 2*i - 1 = n2
i=1
so it says that the sum of all 2*i-1 for i starting with 1 up to n is equal to the square of n. I would be interested to learn how to write the corresponding formula for the cubic numbers, any [EMAIL="pullmoll@t-online.de"]hints[/EMAIL]?
[/QUOTE]

 petrw1 2008-03-08 22:49

Yes I did in fact read that but didn't take enough time to absorb how that extends to the algorithm he describes.

For example to calculate sqrt(1024) only requires adding 1+3+5 and later 61+63, rather than all odds from 1 to 63.

(1+3+5) * 100 = 900 = sum of odds to 60. Cool...

As I continue to investigate it starts to make sense .... so let me at it for a while and I'll be fine.

Thanks

 nibble4bits 2008-03-15 07:35

Do I understand right? That this is based on this formula for quadratics:
(n+1)^2=n^2+2n+1; let m=n+1
m^2-n^2-1=2n
Thus consecutive squares are always 2n+1 appart.

That formule you mentioned is equivilent to this code:
[code]
Let x = 0
For i = 1 to n
x = x + i + i - 1
Next i
REM Returns in x, the square of n using recursive addition instead of multiplication.
[/code]

The optimizes trivially without multiplication to:
[code]
Let x=0
For i = 1 to n
x = x + i + i
Next i
x = x - n
[/code]

You can further remove the For...Next loop using an identity but you get this:
Let x = 2 * n * (n + 1) / 2 - n
Or:
[code]
Let x = n * (n + 1) - n
[/code]
Or:
[code]
Let x = n^2 + n - n
[/code]

As you can see, this leads you back to your original equation of x=n^2.

EDIT:
You should note that for m=n+1:
m^3 - n^3 - 1 =
(n+1)^3 - n^3 - 1 =
n^3 + 3n^2 + 3n + 1 - n^3 - 1 =
3(n^2 + n) =
3n(n+1)

 All times are UTC. The time now is 16:19.