Re: some PARI kernel oddities/remarks

[Bill Allombert <allomber@math.u-bordeaux.fr>]

On Mon, Jan 12, 2004 at 11:37:41PM +0100, Bill Allombert wrote:
> Hello PARI-dev,
> 
> While trying to understand why Flx_sqr was so slow,
> I found some oddities in the kernel:
> 
> I suppose I will test NTL with my benchmark to start with.

Well here are the results:
[The host is much faster/reliable than  the previous one used]
NTL was compiled with GMP as multiprecision package.
NTL version 5.3.1
GMP version 4.1.2
PARI version 2.1.8 CVS
GCC 2.95.4 Debian
(I use pari-ntl interface to use NTL under GP)

i       : NTL  |Flx_sqr|  sqri |  GMP sqri
1       : 300  | 40    |  30   |  30
2       : 170  | 20    |  10   |  10
3       : 90   | 20    |  10   |  10
4       : 60   | 30    |  10   |  0
5       : 50   | 40    |  10   |  10
6       : 40   | 50    |  20   |  20
7       : 50   | 80    |  30   |  20
8       : 80   | 130   |  40   |  30
9       : 110  | 210   |  60   |  40
10      : 160  | 310   |  90   |  60
11      : 170  | 470   |  130  |  90
12      : 190  | 700   |  210  |  110
13      : 210  | 1080  |  310  |  120
14      : 310  | 1630  |  480  |  160
15      : 360  | 2440  |  750  |  170
16      : 1000 | 3720  |  1140 |  210

The NTL result  for i=1...3 are probably due to the overhead to convert
PARI vecsmall to NTL lzz_pX objects, hence are not significants.

NTL is much slower than GMP sqri here. It is much faster than PARI Flx_sqr
and became faster than PARI sqri for large degree, but it use asymptotically 
faster algorithms than Karatsuba.

In fact, even using evaluation in 2^64 instead of 2^32, GMP should be
twice faster than NTL.

Bill.