Bill Allombert on Wed, 2 Apr 2003 23:25:28 +0200

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

Re: group identification patch

On Wed, Apr 02, 2003 at 12:52:38PM -0800, Ilya Zakharevich wrote:
> On Wed, Apr 02, 2003 at 03:05:49PM +0200, Bill Allombert wrote:
> > Hello PARI-dev,
> > 
> > Here a (large) patch that add a feature similar to GAP IdGroup
> > function for weakly super-solvable group.
> > +GEN
> > +groupelts_center(GEN S)
> > +{
> This looks like a part of a very sad story.  It looks like different
> (complicated) algorithms used for implementation of particular PARI
> functions have tons of small C helper functions.  Some of these helper
> functions have a signature good for importing to PARI.  Some of these
> helper functions provide algorithms of general interest (I remember
> seeing something like a knapsack algo etc., now some algorithms for
> group manipulation).
> But all these goodies are sitting there undocumented - and as a
> consequence, unused!  Should not we keep a list of "semi-supported"
> importable toolbox-functions in PARI core?

Having small C helper function is a major win in design compared to the
old monolithic design. This is not a loss.

The point of the description system is to be able to document functions
that are not GP function, and to be able to just do install(func)
without guessing the prototype.

I thing we should go ahead and use it. It is a zero-code patch.
It will require a huge effort to document all the PARI function
we find interesting, but then better start now!

A different point is to have a naming policy for PARI functions
that help to find them.

It seems we have standardised on
<argument types>_<what it does>

(with some unfortunate exception like polcyclo and matcompanion.

I have even wrote a file sometime ago:

This file describe the naming scheme for functions
performing modular computation in PARI.

Here the decription using yacc syntax:

function_name: type exponent '_' func 
             | type exponent '_' function_name

type: basering | type letters;

basering: Fp | Fq | Z | Q;

       | letters X /*polynomial*/
       | letters M /*matrix*/
       | letters V /*vector*/
       | letters Q /*quotient by a polynomial, add a new modulus*/
exponent: /*empty*/

func : add /*add*/
     | sub /*substract*/
     | mul /*multiply*/
     | divres
     | div /*divide*/
     | res /*lift*/
     | pow /*power*/
     | compo /*composition*/
     | etc.../*et caetera...*/

Func: Each func has its own argument spec, for nonmoduli args:

add:x,y -> x+y;/*commute*/
sub:x,y -> x-y;
mul:x,y -> x*y;/*commute*/
div:x,y -> euclidean quotient of x by y; 
res:x,y -> euclidean residue of x by y;
divres: x,y,*z -> as div but set z to res(x,y);
If all args of func have the same type, with same moduli, only one is needed and should have empty exponent, else all args must have a type and and exponent so that consecutive types are disctinct.  
If two types correspond to commuting args, they must be sorted by decreasing lexicographic order.

Arguments passing:

Argument are passed in order:
first arg of func, then moduli in the same order than in function_name.
One modulus for the first Fp, one for the first Fq, and one for each Q letter. 



compute P^n mod (p,T) where P is a polynomial.
(formerly Fp_pow_mod_pol)

GEN FpX_Fp_add(GEN P,GEN x, GEN p);

 add the scalar x to the polynomial P
(formerly  Fp_add_pol_scal)


compute P(Q) mod (T,p)

GEN FpX_divres(GEN x,GEN y,GEN *z,GEN p)