About sqrt_exact...

[marco.bodrato at tutanota.com]

Ciao,

22 giu 2026, 17:50 da marco.bodrato at tutanota.com:

> Ciao Niels,
>
> 22 giu 2026, 13:26 da > nisse at lysator.liu.se> :
>
> I agree, again. It should be a faster way to compute the square root
> if ones know in advance that a number is a perfect square...
>
At last I wrote some code, it's attached.
I'm using bsqrt for the lowest 1/4 of the result,
and the plain sqrt for the highest 3/4.


> Or maybe it can be used to detect if a number actually is a perfect square.
> If the overlapping limb reveals that the
> two parts can not be "glued in a consistent way, then it's not a square.
> An if the two parts can be glued... maybe it's enough to check if
> a mulmid gives the expected result.
>
I'm trying with mulmod_bnm1.


> Can this be faster than the current code? I don't know.
>
It is, but maybe too slightly faster for such a complex code, is it worth adding?Here are the timings on my laptop:

$ build/tune/speed -p100000000 -c -s 1-1600 -f1.5 mpn_perfect_square_p
overhead 5.25 cycles, precision 100000000 units of 5.28e-10 secs, CPU freq 1895.63 MHz
                 after            before
1                68.43             70.22	    
2               133.89            128.77	    
3               189.03            319.57	    
4               185.58            272.31	    
6               318.39            414.99	    
9               575.23            854.72	    
13              791.94            967.31	    
19             1203.43           1448.53	    
28             2038.94           1763.29	    
42             2859.41           2804.96	    
63             4504.65           4614.51	    
94             6674.98           6774.17	    
141           10713.67          12355.94	    
211           17956.97          21342.91	    
316           31805.80          39641.78	    
474           57801.74          74848.89	    
711          112779.93         147468.30	    
1066         233826.29         280769.99	    
1599         452747.42         529568.46

But a lot of work is still needed, because:
 - the code passes "make check" and also some deeper testing, but... it is not completely correct, there are some possible corner cases that are not handled yet;
 - now it uses some hardcoded thresholds, that should be tuned instead;
 - is the last mpn_sqrmod_bnm1 computation a correct way to check if the result actually is the root of the given operand?
 - maybe we can gain some more speed with a more clever implementation of mpn_bsqrt?

If someone wants to test this code, and maybe reply with some comment, I'll be happy.Is it worth working on that approach?
Or it's too risky to add a complex piece of code for a marginal speed-up, maybe?

Ĝis,
m
-------------- next part --------------
A non-text attachment was scrubbed...
Name: sqrt_exact.diff
Type: text/x-patch
Size: 14518 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20260717/67259a2e/attachment.bin>