Bill Allombert on Tue, 14 Dec 2004 17:38:26 +0100

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

Re: Some wishlist feature suggestions

On Tue, Dec 14, 2004 at 07:42:13AM -0800, Phil Carmody wrote:
> I've found myself coding long-hand the following constructs many times, and
> think that they'd be far better implemented as language constructs.
> 1) Instead of a plain for loop and a gcd call -
> forcoprime(n,X,seq): the sequence is evaluated, X running over values coprime
> to n.

How do you want to implement that?
or do you have a better algorithm in mind ?

> 2) Instead of an explicit evaluation of znorder(x) (very simple, but slow), 
> or similarly an evaluation of x^d for d=n/p for each non-composite p|n (fast,
> but several lines of code) - 
> znorderis(x,n): true(1) if the znorder(x) is n, false(0) if not.
> I'd love to implement them myself, but to be honest I had a look 
> at (1), to see if I could rip off the fordiv() code, or similar, 
> and I just got confused. I think the overlap with current code 
> should be pretty substantial.

> Similarly, I reckon that znorderis has an enormous overlap with 
> the Pocklington test code (because that's essentially most of what 
> a Pocklington test consists of).

Not really. For Pocklington-Lehmer-Selfridge test you only need
T(x,n,p)=x^n=1 && x^(n/p)!=1 

You need to find a suitable x for all p | n-1.

> Perhaps someone could give a masterclass in implementing new functions,
> so that those like myself on this list could become more constructive
> contributors rather than just test-monkeys.

Karim did it at the PARI/GP workshop. We should put the slide on the
PARI website.

Implementing 1) need knowledge of the parser internal so is difficult to

Implementing 2) is much easier.
You can first write it in GP and look at the C code generated by gp2c.

Secondly, run
make ctags etags
cd src
if you use vi enter vi -t znorder
if you use emacs, lauch emacs and enter M-. znorder.
That will jump to the code for the znorder function:
the C function 'order'.

Copy-paste this function and rename it orderis.
Change it to what you want by keeping an eye of the gp2c output:
Your new function need to take 2 parameter so you have to change the
prototype to GEN orderis(GEN x, GEN o).

If you want I can write a line-by-line explanation of the znorder code.

Add the prototype to src/headers/paridecl.h below the prototype of order
(line 326) to preserve alphabetic sorting.

Now copy src/functions/number_theoretical/znorder
to src/functions/number_theoretical/znorderis
and edit src/functions/number_theoretical/znorderis
to change the function name, the help, the C-name and the prototype.
A prototype of "GG" (the function take 2 GEN not 1). should do.

Rebuild. Now GP should include a znorderis function and ?znorderis
should display the help text.

For the case at hand: probably it would be better to add an optional
parameter to znorder (a multiple of the order) than adding a whole
new function.