# O(M(n)) division and square root

Torbjorn Granlund tg at gmplib.org
Tue Jan 12 12:48:56 CET 2010

```Paul Zimmermann <Paul.Zimmermann at loria.fr> writes:

a nice side-effect of the fact that division in GMP has now complexity O(M(n))
is that the square root has complexity O(M(n)) too (since the square root
algorithms uses division):

GMP 4.3.2 on 2.4Ghz Opteron:
achille% ./speed -s 1-10000000 -f 2 -r mpn_mul_n mpn_dc_tdiv_qr mpn_sqrtrem
...
1048576   #1.555764000        5.4396        1.8143
2097152   #3.278501000        6.1238        2.0997
4194304   #6.921948000        6.7607        2.3756
8388608  #14.488797000        7.4266        2.6747

GMP 5.0.0 on 2.4Ghz Opteron:
achille% ./speed -s 1-10000000 -f 2 -r mpn_mul_n mpn_dc_tdiv_qr mpn_mu_div_qr mpn_sqrtrem
...
1048576   #1.488774000        2.7105        2.7052        1.1457
2097152   #3.172518000        2.7835        2.7649        1.2540
4194304   #6.838960000        2.7532        2.7478        1.3265
8388608  #14.940729000        2.7201        2.7172        1.3533

Indeed.  Several operations have lost a log(n) term as a result of the
division improvements, e.g., kth root and conversion from the internal
format to digit strings.

In mpn/generic/rootrem.c we actually use mpn_div_q, which is much faster
than remainder-full division unless it needs to check the results.

There are still a few operations that are slow in GMP:

1. Jacobi/Lagrange is O(n^2) (should be O(M(n)log(n)).
2. n-over-k is completely naive
3. n-factorial is slightly inefficient (I don't recall the details)
4. Plus other things, surely.

--
Torbjörn
```