Re: alarming inefficiency ( modular arithmetic )

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

[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/