Re: Some wishlist feature suggestions

[Phil Carmody <thefatphil@yahoo.co.uk>]

--- Bill Allombert <allomber@math.u-bordeaux.fr> wrote:
> 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?
> for(i=1,N,if(gcd(i,N)==1,....))
> or do you have a better algorithm in mind ?

Different techniques work best depending on the factorisation of N.
My main concern is when there are many small factors. In that situation 
a sieve/CRT could be used to reduce the work factor dramatically.

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

And for znorderis one would require 
  T(x,n,p)=x^n=1 && x^(n/p)!=1
where x is given, and thus the same for each p | n-1.
I see quite a lot of overlap personally.

> > 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
> explain.
> 
> 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.

OK, that doesn't sound too frightening, certainly easier than 
what forcoprime seemed to entail.

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

That would certainly work, the default being eulerphi of the 2nd 
component to the Mod (presumably that's what order()'s current 
"o=phi((GEN) x[1]);" represents). I assume that decomp() returns 
the factorisation of its parameter as some kind of matrix. 
In which case, it should be a simple alteration to order(), once
I work out how optional parameters work. The only optional parameters 
I can find are flags, not GENs; I don't know if that matters.


Phil

=====
When inserting a CD, hold down shift to stop the AutoRun feature
In the Device Manager, disable the SbcpHid device.
http://www.cs.princeton.edu/~jhalderm/cd3/

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com