Magma and Pari

[john@maths.usyd.edu.au (John Cannon)]

I couldnt answer this letter when it first appeared. I would now like
to make a couple of points.

>>> from a posting on sci.math:
>>> 
>>> p = 2^29440 - 2^27392 + 1 b = 2^32 k = (p-1)/2^10
>>> 
>>> I did Mod(b,p)^k in gp
>>> 
>>> it took 20 min on Linux 450MHz PC.
>>> 
>>> However, from a follow-up to the same posting, Magma only takes 8 min (
>>> not clear on what platform, but I'm certain it's as fast or slower than
>>> my machine ).
>>> 
>>> So, I am wondering, if there's still room for improvement, because I
>>> believe Pari should be able to beat Magma in speed.
>
>I would disagree with this last comment. The Magma team started from PARI a
>long time ago, then spent quite a lot of time implementing more efficient
>algorithms wherever they could. [ that's actually what you pay Magma for: so
>that they can pay their developpers... ]

There are two fundamental errors of fact in this statement. 

Firstly, Magma did NOT start from Pari. It, or more precisely its predecssor 
Cayley, existed long before Pari appeared. The integer arithmetic in Magma 
has no relation to that in Pari and never has. There have been several
geenrations, the current of which was developed in Sydney from scratch 
by Allan Steel of the Magma group.

In 1993 H Cohen generously offered the Magma team the right to include
functionality from Pari within Magma. The following modules were imported:

  Real arithmetic + all the associated real and complex functions

  Power series. But these have been replaced by our own much faster code 
  about two years ago.

  p-adics. These have been replaced by our own code about six months ago.  
  In fact the Magma implmentation supports p-adics and finite degree 
  extensions of p-adics (general completions of local fields).

  Quadratic fields (including quadratic forms). In the process of being 
  replaced by native Magma code.

Only in the case of real arithmetic do we run code that is basically the
same as that in Pari. The other three modules were coded from scratch
by the Magma group using the Pari algorithms.

That is what was imported into Magma and we are very grateful for the
generosity of the H Cohen and the Pari group. However, the Magma integer 
arithmetic, polynomial arithmetic, linear algebra,  lattice theory,
elliptic curves, ...  were all written in Sydney and owe nothing whatsoever
to similar modules in Pari.  Magma has always used the KANT package 
for general number fields.

I find the implication that the Magma group would be unable to write 
fast code without it being derived from Pari to be derogatory to the 
members of the Magma group.

The second error in this statement concerns the statement that 

>>long time ago, then spent quite a lot of time implementing more efficient
>algorithms wherever they could. [ that's actually what you pay Magma for: so
>that they can pay their developpers... ]

The implementation of almost all modules in Magma is paid for by 
research grants. The licence charge covers the costs of maintaining
and distributing Magma. To get research grants we have to show that
research funds wont be spent on such support activities. The one
correct part of this statement is that we *do* spend a lot of time
devising fast algorithms and fast implmentations.

>Anyway, I can certainly improve (a bit) Karatsuba multiplication in PARI
>(unrolling the last recursive steps), but not that much. FFT multiplication
>should not be useful in this range. [ btw. does Magma include
>Schoenage-Strassen (I would tend to believe so) ? ]

It does so but it was not relevant in this problem since it cuts in
around 10,000 decimal digits. 

The Magma edge in this example mainly came from using a Karatsuba-type
division algorithm.

I would be very interested to hear of Pari timings for the larger
(100003-bit) Marsaglia exmple. Here the Magma FFT really pays off.

John Cannon