This page contains the description of the following commands gcd, generator_modp, gensym, get, get_bep, getcoef, getdef, getenv, getfn, getfn1, gethash, getprop, get_theta, get_val, go, go-on,
The pgcd function returns the greatest common divider of its two of arguments. The gcd function computes the gcd of its arguments (result is 0 if no argument given). The lcm function returns the least common multiple: it is the product of the arguments divided by the gcd.
[Endymion] (pgcd 30 100) 10 [Endymion] (gcd -30 100 0 25) 5 [Endymion] (lcm 10 -25) -50 [Endymion] (gcd 1/2) pgcd : not a number : 1/2
The generator_modp function returns a generator of the multiplicative group modulo n. An error is signalled in the case the argument is not an integer; nil is returned if the group is not cyclic. The group is cyclic if n is a power of an odd prime, or twice the power of an odd prime, or two or four. Details about the algorithm can be found in here.
If a is a generator, then any other generator is a power of a (by construction) and of the form a power q, where q is coprime to (Euler_phi n). The testp function shown below returns true if a is a generator mod n, the allg function returns all generators given one of them. Functions that follow are a possible implementation of generator_modp.
(defun testp (a n)
(let ((f (Euler_phi n)) res (b 1))
(for (i 1 1 f)
(setq b (remainder (* a b) n))
(unless (member b res) (setq res (cons b res))))
(eq (length res) f)))
(defun allg (a n)
(let ((f (Euler_phi n)) res (b 1))
(for (i 1 1 f)
(setq b (remainder (* a b) n))
(when (eq 1 (gcd i f))
(setq res (cons b res))))
(sort2 res)))
(defun generator_modp (n)
(cond ((eq n 2) 1)
((eq n 4) 3)
(true (generator1 (ifactor n)))))
(defun generator1 (s)
(let ((c 0) e n gen)
(cond ((null s) ) ; no factor
((null (cdr s)) (setq c 1)) ; one factor
((null (cddr s)) ; two factors
(if (and (eq (caar s) 2) (eq (cadar s) 1))
(setq c 2 s (cdr s)))))
(if (eq c 0)
()
(setq n (caar s) e (cadar s))
(if (eq n 2)
()
(setq gen (generator2 n (ifactor (- n 1))))
(if (and (neq e 1) (eq 1 (powermod gen (- n 1) (* n n))))
(setq gen (+ gen n)))
(if (and (eq c 2) (even? gen))
(setq gen (+ gen (** n e))))
gen))))
(defun found_gen ()
(let ((res true))
(for (i 0 1 (- Ln 1))
(unless (car (vref Lv i)) (setq res ())))
res))
(defun check_next (prime n)
(for (i 0 1 (- Ln 1))
(unless (car (vref Lv i))
(let ((p (cadr (vref Lv i))) (k (caddr (vref Lv i))) q r b)
(setq q (/ (- n 1) (** p k))
r (** p (- k 1))
b (powermod prime q n))
(when (neq 1 (powermod b r n))
(rplaca (vref Lv i) true)
(setq Lgen (remainder (* Lgen b) n)))))))
(defun generator2 (n L)
(let (Ln Lv Lgen)
(setq Ln (length L))
(setq Lv (makevector Ln 0))
(for (i 0 1 (- Ln 1))
(vset Lv i (cons () (nth i L))))
(setq Lgen 1)
(setq prime 2)
(while (not (found_gen))
(check_next prime n)
(setq prime (nextprime prime)))
Lgen))
Example
[Endymion] (setq res ()) () [Endymion] (for (i 2 1 100) (setq a (generator_modp i)) [Endymion] (newl res a) [Endymion] (when a (unless (testp a i) (error 'bad a i)))) () [Endymion] res (() () 3 10 () () 43 () () () () 38 () () 61 () () 79 11 2 () 29 () () () () 15 5 () 13 () () () 44 () () () () 43 17 () 55 47 () () () 29 3 () () 27 3 () 43 19 () () 18 () 11 () () 15 15 () () 3 () () 12 () 18 () 2 11 2 () 19 7 () () 15 11 3 () () 3 11 () 7 7 2 () 3 5 2 3 2 1)
The gensym function takes no argument; it returns a new uninterned symbol. This name is formed by the letter 'g' followed by an integer. Example
[Endymion] (gensym) g1 [Endymion] (setq x (gensym)) g2 [Endymion] (eq x 'g2) () [Endymion] (type-of x) symbol [Endymion] (set x 12) 12 [Endymion] x g2 [Endymion] (eval x) 12
The get function is a an alias for getprop. It takes two arguments. The first one has to be a symbol. It returns the value associated to the key on the property list of the symbol (or nil, if there is none). For an example, see putprop.
The gethash function returns the hashcode of an object. This some small integer that is more or less randomly selected. For instance, in the case where the argument is a symbol or a a string, this is 513 plus (hash x).
[Endymion] (gethash 'foo) 892 [Endymion] (gethash '(foo)) 29892 [Endymion] (gethash '(foo #[foo])) 29968 [Endymion] (gethash '(foo #[bar])) 29617 [Endymion] (gethash '(foo #[bar 1.2 "aa" 1/3])) 30246 [Endymion] (gethash #[1 2 3]) 20607 [Endymion] (gethash #:foo:#[1 2 3]) 22035
This returns the coefficient of x^i in the polynomial f, it works also for non-polynomials.
The getdef function takes one argument, that should be a function name. An error may be signaled if this is not the case. If the symbol corresponds to an undefined function, the return value is nil. If this is a user defined function, the value is a list, starting with defun or dmd, that can be used to define the function. If it is a compiled function, the result is a list of four items. The first is ds, the second is the name of the symbol, it is followed by the type of the function (a number), and the address (a number).
[Endymion] (getdef 'version) (ds version 1 134914352) [Endymion] (getdef 'car) (ds car 2 134778048) [Endymion] (getdef 'symbol) (ds symbol 3 134922784) [Endymion] (getdef 'vset) (ds vset 4 134793216) [Endymion] (getdef 'mset) (ds mset 5 134537152) [Endymion] (getdef 'end) (ds end 6 134725392) [Endymion] (getdef 'typevector) (ds typevector 7 134793584) [Endymion] (getdef 'getfn) (ds getfn 8 134925376) [Endymion] (getdef 'fillvector) (ds fillvector 9 134800416) [Endymion] (getdef 'list) (ds list 10 134778496) [Endymion] (getdef 'if) (ds if 11 134719888) [Endymion] (getdef 'ifn) (ds ifn 12 134728928) [Endymion] (dmd mymac (a b) c) mymac [Endymion] (getdef 'mymac) (dmd mymac (a b) c) [Endymion] (defun myfct (A B) C) myfct [Endymion] (getdef 'myfct) (defun myfct (A B) C) [Endymion] (getdef (gensym)) () [Endymion] (getdef 123) getdef : not a symbol : 123
The getenv function takes as argument a string (or anything that can be converted to a string). It returns the value of the shell environment of that name. It returns nil if this is not possible.
[Endymion] (getenv 'HOME) /user/grimm/home [Endymion] (getenv "HOME") /user/grimm/home [Endymion] (getenv "does-not-exist") ()
The findfn function takes two or three arguments, a package, a name, and an end-marker. It returns nil, if the name is not a symbol, or if the package is not a symbol. Otherwise, it considers the symbol with name name in the package p where p is pack, or its packagecell, or the packagecell of its packagecell, etc. For instance, if the name argument is foo, the package is #:a:b:c:d, then #:a:b:c:d:foo, #:a:b:c:d:foo, #:a:b:c:foo, #:a:b:foo, #:a:foo, and foo are considered. If a third argument is given, it indicates the first package to ignore. For instance, if it is a, then neither #:a:foo nor foo are considered. If the third argument is the same as the first, nothing is considered. If any symbol considered is a function, it will be returned. If nothing is found, then nil is returned. The function could be defined as follows
(defun getfn (pack fn . c)
(if c (setq c (car c)) (setq c 0))
(let ((res ()) (ok ()) z)
(until ok
(if (eq pack c)
(setq ok true)
(setq z (symbol pack fn))
(if (getdef z)
(setq ok true res z)
(if (null pack)
(setq ok true)
(setq pack (packagecell pack))))))
res))
Example
[Endymion] (defun foo ()) foo [Endymion] (defun #:bar:foo ()) #:bar:foo [Endymion] (defun #:bar:gee:buz:foo ()) #:bar:gee:buz:foo [Endymion] (getfn '#:bar:gee:buz 'foo) #:bar:gee:buz:foo [Endymion] (getfn '#:bar:gee 'foo) #:bar:foo [Endymion] (getfn '#:bar 'foo) #:bar:foo [Endymion] (getfn () 'foo) foo [Endymion] (getfn '#:potop:teraz 'foo) foo [Endymion] (getfn '#:bar:gee 'foo ()) #:bar:foo [Endymion] (getfn '#:bar 'foo ()) #:bar:foo [Endymion] (getfn '#:gee 'foo ()) () [Endymion] (getfn '#:bar:gee:buz 'foo 'bar) #:bar:gee:buz:foo [Endymion] (getfn '#:bar:gee 'foo 'bar) () [Endymion] (getfn 1 2 3 4) getfn : wrong number of arguments : 4 this should be at most 3 [Endymion] (getfn 1) getfn : wrong number of arguments : 1 this should be at least 2
The getfn1 function takes two arguments, which are symbols. It construct a symbol like symbol, but only if that symbol exists and is a function; it returns nil otherwise. If any of the argument is not a symbol, nil is also returned. The function could be defined as follows
(defun getfn1 (pack fn)
(if (not (symbolp pack))
()
(if (not (symbolp fn))
()
(let ((z (symbol pack fn)))
(if (getdef z)
z
())))))
Example
[Endymion] (defun #:foo:bar1()) #:foo:bar1 [Endymion] (defun #:foo:bar2 (x) x) #:foo:bar2 [Endymion] (getfn1 'foo 'bar1) #:foo:bar1 [Endymion] (getfn1 'foo 'bar2) #:foo:bar2 [Endymion] (getfn1 'foo 'bar3) () [Endymion] (getfn1 "foo" 'bar1) () [Endymion] (getfn1 'foo "bar1") ()
The getprop function takes two arguments. The first one has to be a symbol. It returns the value associated to the key on the property list of the symbol (or nil, if there is none). For an example, see putprop.
The go special form takes one argument. In can be used only inside a tagbody. The argument has to be a valid tag, defined by the tagbody. The example shown here do not work.
[Endymion] (go) go : wrong number of arguments : 0 this should be 1 [Endymion] (go foo) go : undefined escape : foo
If you say (go-on), this interrupts everything, and starts the symbolic evaluator.
back to home page
© INRIA 2005, 2006
Last modified $Date: 2008/09/04 08:48:33 $