Karim BELABAS on Mon, 10 Jan 2000 16:42:02 +0100 (MET) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: alarming inefficiency ( modular arithmetic ) |
[Igor:] >> 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... ] Some functions at the user level may be hard to use efficiently, but I don't believe PARI can beat the internal library functions (or maybe for a little while, until they figure out what trick they forgot to implement...). [Bill:] > I have just tested Igor's example on a bi-Pentium III at 600MHz > and the result is: > GP: 14 minutes > MAGMA: 6 minutes According to gprof: 72% of the time is spent computing remainders mod p 26% of the time is spent squaring integers (roughly log_2 (k) of them) which seems very hard to believe since squaring uses Karatsuba and division is the naive one !!! 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) ? ] As for the successive remainders, preconditioning on p [i.e computing invp = 1./p to a sufficient accuracy, then u mod p as u - trunc(invp*u)*p], should noticeably improve matters. For this particular p, I gain a factor 10 for an individual division (quick GP test). And roughly another factor 2 by switching on Karatsuba for real numbers (disabled by default). All in all, I can expect to make this whole computation about 4 times faster, (which probably means that Magma doesn't precondition on p...). More if I don't really believe in what gprof told me. I'll put a note in the TODO list (or do it altogether if I can find the time for it). 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://hasse.mathematik.tu-muenchen.de/ntsw/pari/