Re: znlog() behavior

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* Bill Allombert [2011-07-24 00:11]:
> On Wed, Jul 20, 2011 at 03:31:53PM +0200, Max Alekseyev wrote:
> > And here is another bug, isn't it?
> > 
> > ? znlog(6,Mod(2,7),znorder(Mod(2,7)))
> > %2 = 1
> 
> Sort of. (The code actually returns 3\2, see the attached patch which fix this issue).
> The problem is that there is no interfaces for reporting "no solution".

I have implemented one in current svn: return the "impossible value" []
if there are no solution (same convention as in bestappr(), for instance).

> For example:
> ? znlog(2,Mod(4,17),znorder(Mod(4,17)))
>   ***   at top-level: znlog(2,Mod(4,17),zn
>   ***                 ^--------------------
>   *** znlog: gen_Shanks_log: supplied order (= 2) is incorrect.
> 
> but the supplied order is actually correct.
> Maybe we should just do pari_err(consister,"gen_Shanks_log") instead.

(23:45) gp >  znlog(2,Mod(4,17),znorder(Mod(4,17)))
%1 = []

On Wed, Jul 20, 2011 at 09:17:15PM +0200, Karim Belabas wrote:
> * Max Alekseyev [2011-07-20 20:57]:
> > Yet another problematic input:
> >
> > ? znlog(3,Mod(3,8),znorder(Mod(3,8)))
> >   ***   at top-level: znlog(3,Mod(3,8),zno
> >   ***                 ^--------------------
> >   *** znlog: not a primitive root in znlog.
> >   ***   Break loop: type 'break' to go back to GP
> >
> > I would expect it to simply return 1.
>
> This one is a bug. Ackowledged :-)

And also fixed in svn:

(23:45) gp > znlog(3,Mod(3,8),znorder(Mod(3,8)))
%1 = 1

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.

Keep testing, thanks for your feedback !

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

--513BC72376.1311544376/smail.math.u-bordeaux1.fr--