Pedro Fortuny Ayuso on Thu, 13 Nov 2014 15:29:49 +0100

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

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