About sqrt_exact...

[marco.bodrato at tutanota.com]

Ciao,

22 giu 2026, 13:13 da tg at gmplib.org:

> With the current code, bqsrtinv is measurably faster than sqrt for
> small sizes, but it eventually became slower.
>
> Is it evident why it becomes slower for large operands?
>

Well, let's see what is needed to go from n limbs to 2n limbs.
I consider only the superlinear operations.
sqrt
  tdiv_qr 2n/n -> n
  sqr n -> 2n (maybe)

bsqrtinv:
  sqr n  -> 2n
  mullo 2n -> 2n
  mullo n+1 -> n+1

The larger n is, the less mullo is effective in saving operations compared to plain mul, is this the reason maybe?
In the mullo 2n -> 2n, we actually need only the highest half of the result. should we try a mullo n + a mulmid 2n×n?

Meanwile, I also touched the function mpn_bsqrt. It is not used nor documented. But now at least it is tested, and its speed can be measured... I already pushed the changes.

Ĝis,
m