Hi!
15-Mar-98 00:54 Paul B. Webster VK2BZC wrote about "Re: divide by 3":

 >> Vladimir M. Klochko wrote:
 >>
 >> > Furthermore, it's possible to use the same method to divide by 5:
 >> >     1/5=0.0011001100110011...
 >>
 >>   Which is of course quite useful in decimal conversion.
    Yes, but for indication only. Not for further computations.
And Bin2Dec need both quotient and reminder (this method doesn't
give the reminder).

 >> > Are these methods (quick and not exact) usefull?
 >> > May be. I have a doubt.
 >>
 >>   You misunderstand something here.  They *are* quick, and they *are*
 >> exact.  They are the fastest way to perform constant divisions.  They
 >> are *as* accurate as but much faster than "long division" algorithms.
 >> In either case, you must perform *all* intermediate calculation without
 >> truncation, that is, you have to retain and perform addition on the
 >> *whole* of any right-shifted value.


    Well, let us check the formula  N/3=(N*0x55+128)/256.
The best method is a brutal force, because it helpes me to
reduce a quantity of English words. :)

    Here the output of the simple C program. The first column is N,
the second is (N*0x55+128)/256, the third N-3*((N*0x55+128)/256)
(it should be named "reminder"), the 4-th and 5-th are N/3 and N%3.

  0    0,  0    0,  0
  1    0,  1    0,  1
  2    1, -1    0,  2
  3    1,  0    1,  0
  4    1,  1    1,  1
  5    2, -1    1,  2
  6    2,  0    2,  0

    Reminder of fast algorithm is {-1,0,1} since we use
rounding. Okay. Let us continue.

    . . .
126   42,  0   42,  0
127   42,  1   42,  1
128   43, -1   42,  2
129   43,  0   43,  0
130   43,  1   43,  1
131   43,  2   43,  2
132   44,  0   44,  0
133   44,  1   44,  1

    Note that reminder became TWO!
    And both (128/3) and (131/3) (i.e.((128+3)/3)) are 43!

    . . .
252   84,  0   84,  0
253   84,  1   84,  1
254   84,  2   84,  2
255   85,  0   85,  0
    And up to N=255 there are no more surprises.


    Any exact division algorithm should give a reminder in range
0,1,...(K-1) for any divisor K. Of course, using rounding we can
shift this range. But there are only K different legal values
for reminder. The above table shows FOUR values {-1,0,1,2} for
reminder of division by THREE using this algorithm.

    So, is it an "*exact* algorithm"?

    The reason is quite clear. The exact formula is
N/3=(N*0x55+128)/255 (not .../256!). 128 (or 127, or 0 -- no
matter) represent only the method of rounding and no more. Using
division by 256 instead of division by 255 we found the fast
method. :)  And loose precision. :(

    Though it is possible to vary the constant 128 and try to
restore precision (but for limited range of N only!).
Scott Dattalo did it. And it's work. Exellent!

--

                                    Vladimir M. Klochko