Re: (Modular ^) vs. (^ then mod)

[Pedro Fortuny Ayuso <fortunypedro@uniovi.es>]

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