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
More information about the gmp-devel
mailing list