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.
> 

I installed version 2.7.2 and the behavious is as you state. Also
the FpM_powu works like a charm.

Thanks a lot!


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