Bill Allombert on Sat, 02 Oct 2004 17:10:20 +0200

 Fast sqrt with the GMP kernel.

```Hello PARI-dev,

I have a commited a patch that implement a faster sqrt routine
for real numbers when using the GMP kernel.

Here the results with the test-suite below:
(on the pari machine (athlon MP 1800+))

Here the time in ms with the GMP kernel:

prec  | old  | new  | without GMP.
------+------+--------------------
19    | 2,180| 2,010| 2,320
28    | 2,290| 2,180| 2,440
1000  | 9,210| 3,940| 9,180
10000 | 4,760| 1,340|10,080
30000 | 1,880| 0,750| 6,110
100000| 1,400| 0,500| 7,830

For some reason I had to round up at HIGHBIT-1 instead of
HIGHBIT to match the behaviour of the portable kernel. Any idea
about fixing the portable kernel welcome.

The variant with a single word of extra accuracy appears to be slower
for small precision. Apparenlty GMP mpn_sqrtrem prefer even-sized
operands (which is not really surprising):

19    |2,250|
28    |2,490|
1000  |4,050|
10000 |1,360|
30000 |0,760|
100000|0,500|

What should be done now, is to add a tuning switch for log to use logagm
for large operand. Both  glog and constlog2 are slower than logagm for
large operand when the square root is fast enough.

Cheers,
Bill

\p19
V=vector(1000,i,random(10^19)*1.);
for(j=1,1000,for(i=1,1000,sqrt(V[i])));
##
\p28
V=vector(1000,i,random(10^28)*1.);
for(j=1,1000,for(i=1,1000,sqrt(V[i])));
##
\p1000
V=vector(1000,i,random(10^1000)*1.);
for(j=1,100,for(i=1,1000,sqrt(V[i])));
##
\p10000
V=vector(100,i,random(10^10000)*1.);
for(j=1,10,for(i=1,100,sqrt(V[i])));
##
\p30000
V=vector(10,i,random(10^30000)*1.);
for(j=1,10,for(i=1,10,sqrt(V[i])));
##
\p100000
V=vector(10,i,random(10^100000)*1.);
for(j=1,1,for(i=1,10,sqrt(V[i])));
##

```