mpn_sqrtrem{1,2} - patch for pure C implem

Marco Bodrato bodrato at mail.dm.unipi.it
Sun Apr 2 04:44:48 UTC 2017


Ciao,

Il Sab, 1 Aprile 2017 9:02 pm, Adrien Prost-Boucle ha scritto:
> On Sat, 2017-04-01 at 18:15 +0200, Marco Bodrato wrote:
>> After the patch:
>> $ (cd tests/devel; make sqrtrem_1_2)&&time tests/devel/sqrtrem_1_2 c
>> Corner cases tested, up to bits:
>> \ 63
>> Values of a single limb, tested.
>>
>> > user	1m47.889s

> I also saved one instruction in the final correction step (for now lightly
> tested, just make check).

> +  /* Correction: add 1 to the root if needed (test: r^2 + 2r - a < 0) */
> +  accu = a0 - root * root;
> +  if ( (mp_limb_signed_t)(2*root - accu) < 0) {
> +    accu -= 2*root + 1;
> +    root++;
> +  }

Compared to your previous proposal, that's a small regression, I get:
user 	1m49.209s

I refined a little bit the exhaustive testing program for sqrtrem[12]:
https://gmplib.org/repo/gmp/rev/c32d616089b4

For ABI=32, can you please tell us the timings obtained with:

make&&(cd tests/devel/;make sqrtrem_1_2&&time ./sqrtrem_1_2 x 1)

before, and after your patch (maybe playing with the different flavours of
the correction step :-)?

Best regards,
m

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



More information about the gmp-devel mailing list