Path: republic.btigate.com!news-xfer.netaxs.com!news-peer.gip.net!news.gsl.net!gip.net!news-peer.sprintlink.net!news.sprintlink.net!Sprint!newsfeed.nacamar.de!uni-erlangen.de!newsfeed1.telenordia.se!pepsi.tninet.se!not-for-mail
From: "Stefan Odelfalk" <sod@elit.se>
Newsgroups: comp.sys.hp48
Subject: Fast integer and FP square roots
Date: Jan 07 1998 00:00:00 GMT
Organization: Algonet/Tninet
Message-ID: <68vvbl$e1u$1@zingo.tninet.se>
NNTP-Posting-Host: rodney.elit.se
X-Newsreader: Microsoft Outlook Express 4.72.2106.4
X-Mimeole: Produced By Microsoft MimeOLE V4.72.2106.4
Xref: republic.btigate.com comp.sys.hp48:5875


Contents of this document

1. Introduction
2. How to do it the easy way
3. Why does this work?
4. Speeding up the algorithm
5. Comparison
6. Rounding off
7. Implementation issues
8. Source code
9. Binaries


1. Introduction

I once found an instruction booklet for an abacus. When skimming
through this I was amazed at the complex calculations you can
perform with this tool. Some of the algorithms used were pretty
clever, and this document is based upon the instructions for
calculating square roots that were given in the booklet.

For comments or improvements, contact me:

Stefan Odelfalk,
sod@elit.se


2. How to do it the easy way

When simplified as far as possible the algorithm for calculating
the square root of N can be described as:

1. Set X to N.
2. Set Y to 1.
3. Set X to X-Y.
4. If X >= Y+2, set Y to Y+2 and go to step 3.
5. Set Y to (Y+1)/2.

After doing this, Y will be the largest integer such that Y^2 is
less than or equal to N, i.e. floor(sqrt(N)). Moreover, X will
be the error in the integer approximation, i.e. Y^2+X=N.

For practical purposes it is easier to use this version (the
first one will be used for the proof in the next section):

1. Set X to N.
2. Set Y to 1.
3. Set X to X-Y.
4. Set Y to Y+2.
5. If X >= Y, go to step 3.
6. Set Y to (Y-1)/2.

This the same algorithm but it does one unnecessary addition to
Y in step 4 and then corrects this in step 6 (note the minus
sign that replaces the plus sign). This version is easier to
implement since the testing in step 5 (formerly 4) is less
complicated.

Note that the only operations used in both description is
comparison, subtraction, addition and division by 2, which are
all very efficient when programmed in ml for example.

A tiny user-rpl program that implements this was posted to the
newsgroup just before Christmas and looked like this:

<< 1 SWAP WHILE DUP2 <= REPEAT OVER -
SWAP 2 + SWAP END DROP 1 - 2 / >>


3. Why does this work?

Proving that the algorithm is correct is easy. Observe that when
looping Y will run through the series 1, 3, 5, ..., Y, i.e. the
odd integers. The total subtracted from X when we reach step 5
in the algorithm will thus be 1+3+5+...+Y which is ((Y+1)/2)^2
(convince yourself that this is true).

Supposing that N is an even square number (i.e. N=p^2 for some
integer p), X will be zero when the algorithm reaches step 5,
and 1+3+5+...+Y will be equal to N. In other words,
((Y+1)/2)^2=N or (Y+1)/2=sqrt(N), so you see why we do the final
addition and division in step 5.

If N is not an even square number (in other words, N=p^2+r for
integers p and r where r < (p+1)^2), X will be a non-zero
positive integer when we reach step 5, and the condition in step
4 assures us that X is less than Y, the last term in the sum. In
fact, when the algorithm finishes, X will be r and Y will be p.


4. Speeding up the algorithm

The simple version of the algorithm is nice, because it is clear
and easy to understand. The obvious shortcoming is running time;
the time used is proportional to the square root of N. To see
why this is so, consider the loop: at every iteration we add 2
to Y. This corresponds to adding 1 to the final result. In other
words, the algorithm tries all solutions 1, 2, 3, 4, and so on
until it finds the correct one. Even if the test is rather
simple, this will take a very long time for large inputs.

The idea used for speeding it up is to apply the algorithm to
the most significant digits of the input first, then proceed to
less significant digits. It also based upon the simple fact that
sqrt(100*N)=10*sqrt(N).

Perhaps an example is the best way to explain this. The simple
version of the algorithm proceeds like this for input N=8 (I use
the latter version here):

X      Y
8      1          X >= Y, so iterate
8-1=7  1+2=3      X >= Y, so iterate
7-3=4  3+2=5      X < Y, so stop
       (5-1)/2=2  Y^2+X=2^2+4=8=N

Now, if the input is N=876543, instead of starting with Y=1, we
set Y to 10000, which is the largest integer less than or equal
to N on the form 100^p where p is an integer. Instead of adding
2 to Y in step 4, we add 20000. This would look like:

X                    Y
876543               10000                X >= Y, so iterate
876543-10000=866543  10000+20000=30000    X >= Y, so iterate
876543-30000=846543  30000+20000=50000    X >= Y, so iterate
...
236543-17000=66543   170000+20000=190000  X < Y, so stop

To continue from here, we subtract 10000 from Y and divide Y by
10 (not related to the division by 2, this comes later). We then
add 100 to Y to initialise for the next loop; also we will now
add 200 to Y in each iteration instead of 20000. Do not touch X.

X                    Y
66543                18100            X >= Y, so iterate
66543-18100=48443    18100+200=18300  X >= Y, so iterate
48443-18300=30143    18300+200=18500  X >= Y, so iterate
30143-18500=11643    18500+200=18700  X < Y, so stop

To continue, subtract 100 from Y and divide by 10. Then add 1 to
initialise for the final loop.

X                Y
11643            1861         X >= Y, so iterate
11643-1861=9782  1861+2=1863  X >= Y, so iterate
9782-1863=7919   1863+2=1865  X >= Y, so iterate
...
2318-1871=447    1871+2=1873  X < Y, so stop

Now we are done, the only thing that remains is subtracting 1
and dividing by 2 which gives Y=(1873-1)/2=936. This is the
correct answer since 936^2=876096 which is N-X=876543-447.

Here is the actual algorithm:

  1.  Set Y to N.
  2.  Set C to 100^p where p the largest integer such that C is
      less than or equal to N.
  3. Set X to 0.
  4. Set X to X+C.
  5. If X > Y, go to step 9.
  6. Set Y to Y-X.
  7. Set X to X+2*C.
  8. Go to step 5.
  9. If C = 1, go to step 13.
  10. Set X to (X-C)/10.
  11. Set C to C/100.
  12. Go to step 4.
  13. Set X to (X-1)/2.

I know this looks more like a BASIC program than an algorithm,
but this formulation will make the transition to ml a lot
easier.

I have not yet had time to construct a proof for this algorithm,
nor have I had time to approximate the running time. If anyone
is interested in doing this please contact me.


5. Comparison

Counting the number of subtractions (X-Y) here gives us
9+3+6=18, in other words we go through the loop a total of 18
times! Compare this to 936 times for the simple version of the
algorithm presented above...


6. Rounding off

For uses in integer math this algorithm is useful since it
produces both the square root and the exact error (i.e.
Y^2+X=N), but if you want to use it for fixed-point
approximations you would probably want to round the answer to
keep your calculations as close to the real value as possible.

Since Y is guaranteed by the algorithm to be the largest integer
such that Y <= sqrt(N), you will have to choose between Y and
Y+1. Two ways of doing this spring to mind. First, you may want
to use the one of Y and Y+1 that is closest to sqrt(N). Second,
you may want to use the one that squared is closest to N.

The first way can be expressed as "if sqrt(N)-Y is larger than
(Y+1)-sqrt(N), choose Y+1". This test can be simplified to:

  sqrt(N)-Y > (Y+1)-sqrt(N)
  2*sqrt(N) > 2*Y+1
    sqrt(N) > Y+1/2
          N > Y^2+Y+1/4
      N-Y^2 > Y+1/4  and since N-Y^2 is equal to X,
          X > Y+1/4  and since both X and Y are integers,
          X > Y

In other words, if upon completion of the algorithm X > Y then
you should add 1 to Y.

The second way can be expressed as "if N-Y^2 is larger than
(Y+1)^2-N, choose Y+1". This simplifies to:

  N-Y^2 > (Y+1)^2-N
      X > Y^2+2*Y+1-N
      X > -(N-Y^2)+2*Y+1
      X > -X+2*Y+1
    2*X > 2*Y+1
      X > Y+1/2
      X > Y

This is the same result as above (this might be obvious to most
of you but I dont think so). So either way, if X > Y when you
finish you should add 1 to Y.


7. Implementation issues

When it comes to programming, working in base 10 is often not
practical. For example, step 2, 10 and 11 in the algorithm would
be difficult to do in ml. However, the described algorithm
translates beautifully to base 16. Just replace the lines with:

  2.  Set C to 256^p where p the largest integer such that C is
      less than or equal to N.
  10. Set X to (X-C)/16.
  11. Set C to C/256.

This can be done easily in ml using bit shifts. This means that
the entire algorithm can be implemented using only shifts,
additions and subtractions.

Another observation is that no intermediate results are larger
than the input N. This means that if N fits in a 16-nybble
register, then all calculations can be performed using only 16-
nybble registers. Coincidentally, this is also the default size
of the built-in integer data type and the size of the
processors arithmetic registers A, B, C and D.


8. Source code

The source code for JAZZ. The tabbing should look ok in ED.

%%HP: T(1)A(D)F(.);
"::
CK1NOLASTWD
CK&DISPATCH1 #B
::
TOTEMPOB (make sure it's safe
           to overwrite it)
CODE
   GOSBVL   =SAVPTR
   C=DAT1   A
   D1=C
   D1=D1+   5
   C=DAT1   A  * fetch size field
   LA(5) 16+5  * should be 16 nibbles
   ?C=A  A
   GOYES sizeok
   GOSBVL   =GETPTR
   GOVLNG   =DOSIZEERR
sizeok   D1=D1+   5
   C=DAT1   W  * fetch value
   ?C=0  W
   GOYES exit  * sqrt(0)=0
   A=0   W  * initialize mask by
   A=A+1 W  * shifting a #1 left
masklp   ?C<A  W  * two nibbles at a
   GOYES maskfix  * time until it's bigger
   ASL   W  * than C or wraps
   ASL   W
   ?A=0  W
   GOYES fullwd
   GOTO  masklp
fullwd   A=A+1 W  * we wrapped so we
   ASRC     * set the mask to
   ASRC     * 2^(64-8)
   GOTO  maskok
maskfix  ASR   W  * shift it back
   ASR   W  * one byte
maskok   D=C   W  * store the value in D
   C=0   W
shiftlp  CSR   W
   C=C+A W  * C=C+1 somewhere
   A=A+A W  * double the mask (to a 2)
subloop  ?D<C  W  * no more to subtract here
   GOYES subdone
   D=D-C W
   C=C+A W  * next odd integer
   GOTO  subloop
subdone  ASRB     * set mask to a 1 again
   C=C-A W  * C=C-1 somewhere
   ASR   W
   ASR   W  * shift mask
   ?A#0  W  * more to do?
   GOYES shiftlp
   CSRB     * C=C/2
   ?D<=C W  * no need to round up?
   GOYES exit
   C=C+1 W
exit  DAT1=C   W
   GOVLNG   =GETPTRLOOP
ENDCODE
;
;
"


9. Binaries

The binary, encoded with ASC (call it whatever you like).

%%HP:T(1);
"D9D202BA812BF81D5040D9D2075660CCD203B0008FB976014713517414780824
510008A2018F2D7608D7AC81174157797A96AF0B749F6E1BF0BF0978606FEFB7
48148146900BF4BF4AF7AF2BF6A72A749F7C0B73A7264FF81CB72BF4BF497C9D
81E9FF50B7615578D34150B2130B21304F8B"



[the following was from a repost, adds some more info]

Here is the source code and binary that performs the integer
root algorithm that I described in my previous posting
(which Mr. John H Meyers refered to as "the odd-number
algorithm" and apparently was implemented in earlier HP
calculators) and promised to post later. You will probably
not understand the code if you haven't read that posting,
so I suggest that you do so.

The program is almost a direct translation of the algorithm
description. Register D holds the variable X, C holds Y and
A holds the "mask" C. This implementation also uses the
mentioned rounding scheme.

Some error checking has been added. The program expects an
integer (looks like: # 123d) on level 1. This integer should
be 64 bits (assure this by doing 64 STWS). All other inputs
will produce some kind of error.

A user-rpl equivalent of this program (only slower and with
less precision) would be:

<< B->R V 0 RND R->B >>  (where V is a square root sign)


For those of you who are skeptical, here is why the speeded-up
version of the algorithm works (decimal version, variable names
refers to the original posting):

Observe that when you have subtracted the numbers
1, 3, 5, ..., 19 this totals to ((1+19)/2)^2 = 100, so if X is
larger than 100 you might as well subtract that initially, and
then continue at 21. Also, 1 + 3 + ... + 39 = 400, so why not
subtract this and continue at 41 (and so on)?
This fits nicely into the algorithm, since if you start
subtracting Y = 100, 300, 500, ... from X until no further
subtraction is possible, all you have to do is translate this Y
into the one to "continue" at (100 to 21, 300 to 41). This
translation formula is T1(X)=(X+100)/10+1 in this case.

Continuing this, observe that
100 + 300 + 500 + ... + 1900 = ((100+1900)/20)^2 = 10000, so if
X initially is larger than 10000, subtract that and continue at
2100 as described in the previous paragraph. In this case, the
translation formula is T2(X)=(X+10000)/10+100. You can easily
see how to extend this to even larger positions, can't you?

However, there is one caveat: if X initially is smaller than
100 you cannot use the translation formula T1(0)=(0+100)/10+1=11,
since you should "continue" at 1 in this case. Rephrasing the
algorithm the way I did with the basic one you do not get this
problem. Instead of stopping subtracting at the odd number that
is the last you can subtract from X, stop at the first one that
you cannot subtract. The translation then becomes
T1'(X)=(X-100)/10+1 and this works well even for the troublesome
case. Here is an example:

Starting out with the integer 40401, observe that it's larger
than 10000, so subtract that: 40401-10000=30401. The next odd
tenthousandth is 30000, which is also ok, so subtract:
30401-30000=401. The next number is 50000, not ok, use the
translation to find out where to continue:
T2'(50000)=(50000-10000)/10+100=4100, which is bigger than 401,
so translate again: T1'(4100)=(4100-100)/10+1=401, which can
be subtracted from 401 yielding 401-401=0. The next number to
subtract is 403, which is bigger than 0 so stop. We cannot
translate any further now, so the square root of 40401 must be
(403-1)/2=201 (and it certainly is).

Finally, there is one thing I haven't had time to look into. The
included implementation uses powers of 256 for the shifts (the
example above uses 100) and the translation formulas
T1(X)=(X-256)/16+1, T2(X)=(X-256^2)/16+256 and so on. You might
as well use powers of 16 and the translations
T1(X)=(X-16)/4+1, T2(X)=(X-16^2)/4+16. I have no idea which one
is faster, and if someone would like to try this and inform me
of their findings, I'd appreciate it.

That's all for now, I think.

Stefan Odelfalk  (sod@elit.se)