John Cannon on Sun, 12 Mar 2000 15:35:37 +1100 (EST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Magma and Pari |
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