Hello everyone. I'm looking for the different ways known to calculate the square root of real positive numbers by using integer addition operations only. I'm thinking of their application to microprocessor subroutines, which work on integer numbers only. Any ideas?
On Tue, 27 Apr 2004 23:40:54 -0400, Don wrote: > Hello everyone. I'm looking for the different ways known to calculate > the square root of real positive numbers by using integer addition > operations only. I'm thinking of their application to microprocessor > subroutines, which work on integer numbers only. > Any ideas?
2's complement or 1's complement integer rep? Is negation of positive quantities allowed (if so, you can form the complement and add to emulate subtraction)? What's the real number representation, or are you assuming a rational approximation?
In any case, you might want to check out what's being done in hardware already. Here's a few references (Google "square root algorithm hardware" for more):
> Hello everyone. I'm looking for the different ways known to calculate > the square root of real positive numbers by using integer addition > operations only. I'm thinking of their application to microprocessor > subroutines, which work on integer numbers only. > Any ideas?
> Thanks for your time.
Don:
Probably the best use of your time is to pull up all the IEEE publications on this at your closest University library web station. They have dozens and dozens of papers on this topic as it remains an interest to hardware processor designers.
Thanks for replying and for your time. As it happens, I've been doing some research on the web regarding algorithms for extracting the square root of real numbers.
My reason is the following: I've found a way to extract the square root of real positive numbers by the use of algebraic addition only, integer addition, and as far as I've tested it, it seems to work faster than even Newton's method. What I've been doing for the past few months is to look around what's been up with technology, to see if my method is of any worth and, as far as I can tell, it seems better. I use the words "faster" and "better" with much caution. My method is not approximative. It yields, on iterations towards infinity, increasingly accurate values. As a test, I've programmed a machine language subroutine to produce digits of the square root of two and I've been comparing them to (supposedly) NASA results located at http://antwrp.gsfc.nasa.gov/htmltest/gifcity/sqrt2.1mil, and so far my tests compare equally to theirs up to the 100,000th digit. If time and memory allow it, I should soon reach the millionth digit.
If I'm right, I may be on to something here. The method is so simple that extracting square roots by hand can be done by anyone that can add and subtract with pen and paper.
Right now I'm not sure what to do next, if to release it publicly, if to publish it, if to sell it. I'd like to spread the news as far as I can to see what happens next, but I'm not quite sure what to do afterwards. God knows my research could use the funds, but I also know kids at school and everyone in particular could profit from this simple knowledge. The more we know the better for all of us. Any suggestions, based on experience or otherwise?
> Hello everyone. I'm looking for the different ways known to calculate > the square root of real positive numbers by using integer addition > operations only. I'm thinking of their application to microprocessor > subroutines, which work on integer numbers only. > Any ideas?
> Thanks for your time.
Something I wrote years ago: The C code also uses shifts and multiplications. Using only additions might be very inefficient. Which processor do you have in mind? (short...16bit signed integer, long...32bit signed integer)
short sqrt64 ( short i )
/* sqrt64 computes 64 * sqrt ( i ), i < 32768. 0 is returned for i <= 0.
Method: Bisection. */
{ short l, h, m; long t;
/* Check for non-positive input */ if ( i <= 0 ) return 0;
/* Set lower and upper limits for bisection */ l = 64; h = 11585;
/* Set target value for comparison */ t = i << 12;
/* Perform bisection until difference h-l is reduced to 1 */
while ( l < (h-1) )
{ m = l + h >> 1; if ( m*m < t ) l = m; else h = m; } /* end while */
/* Check, which of the two values l or h gives a better result */
if ( ( t - l*l ) < ( h*h - t ) ) return l; else return h;
Don <yss...@hotmail.com> wrote in message <news:lk689uvqursf@legacy>... > Thanks for replying and for your time. As it happens, I've been doing > some research on the web regarding algorithms for extracting the > square root of real numbers.
> My reason is the following: I've found a way to extract the square > root of real positive numbers by the use of algebraic addition only, > integer addition, and as far as I've tested it, it seems to work > faster than even Newton's method. What I've been doing for the past > few months is to look around what's been up with technology, to see if > my method is of any worth and, as far as I can tell, it seems better. > I use the words "faster" and "better" with much caution. My method is > not approximative. It yields, on iterations towards infinity, > increasingly accurate values. As a test, I've programmed a machine > language subroutine to produce digits of the square root of two and > I've been comparing them to (supposedly) NASA results located at > http://antwrp.gsfc.nasa.gov/htmltest/gifcity/sqrt2.1mil, and so far my > tests compare equally to theirs up to the 100,000th digit. If time > and memory allow it, I should soon reach the millionth digit.
> If I'm right, I may be on to something here. The method is so simple > that extracting square roots by hand can be done by anyone that can > add and subtract with pen and paper.
> Right now I'm not sure what to do next, if to release it publicly, if > to publish it, if to sell it. I'd like to spread the news as far as I > can to see what happens next, but I'm not quite sure what to do > afterwards. God knows my research could use the funds, but I also > know kids at school and everyone in particular could profit from this > simple knowledge. The more we know the better for all of us. Any > suggestions, based on experience or otherwise?
