About sqrt_exact...

[marco.bodrato at tutanota.com]

Ciao,
16 giu 2026, 18:42 da :

> I started with a very simple optimization: an initial loop on a single limb, and...
>
And the next step was to optimize every step.

The timing was:
> [bodrato at shell ~/gmp-repo]$ /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       #0.9083
> 2        #0.000000024        1.4472
> 4         0.000000065       #0.8762
> 8         0.000000114       #0.9990
> 16        0.000000276       #0.8852
> 32       #0.000000441        1.3615
> 64       #0.000000857        2.0866
> 128      #0.000001938        3.1572
> 256      #0.000005202        3.7938
> 512      #0.000016213        3.7798
> 1024     #0.000052126        3.5139
> 2048     #0.000159041        3.1950
>
Now we have
[bodrato at shell ~]$ /var/tmp/bodrato/gmp/hg/build/tune/speed -r -s 1-3000 -p 100000000 -f 2 mpn_sqrt mpn_bsqrtinv
overhead 0.000000001 secs, precision 100000000 units of 2.86e-10 secs, CPU freq 3500.17 MHz
             mpn_sqrt  mpn_bsqrtinv
1         0.000000009       #0.5729
2         0.000000024       #0.3436
4         0.000000065       #0.5287
8         0.000000113       #0.6261
16        0.000000276       #0.5841
32        0.000000439       #0.8851
64       #0.000000859        1.2817
128      #0.000001936        1.8916
256      #0.000005178        2.3169
512      #0.000016193        2.2998
1024     #0.000052107        2.1233
2048     #0.000158778        1.9671

With the current code, bqsrtinv is measurably faster than sqrt for small sizes, but it eventually became slower. It currently is used only by mpn_perfect_power_p, but I'm not sure it's worth having it instead of directly using using mpn_sqrt.

We also have a function mpn_bsqrt (...), which is not used at all, if I understand correctly.

Ĝis,m