O(M(n)) division and square root

[Paul Zimmermann]

       Hi,

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

Paul