2-adic Svoboda

Torbjörn Granlund tg at gmplib.org
Sun May 2 08:11:30 UTC 2021

IIRC, Svoboda's division trick for N/D is to find a small multiplier m
such that, for the division mN/(mD) we have mD = 100000...XX... with the
high limb of mD being 1000...0.

This idea works also for 2-adic division.  Find m = D^(-1) mod \beta
where \beta is the lomb base.  Then do mN/(mD) or mN mod (mD) with
2-adic norm.  Now mD will end in 0...0001, and the quotient limbs will
be the low limbs of the intermediate remainder.

That should mean that we could use mul_basecase directly for
sbpi1_bdiv_r (or its sibling redc_1).

Surely this is not a new observation.

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list