About sqrt_exact...

[marco.bodrato at tutanota.com]

We are talking around sqrt_exact...

Maybe a possible implementation of sqrt_exact could use the ideas implemented in our internal functions mpn_bsqrtinv and mpn_bsqrt...

The first one (mpn_bsqrtinv) is used in the static function is_kth_power, used by mpn_perfect_power_p.
I looked into it a little bit and... it currently seems not very efficient.

At first is_kth_power, after computing R the square root modulo some B^n, checked both if R² or (B^n-R)² gave the expected result. But as Seth Troisi noted in the other thread, we know in advance the size of the square root of a number, so that now it checks only the "root" with the expected length.
https://gmplib.org/repo/gmp/rev/695187d727e4
To measure if the function is efficient or not, I added support to measure mpn_bsqrtinv to tune/speed.
To have it comparable with mpn_sqrt, I actually decided to measure for size "n" the computation of the bsqrtinv of size n/2... Meybe I'll change this soon.
https://gmplib.org/repo/gmp/rev/a89e395f552d

Anyway, on "shell" the current implementation seems really slow:
 /var/tmp/bodrato/gmp/hg/build/tune/speed -r -s 1-3000 -p 100000000 -f 2 mpn_sqrt mpn_bsqrtinvoverhead 0.000000001 secs, precision 100000000 units of 2.86e-10 secs, CPU freq 3500.17 MHz
             mpn_sqrt  mpn_bsqrtinv
1        #0.000000009       11.2977
2        #0.000000024        5.1754
4        #0.000000065        2.2961
8        #0.000000114        1.7856
16       #0.000000275        1.2089
32       #0.000000439        1.5816
64       #0.000000857        2.1930
128      #0.000001921        3.2289
256      #0.000005172        3.8368
512      #0.000016201        3.7842
1024     #0.000052364        3.4894
2048     #0.000158778        3.1970

Ĝis,m