New mpn_divexact code
Paul.Zimmermann at loria.fr
Tue Aug 1 10:41:52 CEST 2006
> I've put improved mpn_divexact code on the the tidbits page
Great! The new timings are very impressive!
> Determining the optimal inverse size is a tricky problem. It
> depends on underlying algorithms such as FFT multiplication and
> how the inverse is computed.
> Determining the cutoff point between basecase divexact and the
> sub-quadratic code is another difficult problem. It is actually
> not a cutoff point, but a cutoff line, as both the dividend size
> and the divisor size comes into play. (Currently it is suboptimally
> implemented as a point.)
When the quotient size (qn) is smaller than the divisor size (dn),
it suffices to consider dn limbs of the dividend and divisor (either
low or high bits, or dn/2 low bits and dn/2 high bits), thus a cutoff
point is enough.
The only real problem is when qn > dn.
> The next thing to do is implementing Jebelean's bidirectional
> modular inversion algorithm. That should save a good deal of the
> inversion time.
The tricky thing here is to glue the high and low parts of the quotient,
and ensure the middle bits are correct.
By the way, I was at the ANTS VII conference last week in Berlin.
There were interesting talks about pseudosquares by Sorenson and
Wooding/Williams. This enables to write a rigorous primality test
up to a given bound (currently about 30 digits), with the same cost
of O(log(n)) modular exponentiations for a n-digit number. This might
be something to consider for future revisions of primality testing
More information about the gmp-devel