source: CGBLisp/trunk/src/coefficient-ring.lisp@ 14

;;; -*- Mode: Lisp; Syntax: Common-Lisp; Package: Grobner; Base: 10 -*-
#|
        $Id: coefficient-ring.lisp,v 1.4 2009/01/22 03:59:21 marek Exp $
  *--------------------------------------------------------------------------*
  |  Copyright (C) 1994, Marek Rychlik (e-mail: rychlik@math.arizona.edu)    |
  |    Department of Mathematics, University of Arizona, Tucson, AZ 85721    |
  |                                                                          |
  | Everyone is permitted to copy, distribute and modify the code in this    |
  | directory, as long as this copyright note is preserved verbatim.         |
  *--------------------------------------------------------------------------*
|#

(defpackage "COEFFICIENT-RING"
  (:export ring
           ring-+
           ring--
           ring-*
           ring-/
           ring-gcd
           ring-lcm
           ring-signum
           ring-zerop
           ring-unit
           ring-length
           ring-numerator
           ring-denominator
           make-ring
           *coefficient-ring*
           *ring-of-integers*
           *field-of-rationals*
           field-modulo-prime
           )
  (:use "MODULAR" "COMMON-LISP"))
    
(in-package "COEFFICIENT-RING")

(proclaim '(optimize (speed 0) (debug 3)))

(defstruct ring
  "The structure whose slots are bound to functions
performing usual ring operations. In addition to usual arithmetical
operations, bindings for other common operations
which increase efficiency of Grobner basis calculations are also
included. They are as follows:
        GCD     - greatest common divisor;
        LCM     - least common multiple;
        ZEROP   - test whether an element is zero;
        SIGNUM  - the sign of a ring element (+1, -1 or zero);
        UNIT    - the unit of the ring;
        NUMERATOR - the numerator, if a ring of fractions
        DENOMINATOR - the denominator, if a ring of fractions
        LENGTH  - an integer giving the approximate length
                of the representation; for example, for integers
                its default binding is #'integer-length;
"
  + - * / gcd lcm zerop unit length signum numerator denominator)

(defvar *ring-of-integers*
  (make-ring :+ #'+
             :- #'-
             :* #'*
             :/ #'floor
             :gcd #'gcd
             :lcm #'lcm
             :zerop #'zerop
             :signum #'signum
             :unit 1
             :length #'integer-length
             :numerator #'numerator
             :denominator #'denominator)
  "Operations in the ring of integers.")

(defvar *field-of-rationals*
  (make-ring
   :+ #'+
   :- #'-
   :* #'*
   :/ #'/
   :gcd #'(lambda (&rest r) (declare (ignore r)) 1)
   :lcm #'(lambda (&rest r) (apply #'* r))
   :zerop #'zerop
   :signum #'signum
   :unit 1
   :length #'(lambda (x) (+ (integer-length (numerator x))
                            (integer-length (denominator x))))
   :numerator #'numerator
   :denominator #'denominator)
  "Operations on the field of rational numbers.")

(defun field-modulo-prime (modulus)
  "Return a RING structure with operations bound
to the arithmetical operations modulo MODULUS, which
should be a prime."
  (make-ring
   :+ #'(lambda (&rest r) (mod (apply #'+ r) modulus))
   :- #'(lambda (&rest r) (mod (apply #'- r) modulus))
   :* #'(lambda (&rest r) (mod (apply #'* r) modulus))
   :/ (make-modular-division modulus)
   :gcd #'(lambda (&rest r) (declare (ignore r)) 1)
   :lcm #'(lambda (&rest r) (mod (apply #'* r) modulus))
   :zerop #'zerop
   :signum #'(lambda (x) (if (zerop x) 0 1))
   :unit 1
   :length #'(lambda (x) (declare (ignore x)) 1)
   :numerator #'identity
   :denominator #'(lambda (x) (declare (ignore x)) 1)))


(defvar *coefficient-ring* *ring-of-integers*
  "The default RING structure, used in most operations
on the coefficients of polynomials. It should be carefully
set if rings other than the default ring is used.")