Pedro Fortuny Ayuso on Thu, 13 Nov 2014 16:23:38 +0100

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

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

• To: pari-users@pari.math.u-bordeaux.fr
• Subject: Re: (Modular ^) vs. (^ then mod)
• From: Pedro Fortuny Ayuso <fortunypedro@uniovi.es>
• Date: Thu, 13 Nov 2014 16:23:19 +0100
• Delivery-date: Thu, 13 Nov 2014 16:23:38 +0100
• References: <20141113095028.GA495@MBP-pfortuny.local> <20141113102952.GB12828@yellowpig>
• User-agent: Mutt/1.5.20 (2009-06-14)

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