Square root
Don
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.
Frank A. Adrian
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):
http://csdl.computer.org/comp/mags/mi/1997/04/m4056abs.htm
http://www.cs.cornell.edu/jyh/papers/tpcd94/paper.pdf
http://www.azillionmonkeys.com/qed/sqroot.html (check bottom of page)
faa
anonymous
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.
Don
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?
Thank you.
Hugo Pfoertner
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;
} /* End of function sqrt64 */
Hugo Pfoertner
David Sexton
Did you look at
http://mathworld.wolfram.com/WolframsIteration.html
I've done some similar work with logs and antilogs--more to come.
David Sexton