mpn_sqrtrem{1,2}

[Marco Bodrato]

Ciao,

Il Gio, 16 Febbraio 2017 10:45 pm, Adrien Prost-Boucle ha scritto:
> Before doing heavy (for me) asm development,
> I first wanted to evaluate could be the impact, on the mpz_sqrt()
> function itself, of a 2-3x speedup on functions mpn_sqrtrem{1,2}.


> There is some noticeable speedup only for very short bit widths.
> And the speedup is "only" 20-30%.
> Which is a bit disappointing given the 2x-3x speedup put
> on mpn_sqrtrem{1,2}.

> So clearly these functions are not the hot spot, contrary to what was
> assumed at the beginning of the discussion about accelerating sqrt.

Every call to mpn_sqrtrem does call mpn_sqrtrem{1,2} just once. Speeding
up those two functions will not impact much on the asymptotic timings for
big integers. But the performance on "small" numbers IS important.

The current mpn_sqrtrem2 implementation calls mpn_sqrtrem1. If the new one
does not, mpn_sqrtrem1 will be used ONLY for single-limb operands (less
than 32 or 64 bits, depending on the ABI), and it will be left completely
untouched for larger computations... but it would anyway be important to
have it faster, and cleaner, if possible!

Regards,
m

-- 
http://bodrato.it/papers/