mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2008-03-06, 22:18   #1
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

447310 Posts
Default "ODD" Square root Algorithm

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

http://pullmoll.stop1984.com/sqrt.html
petrw1 is online now   Reply With Quote
Old 2008-03-08, 20:45   #2
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24×33 Posts
Default

Quote:
Originally Posted by petrw1 View Post
Odd to me anyway ... some of you may be familiar with it or why it works.

http://pullmoll.stop1984.com/sqrt.html
Did you read at the end of the page:
Quote:
More information

After asking on the usenet group sci.math.num-analysis 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 reference 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 hints?
m_f_h is offline   Reply With Quote
Old 2008-03-08, 22:49   #3
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

32×7×71 Posts
Default

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
petrw1 is online now   Reply With Quote
Old 2008-03-15, 07:35   #4
nibble4bits
 
nibble4bits's Avatar
 
Nov 2005

18210 Posts
Default

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.
The optimizes trivially without multiplication to:
Code:
Let x=0
For i = 1 to n
x = x + i + i
Next i
x = x - n
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
Or:
Code:
Let x = n^2 + n - n
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)

Last fiddled with by nibble4bits on 2008-03-15 at 07:44 Reason: Added note
nibble4bits is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!" wildrabbitt Miscellaneous Math 11 2015-03-06 08:17
Primo quit with "Candidate is presumably a square" lavalamp Software 12 2011-06-09 19:27
Fastest possible algorithm to calculate the square root of a 10,000,000 digit number Fusion_power Math 19 2007-11-02 21:37
Would Minimizing "iterations between results file" may reveal "is not prime" earlier? nitai1999 Software 7 2004-08-26 18:12

All times are UTC. The time now is 02:29.

Sat Dec 5 02:29:58 UTC 2020 up 1 day, 22:41, 0 users, load averages: 1.89, 1.59, 1.49

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.