About sqrt_exact...

[marco.bodrato at tutanota.com]

Ciao Niels,
22 giu 2026, 13:26 da nisse at lysator.liu.se:

> Seems I've forgotten much of bsqrt (even though I think I was involved
> somehow when it was added). And it's for odd numbers only, right? Thanks
> for reminding me.
>
Currently, bsqrt uses bsqrtinv
and inv (mod 2^...) is possible only for odd numbers.


> So then a sqrt_exact could first process trailing zero bits
> (must be an even number).
>
I agree, and that's an easy step.

>  So say what remains is an odd number of 4n limbs. Call
> bsqrt on the low n + 1 limbs (one extra for overlap), and sqrtrem on the
> top 2n limbs (middle quarter of the input completely ignored). Use the
> overlapping limb to select the right sqrt from binv and check that result
> can be glued in a consistent way with the high part. Other variants of
> splitting are possble, e.g, bsqrt on low third, sqrtrem on top third.
>
I was thinking about this today, and about the same as you write.
But since bsqrt seems a little bit slower than sqrt
I think that its slice should shrink. Maybe 2/3 and 1/6...
It should be tuned :-)

> I think that would qualify as a bidirectional algorithm. If it's
> actually useful, I don't know.
>
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...
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.
Can this be faster than the current code? I don't know.
Ĝis,
m