non-subquadratic functions in gmp

[Kevin Ryde]

Paul.Zimmermann@loria.fr (Paul Zimmermann) writes:
>
> which functions are still O(n^2) in gmp-4.1.2?

Binomial coefficients, though they don't really rate as important.

> I know gcd (and gcdext).

And the jacobi symbol similarly (currently a rather simple minded
binary algorithm).

> I remember divexact was O(n^2)
> in a previous release. Is it still the case? 

Yes, via mpn_bdivmod.

> Does anybody on the list know better algorithms?

Mark Sofroniou had some code for a sub-quadratic divexact which he'd
used in mathematica (or was going to).  If I remember it wasn't an
inverse but some sort of straight divide and conquer.  Don't know if
that'd be faster or slower.

> /* rop <- 1/op1 mod 2^t. Assumes op1 is odd. */

I've still got modlimbs_invert.c from mpm, but alas never got around
to incorporating your suggestions about avoiding re-calculating low
limbs on each iteration.