Division by 9 (and other factors of 2^60 - 1)

Niels Möller 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)?

Regards,
/Niels



More information about the gmp-devel mailing list