Division by 9 (and other factors of 2^60 - 1)
nisse at lysator.liu.se
Tue Oct 13 10:18:27 CEST 2009
Torbjorn Granlund <tg at gmplib.org> writes:
> nisse at lysator.liu.se (Niels Möller) writes:
> Repeated divexact_by3 seems to be the most efficient way, so far, to
> divide by 9 on x86_64. It might be fun to try to do two iterations of
> bdiv_dbm1c as a single loop. That would be able to handle division by
> 9, 15 and 25.
> Two-iteration bdiv_dbm1c is probably the way to go on AMD chips.
And to correct myself: 15 can be handled by current bdiv_dbm1c. Doing
it twice, new interesting divisors include 9, 25, 45, 75 and 225 (and
more, involving the larger factors of 2^64 - 1).
Do you think there are any interesting machines where division via
2^60 - 1 is useful (or 2^24 - 1, for 32-bit machines)?
More information about the gmp-devel