# Would someone mind elaborating the explanation in the manual?

Brian Hurt bhurt at spnz.org
Mon Oct 27 10:40:13 CET 2003

```On Mon, 27 Oct 2003, Kevin Ryde wrote:

> If you're only testing divisibility then for instance n%3==0 becomes
>
> 	(n * 0xAAAAAAAB) <= 0x55555555
>
> which is one multiply.

In 32-bit.  In 64-bit, if n = 3, then n * 0xAAAAAAAB becomes 0x200000001,
and the test fails.  Although you can make you life somewhat simpler by
only dealing with three cases: 1) 32-bit, where you test that (n *
0xAAAAAAAB) <= 0x5555555, 2) 64-bit, where you test that (n *
0xAAAAAAAAAAAAAAAB) <= 0x5555555555555555), and 3) everything else, where
you test that (n % 3) == 0.

I'd keep case 3.

You snipped too much here:
> > Which isn't always faster than a divide instruction.
>
> True, that should be checked, but almost everywhere one multiply is
> faster than a divide.
>

In every architecture I know of, multiply is at least as fast as divide,
and generally faster.  I'm not sure it's true that a divide is slower than
2 multiplies, a shift, and a subtract (which is what I was comparing it
to).

Brian

```