Re: Magma and Pari

[Karim BELABAS <Karim.Belabas@math.u-psud.fr>]

> [I hastily wrote:]
>>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... ]

[John Cannon answered:]
> 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.

I'm sorry if it could be understood that way. I intended to state that the
original implication: "Magma can do it ==> PARI can do it faster"  wasn't
sensible. The part about borrowing code was meant to indicate that even if
parts of the original code were similar [I wasn't sure about the exact extent
of PARI code included in Magma, thanks for clearing out my inaccuracies
there], it would have been improved beyond recognition by the Magma team, and
so would be much faster than ours.

Convey my apologies to the rest of the Magma group, I didn't intend to
slighten their work in any way. On the contrary it was appreciative [ and so
was the other inaccuracy about paying developpers: I meant the license fee
actually covered a lot of work and not hype as in some other rival commercial
products ]

>> 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.

There's no FFT in Pari :-(, so I expect it'll be a disaster... I'll try it :-)

All the best,

  Karim.

__
Karim Belabas                    email: Karim.Belabas@math.u-psud.fr
Dep. de Mathematiques, Bat. 425
Universite Paris-Sud             Tel: (00 33) 1 69 15 57 48
F-91405 Orsay (France)           Fax: (00 33) 1 69 15 60 19
--
PARI/GP Home Page: http://www.parigp-home.de/