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

bodrato at mail.dm.unipi.it bodrato at mail.dm.unipi.it
Mon Oct 12 18:20:43 CEST 2009

Dear Niels,

> the current code, there are two recurrency variables, one limb and one
> borrow flag (and for typical use, when bd < B/2, they should in
> principle fit in a single signed word, but I don't see how to get any
> advantage out of that).
> Unlike bdiv_dbmc, this code doesn't handle carry in and out of the
> function in a sane way; the return value is somewhat bogus.

Well, if you return (h + cy<<(GMP_LIMB_BITS -1)), it can be recycled
later... the advantage of the single signed word you mention :-)

> The same algorithm could be used for 2^k - 1 for other k in the range
> GMP_LIMB_BITS/2 <= k <= GMP_LIMB_BITS -1. I'm not sure if
> parametrizing the shift count is going to slow it down (on x86, one
> would need to move the values k and 64-k in and out of the %cl
> register).

I'm not an expert at all, but... I heard of some (SSE2?) fast instruction
for shift by byte multiples. Maybe we should try 2^48-1 (or 2^24-1 for
32-bit)? It'd be enough for both diveby9 and by45...



More information about the gmp-devel mailing list