Vladimir M. Klochko wrote:
>

>     Well, let us check the formula  N/3=(N*0x55+128)/256.

  <SNIP>

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

  No, but...

  <SNIP>

>     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!

  Actually, my change to the approximation was this:

  N/3 ~=  (N+1)*0x55/0x100

  Which I proved was exact for INTEGER DIVISION, which (to reiterate)
is defined (correctly) by John Halleck as:

 a integer_divide b  = (a -(a % b)) /b

Integer division does not provide rounding. For those of you who are
C-junkies, integer division is the same thing as this:

int integer_divide(int a, int b)
{
  return(a/b);
}

if you want rounding, then you'll need to do something like:

  return(a/b  + ( (a>=b/2) ? 1 : 0) )

or slightly more accurate but less safe:

  return(a/b  + ( (2*a>=b) ? 1 : 0) )

----------
Out of some kind of perverse enjoyment I've shown that the general
formula holds true.

 a // b = ((a+1) * (b//N)) // N

on the condition that b<N and a < b*N. For brevity, I defined '//'
to be integer division.
For the divide-by-3 case,
  b = 3
  N = 256
  b//N = 85

For the divide-by-5 case,
  b = 5
  N = 256
  b//N = 55

The divide-by-5 case can be implemented in 19 cycles (it may've been
17... my notes are not with me now).

If anybody is interested in the proof, then send me an e-mail and I'll
get it to you next week (when I have my notes).


Scott

--

  If you believe everything you read then you shouldn't read.
                                             Japanese Proverb