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

[bodrato at mail.dm.unipi.it]

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...

Regards,
m

-- 
http://bodrato.it/papers/