Mel Evans <MEvans1027@AOL.COM> jokingly wrote:

> To multiply by 3, double and add to original.  To divide by 3,
> just do the inverse!

and Peter van Hoof <PICLIST@MITVMA.MIT.EDU> thought HE was
joking, too, when he wrote:

> Yeah subtract your answer and then devide by two to get your answer
> >:)

    Actually, Peter, you CAN do it that way... It looks something
    like this:

        To find N/3:

        1.  Make an initial guess at the answer and call it Q.

        2.  Do just as you said... Subtract Q from N, then divide the
            result by two.  If the result of that division is Q,
            you're done; Q = N/3.

        3.  Otherwise, you need to adjust Q; if the result of the
            division-by-2 was SMALLER than Q, Q = Q - Q/2.  If the
            result was LARGER than Q, Q = Q + Q/2.

        4.  Loop back to Step 2.

    Note that, if your initial guess is N/2, this algorithm performs
    exactly the same steps as the one I posted earlier; it computes
    Q = N/2 - N/4 + N/8 - N/16 + N/32 - N/64.... etc.

    If you start with Q = 2^x, where x = log2(N) (i.e., x = the
    number of bits necessary to express N), the algorithm just steps
    through Q from MSB to LSB, setting or clearing each bit
    appropriately... In other words, it's guaranteed to terminate
    within x iterations.

    -Andy

    P.S.  Since we're doing integer math, you probably need to add
          one more test to Step 2... Make it:  "If the result of the
          division is Q, OR IF Q = 1, you're done."

=== Andrew Warren - fastfwd@ix.netcom.com
=== Fast Forward Engineering - Vista, California
=== http://www.geocities.com/SiliconValley/2499