Pedro Fortuny Ayuso on Thu, 13 Nov 2014 11:48:31 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: (Modular ^) vs. (^ then mod) |
On Thu, Nov 13, 2014 at 11:29:52AM +0100, Bill Allombert wrote: > On Thu, Nov 13, 2014 at 10:50:28AM +0100, Pedro Fortuny Ayuso wrote: > > Hi, > > > > I am doing quite a few (millions) of modular powers and > > additions like shown below. Is it natural that the Mod > > operation takes longer than the operation without Mod? > > It may be as simple as "yes, pretty normal" but somehow > > I expected the operation with the Mods to be faster, > > but I may well be quite wrong. > > No it is not normal, and it does not happen on my machine. > What version of GP are you using (what \v says) ? > > With PARI/GP 2.7.2 (64bit) I get: > ? s=[0,0;0,0];for(a=0,n-1, for(b=0, n-1, for(c=0, n-1, s=s+[a,b;0,c]^n))) > ? ## > *** last result computed in 5,421 ms. > ? s=[0,0;0,0]; for(a=0,n-1, for(b=0, n-1, for(c=0, n-1, s=s+[Mod(a,n),Mod(b,n);0,Mod(c,n)]^n))) > ? ## > *** last result computed in 5,301 ms. > > If you really need to optimize this, you can use the internal FpM_powu > libpari function for powering of matrices over Z/nZ as follow > > install(FpM_powu,GLG) > n=120; > s=Mod([0,0;0,0],n);for(a=0,n-1, for(b=0, n-1, for(c=0, n-1, s=s+FpM_powu([a,b;0,c],n,n)))) > > which is about twice faster. > > (ideally, GP should call FpM_powu by itself, but it is not implemented yet). > > Cheers, > Bill. > Sorry I forgot to include the version etc... My computer is OS X Lion, MBPro early 2007 (yes, a bit oldish). ? \v GP/PARI CALCULATOR Version 2.5.3 (released) i386 running darwin (x86-64/GMP-6.0.0 kernel) 64-bit version compiled: Nov 11 2014, gcc-2.1 (tags/Apple/clang-163.7.1) (based on LLVM 3.0svn) (readline v6.3 enabled, extended help enabled) Thanks for the feedback. I shall look at the FPM_powu etc. and tell you about it. I shall also update to 2.7.2 as soon as possible, just in case. Thanks again, Pedro. -- Pedro Fortuny Ayuso http://pfortuny.net [ Dirección nueva: pedro@pfortuny.net ] [ Todas las anteriores siguen funcionando ] EPIG, Campus de Viesques, Gijon Dpto. de Matematicas Universidad de Oviedo