# non-subquadratic functions in gmp

**Kevin Ryde
**
user42@zip.com.au

*Tue, 26 Aug 2003 07:50:13 +1000*

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.