Would someone mind elaborating the explanation in the manual?
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
More information about the gmp-discuss