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

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

On Thu, Nov 13, 2014 at 01:35:29PM +0100, Karim Belabas wrote:
> * Bill Allombert [2014-11-13 11:30]:
> > 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
> 
> Of course, to optimize this precise expression, you might as well use
> the formula
> 
>   [a,b;0,c]^n = [a^n, b*(a^n-c^n)/(a-c); 0, c^n] if a != c
>                 [a^n, n*b*a^(n-1); 0, a^n]       if a = c
> 
> then simplify the resulting triple sum over a,b,c. For example, modulo n > 0,
> your sum is obviously [0,0;0,0]  :-)
> 
> Cheers,

Yes, I know, it was just a simplest of examplest. Thanks anyway,


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