Karim Belabas on Tue, 26 Jul 2011 15:34:46 +0200


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

Re: znlog() behavior


* Karim Belabas [2011-07-25 00:22]:
> I rewrote the function so that it no longer assumes that the group is
> cyclic ( I also removed a number of "not absolutely necessary"
> assumptions ). This also reduced the number of "undefined behaviour"
> cases.
> 
> This has a price, but only in very simple situations:
> (23:50) gp >  for(i=1,10^6,znlog(2,Mod(2,3)))  \\ BEFORE
> time = 248 ms
> (23:50) gp >  for(i=1,10^6,znlog(2,Mod(2,3)))  \\ AFTER
> time = 1,120 ms.
> 
> (23:50) gp >  for(i=1,10^6,znlog(10,Mod(2,101)))  \\ BEFORE
> time = 3,628 ms.
> 
> (23:50) gp >  for(i=1,10^6,znlog(10,Mod(2,101)))  \\ AFTER
> time = 2,416 ms.
> 
> So znlog() is about 50% slower for very simple (non trivial) queries. I'll try
> to improve on this.

More accurately, there is no penalty if the order is explicitly 
-- and correctly! -- indicated:

  (15:32) gp >  for(i=1,10^6,znlog(2,Mod(2,3)))
   time = 1,088 ms.
  (15:32) gp >  for(i=1,10^6,znlog(2,Mod(2,3), 2))
  time = 196 ms.

  (15:32) gp > for(i=1,10^6,znlog(10,Mod(2,101)))
  time = 3,657 ms.
  (15:32) gp > znorder(Mod(2,101))
  %1 = 100
  (15:32) gp > for(i=1,10^6,znlog(10,Mod(2,101),100))
  time = 2,252 ms.

A minor problem remains, it is sometimes more efficient to compute the order
yourself than to let the function sort it out:

  (15:32) gp > for(i=1,10^6,znlog(10,Mod(2,101),znorder(Mod(2,101))))
  time = 3,280 ms.

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`