O(M(n)) division and square root

[Torbjorn Granlund]

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