Andrew Warren <fastfwd@ix3.ix.netcom.com> wrote:


   From first message:

>Your algorithm is pretty cute... I don't think I've seen it before.
>I guess I'm not eligible for the prize, though ..

   I didn't rule you out.  Next time you're in Milwaukee we can bend
   an elbow.

   Your description is quite clear.  Actually, the algorithm is based on
   the one I learned in grammar school, maybe 45 years ago.  We were
   taught a technique to extract roots that involved grouping the number
   in chunks of two digits starting at the decimal point.  What surprises
   me is that very few people with whom I have discussed this have ever
   heard of the algorithm.  It has the advantage (at least in the binary
   world) of not requiring any multiples or divides, permitting
   relatively fast execution time. A Newton-Raphson loop provides more
   compact code but requires a divide in each loop.  Your trick of adding
   odd numbers is probably the most compact but execution time for a
   four byte number would be a little long for most application.


   From second message:

>    bc      xx                SKPC
>    incf    t_a, f            INCFSZ  T_A
>    bnz     xx                GOTO    XX
>    incf    t_x, f            INCF    T_X
> xx:
>    movf    t_a, w
>    subwf   n_a, w
>    movwf   t_a
>    bc      yy                SKPNC

   Good hack.   (Sure would be nice to have a subtract with borrow.)

>P.S.  Have you noticed that your routine behaves inconsistently when
>      evaluating the square root of, say, (x*x)-1?  If x is even,
>      the routine returns x-1; if x is odd, it returns x.
>
   I thought of this late last night after I posted the original
   message.  The root (no pun intended) of the problem comes in at the
   last pass.  At that stage, p_a:p_b contain h'0001'. I shift this
   right and 'or' with the partial root but this drops the last bit into
   the bit bucket and the trial root does not get changed. From a
   practical point, in many applications this would not be a big deal
   but from an academic view this anomaly is not acceptable and will
   require some more thought.  Good catch - probably worth a second
   beer.


--
Bob Fehrenbach    Wauwatosa, WI     bfehrenb@execpc.com