mpn_sqrtrem{1,2}

[Adrien Prost-Boucle]

Hi,

> I'll be grateful if you run your measures again,
> in particular for 100 and 128 bits.

I pulled the latest changes (hg rev 17327) and launched my tests again.
I cleaned up the values ad numbers of bits, just so it's a bit cleaner.

Reminder: I compiled GMP with functions mpn_sqrtrem{1,2} declared as
extern, and I preload my version in a shared lib to do the tests.
I used the floating-point version because it's the fastest one.


Laptop Core 2 Duo 2GHz

The tests are repeated 100000000x (100 million times)
Time is in seconds

1024 bits   time 74.93 -> 75.05   speedup 0.998
 512 bits   time 41.63
-> 37.33   speedup 1.12
 256 bits   time 19.93 -> 16.66   speedup 1.20
 1
92 bits   time 22.20 -> 19.36   speedup 1.15
 128 bits   time  8.43
->  5.65   speedup 1.49
  96 bits   time  9.29 ->  6.27   speedup 1.48
 
64 bits   time  4.65 ->  3.66   speedup 1.27

PC i7-4790 3.60GHz

1024 bits   time 25.55 -> 24.52   speedup 1.04
 512 bits   time 13.40 -> 12.64   speedup 1.06
 256 bits   time  6.09 ->  5.16   speedup 1.18
 192 bits   time  6.96 ->  6.21   speedup 1.12
 128 bits   time  2.42 ->  1.41   speedup 1.72
  96 bits   time  3.16 ->  1.89   speedup 1.67
  64 bits   time  1.06 ->  0.93   speedup 1.14


> Now, I believe he will be able to gain another 2x improving sqrtrem2,
> I did not touch that core functions, only the wrappers !-)

Not 2x, but the potential speedup is much higher indeed.

Adrien