path: root/src/algebra/si.spad.pamphlet

\documentclass{article}
\usepackage{open-axiom}
\begin{document}
\title{\$SPAD/src/algebra si.spad}
\author{Stephen M. Watt, Michael Monagan, James Davenport, Barry Trager}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{category INS IntegerNumberSystem}
<<category INS IntegerNumberSystem>>=
)abbrev category INS IntegerNumberSystem
++ Author: Stephen M. Watt
++ Date Created:
++   January 1988
++ Change History:
++ Basic Operations:
++   addmod, base, bit?, copy, dec, even?, hash, inc, invmod, length, mask,
++   positiveRemainder, symmetricRemainder, multiplicativeValuation, mulmod,
++   odd?, powmod, random, rational, rational?, rationalIfCan, shift, submod
++ Description:  An \spad{IntegerNumberSystem} is a model for the integers.
IntegerNumberSystem(): Category ==
  Join(UniqueFactorizationDomain, EuclideanDomain, OrderedIntegralDomain,
         DifferentialRing, ConvertibleTo Integer, RetractableTo Integer,
           LinearlyExplicitRingOver Integer, ConvertibleTo InputForm,
             ConvertibleTo Pattern Integer, PatternMatchable Integer,
               CombinatorialFunctionCategory, RealConstant,
                 CharacteristicZero, StepThrough) with
   odd?     : % -> Boolean
      ++ odd?(n) returns true if and only if n is odd.
   even?    : % -> Boolean
      ++ even?(n) returns true if and only if n is even.
   multiplicativeValuation
      ++ euclideanSize(a*b) returns \spad{euclideanSize(a)*euclideanSize(b)}.
   base     : () -> %
      ++ base() returns the base for the operations of \spad{IntegerNumberSystem}.
   length   : % -> %
      ++ length(a) length of \spad{a} in digits.
   shift    : (%, %) -> %
      ++ shift(a,i) shift \spad{a} by i digits.
   bit?     : (%, %) -> Boolean
      ++ bit?(n,i) returns true if and only if i-th bit of n is a 1.
   positiveRemainder     : (%, %) -> %
      ++ positiveRemainder(a,b) (where \spad{b > 1}) yields r
      ++ where \spad{0 <= r < b} and \spad{r == a rem b}.
   symmetricRemainder     : (%, %) -> %
      ++ symmetricRemainder(a,b) (where \spad{b > 1}) yields r
      ++ where \spad{ -b/2 <= r < b/2 }.
   rational?: % -> Boolean
      ++ rational?(n) tests if n is a rational number
      ++ (see \spadtype{Fraction Integer}).
   rational : % -> Fraction Integer
      ++ rational(n) creates a rational number (see \spadtype{Fraction Integer})..
   rationalIfCan: % -> Union(Fraction Integer, "failed")
      ++ rationalIfCan(n) creates a rational number, or returns "failed" if this is not possible.
   random   : () -> %
      ++ random() creates a random element.
   random   : % -> %
      ++ random(a) creates a random element from 0 to \spad{a-1}.
   copy     : % -> %
      ++ copy(n) gives a copy of n.
   inc      : % -> %
      ++ inc(x) returns \spad{x + 1}.
   dec      : % -> %
      ++ dec(x) returns \spad{x - 1}.
   mask     : % -> %
      ++ mask(n) returns \spad{2**n-1} (an n bit mask).
   addmod   : (%,%,%) -> %
      ++ addmod(a,b,p), \spad{0<=a,b<p>1}, means \spad{a+b mod p}.
   submod   : (%,%,%) -> %
      ++ submod(a,b,p), \spad{0<=a,b<p>1}, means \spad{a-b mod p}.
   mulmod   : (%,%,%) -> %
      ++ mulmod(a,b,p), \spad{0<=a,b<p>1}, means \spad{a*b mod p}.
   powmod   : (%,%,%) -> %
      ++ powmod(a,b,p), \spad{0<=a,b<p>1}, means \spad{a**b mod p}.
   invmod   : (%,%) -> %
      ++ invmod(a,b), \spad{0<=a<b>1}, \spad{(a,b)=1} means \spad{1/a mod b}.
   canonicalUnitNormal
--   commutative("*")    -- follows from the above

 add
   characteristic == 0
   differentiate x          == 0
   even? x                  == not odd? x
   positive? x              == x > 0
   copy x                   == x
   bit?(x, i)               == odd? shift(x, -i)
   mask n                   == dec shift(1, n)
   rational? x              == true
   euclideanSize(x)         ==
        x=0 => error "euclideanSize called on zero"
        x<0 => (-convert(x)@Integer)::NonNegativeInteger
        convert(x)@Integer::NonNegativeInteger
   convert(x:%):Float       == (convert(x)@Integer)::Float
   convert(x:%):DoubleFloat  == (convert(x)@Integer)::DoubleFloat
   convert(x:%):InputForm   == convert(convert(x)@Integer)
   retract(x:%):Integer     == convert(x)@Integer
   convert(x:%):Pattern(Integer)== convert(x)@Integer ::Pattern(Integer)
   factor x          == factor(x)$IntegerFactorizationPackage(%)
   squareFree x      == squareFree(x)$IntegerFactorizationPackage(%)
   prime? x          == prime?(x)$IntegerPrimesPackage(%)
   factorial x       == factorial(x)$IntegerCombinatoricFunctions(%)
   binomial(n, m)    == binomial(n, m)$IntegerCombinatoricFunctions(%)
   permutation(n, m) == permutation(n,m)$IntegerCombinatoricFunctions(%)
   retractIfCan(x:%):Union(Integer, "failed") == convert(x)@Integer

   init() == 0

   -- iterates in order 0,1,-1,2,-2,3,-3,...
   nextItem(n) ==
     zero? n => 1
     n>0 => -n
     1-n

   patternMatch(x, p, l) ==
     patternMatch(x, p, l)$PatternMatchIntegerNumberSystem(%)

   rational(x:%):Fraction(Integer) ==
     (convert(x)@Integer)::Fraction(Integer)

   rationalIfCan(x:%):Union(Fraction Integer, "failed") ==
     (convert(x)@Integer)::Fraction(Integer)

   symmetricRemainder(x, n) ==
      r := x rem n
      r = 0 => r
      if n < 0 then n:=-n
      r > 0 =>
         2 * r > n => r - n
         r
      2*r + n <= 0 => r + n
      r

   invmod(a, b) ==
      if negative? a then a := positiveRemainder(a, b)
      c := a; c1:% := 1
      d := b; d1:% := 0
      while not zero? d repeat
         q := c quo d
         r := c-q*d
         r1 := c1-q*d1
         c := d; c1 := d1
         d := r; d1 := r1
      not one? c => error "inverse does not exist"
      negative? c1 => c1 + b
      c1

   powmod(x, n, p) ==
      if negative? x then x := positiveRemainder(x, p)
      zero? x => 0
      zero? n => 1
      y:% := 1
      z := x
      repeat
         if odd? n then y := mulmod(y, z, p)
         zero?(n := shift(n, -1)) => return y
         z := mulmod(z, z, p)

@

\section{domain SINT SingleInteger}

<<domain SINT SingleInteger>>=
)abbrev domain SINT SingleInteger

++ Author:  Michael Monagan
++ Date Created:
++    January 1988
++ Change History:
++ Basic Operations: max, min,
++    not, and, or, xor, Not, And, Or
++ Related Constructors:
++ Keywords: single integer
++ Description: SingleInteger is intended to support machine integer
++ arithmetic.

-- MAXINT, BASE (machine integer constants)
-- MODULUS, MULTIPLIER (random number generator constants)


-- Lisp dependencies
-- EQ, ABSVAL, TIMES, INTEGER-LENGTH, HASHEQ, 
-- QSLESSP, QSGREATERP, QSADD1, QSSUB1, QSMINUS, QSPLUS, QSDIFFERENCE
-- QSTIMES,, QSODDP, QSZEROP, QSMAX, QSMIN, QSNOT, QSAND
-- QSOR, QSXOR, QSLEFTSHIFT, QSADDMOD, QSDIFMOD, QSMULTMOD


SingleInteger(): Join(IntegerNumberSystem,OrderedFinite,BooleanLogic,Logic,OpenMath) with
   canonical
      ++ \spad{canonical} means that mathematical equality is implied by data structure equality.
   canonicalsClosed
      ++ \spad{canonicalClosed} means two positives multiply to give positive.
   noetherian
      ++ \spad{noetherian} all ideals are finitely generated (in fact principal).

   -- bit operations
   xor: (%, %) -> %
      ++ xor(n,m)  returns the bit-by-bit logical {\em xor} of
      ++ the single integers n and m.
   Not  : % -> %
      ++ Not(n) returns the bit-by-bit logical {\em not} of the single integer n.
   And  : (%,%) -> %
      ++ And(n,m)  returns the bit-by-bit logical {\em and} of
      ++ the single integers n and m.
   Or   : (%,%) -> %
      ++ Or(n,m)  returns the bit-by-bit logical {\em or} of
      ++ the single integers n and m.

 == SubDomain(Integer, SMINTP(#1)$Lisp) add

   import %icst0: %                 from Foreign Builtin
   import %icst1: %                 from Foreign Builtin
   import %iadd: (%,%) -> %         from Foreign Builtin
   import %isub: (%,%) -> %         from Foreign Builtin
   import %imul: (%,%) -> %         from Foreign Builtin
   import %irem: (%,%) -> %         from Foreign Builtin
   import %iquo: (%,%) -> %         from Foreign Builtin
   import %ineg: % -> %             from Foreign Builtin
   import %iabs: % -> %             from Foreign Builtin
   import %imax: (%,%) -> %         from Foreign Builtin
   import %imin: (%,%) -> %         from Foreign Builtin
   import %igcd: (%,%) -> %         from Foreign Builtin
   import %hash: % -> SingleInteger from Foreign Builtin
   import %iodd?: % -> Boolean      from Foreign Builtin
   import %ieq: (%,%) -> Boolean    from Foreign Builtin
   import %ilt: (%,%) -> Boolean    from Foreign Builtin
   import %ile: (%,%) -> Boolean    from Foreign Builtin
   import %igt: (%,%) -> Boolean    from Foreign Builtin
   import %ige: (%,%) -> Boolean    from Foreign Builtin

   seed : % := %icst1               -- for random()
   MAXINT ==> _$ShortMaximum$Lisp
   MININT ==> _$ShortMinimum$Lisp
   BASE ==> 67108864$Lisp           -- 2**26
   MULTIPLIER ==> 314159269$Lisp    -- from Knuth's table
   MODULUS ==> 2147483647$Lisp      -- 2**31-1

   writeOMSingleInt(dev: OpenMathDevice, x: %): Void ==
    if negative? x then
      OMputApp(dev)
      OMputSymbol(dev, "arith1", "unary_minus")
      OMputInteger(dev, convert(-x))
      OMputEndApp(dev)
    else
      OMputInteger(dev, convert(x))

   OMwrite(x: %): String ==
    s: String := ""
    sp := OM_-STRINGTOSTRINGPTR(s)$Lisp
    dev: OpenMathDevice := OMopenString(sp pretend String, OMencodingXML())
    OMputObject(dev)
    writeOMSingleInt(dev, x)
    OMputEndObject(dev)
    OMclose(dev)
    s := OM_-STRINGPTRTOSTRING(sp)$Lisp pretend String
    s

   OMwrite(x: %, wholeObj: Boolean): String ==
    s: String := ""
    sp := OM_-STRINGTOSTRINGPTR(s)$Lisp
    dev: OpenMathDevice := OMopenString(sp pretend String, OMencodingXML())
    if wholeObj then
      OMputObject(dev)
    writeOMSingleInt(dev, x)
    if wholeObj then
      OMputEndObject(dev)
    OMclose(dev)
    s := OM_-STRINGPTRTOSTRING(sp)$Lisp pretend String
    s

   OMwrite(dev: OpenMathDevice, x: %): Void ==
    OMputObject(dev)
    writeOMSingleInt(dev, x)
    OMputEndObject(dev)

   OMwrite(dev: OpenMathDevice, x: %, wholeObj: Boolean): Void ==
    if wholeObj then
      OMputObject(dev)
    writeOMSingleInt(dev, x)
    if wholeObj then
      OMputEndObject(dev)

   reducedSystem(m: Matrix %) == m pretend Matrix(Integer)
   coerce(x):OutputForm == rep(x)::OutputForm
   convert(x:%):Integer == rep x
   i:Integer * y:%      == %imul(i::%,y)
   0         == %icst0
   1         == %icst1
   base()    == per 2
   max()     == MAXINT
   min()     == MININT
   x = y     == %ieq(x,y)
   ~ x       == LOGNOT(x)$Lisp
   not(x)    == LOGNOT(x)$Lisp
   x /\ y    == LOGAND(x,y)$Lisp
   x \/ y    == LOGIOR(x,y)$Lisp
   Not(x)    == LOGNOT(x)$Lisp
   And(x,y)  == LOGAND(x,y)$Lisp
   x and y   == And(x,y)
   Or(x,y)   == LOGIOR(x,y)$Lisp
   x or y    == Or(x,y)
   xor(x,y)  == LOGXOR(x,y)$Lisp
   x < y     == %ilt(x,y)
   x > y     == %igt(x,y)
   x <= y    == %ile(x,y)
   x >= y    == %ige(x,y)
   inc x     == QSADD1(x)$Lisp
   dec x     == QSSUB1(x)$Lisp
   - x       == %ineg x
   x + y     == %iadd(x,y)
   x:% - y:% == %isub(x,y)
   x:% * y:% == %imul(x,y)
   x:% ** n:NonNegativeInteger == 
      (%ipow(x, n)$Foreign(Builtin) pretend Integer)::%
   x quo y   == %iquo(x,y)
   x rem y   == %irem(x,y)
   divide(x, y)   == %idivide(x,y)$Foreign(Builtin)
   gcd(x,y)  == %igcd(x,y)
   abs(x)    == %iabs x
   odd?(x)   == %iodd? x
   zero?(x)  == QSZEROP(x)$Lisp
   one?(x)   == x = 1@%
   max(x,y)  == %imax(x,y)
   min(x,y)  == %imin(x,y)
   hash(x)   == %hash x
   length(x) == INTEGER_-LENGTH(x)$Lisp
   shift(x,n)    == QSLEFTSHIFT(x,n)$Lisp
   mulmod(a,b,p) == QSMULTMOD(a,b,p)$Lisp
   addmod(a,b,p) == QSADDMOD(a,b,p)$Lisp
   submod(a,b,p) == QSDIFMOD(a,b,p)$Lisp
   negative?(x)  == QSMINUSP$Lisp x
   size() == (MAXINT -$Lisp MININT +$Lisp 1$Lisp)  pretend NonNegativeInteger
   index i == per(i + MININT - 1$Lisp)
   lookup x ==
     (x -$Lisp MININT +$Lisp 1$Lisp) pretend PositiveInteger


   reducedSystem(m: Matrix %, v: Vector %) ==
        [m pretend Matrix(Integer), v pretend Vector(Integer)]

   positiveRemainder(x,n) ==
      r := %irem(x,n)
      negative? r =>
        negative? n => x - n 
        r + n
      r

   coerce(x:Integer):% == per x

   random() ==
      seed := TIMES(MULTIPLIER,seed)$Lisp rem MODULUS
      seed rem BASE

   random(n) == RANDOM(n)$Lisp

   UCA ==> Record(unit:%,canonical:%,associate:%)
   unitNormal x ==
      negative? x => [-1@%,-x,-1@%]$UCA
      [1@%,x,1@%]$UCA

@


\section{License}

<<license>>=
--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
--All rights reserved.
-- Copyright (C) 2007-2010, Gabriel Dos Reis.
-- All rights reserved.
--
--Redistribution and use in source and binary forms, with or without
--modification, are permitted provided that the following conditions are
--met:
--
--    - Redistributions of source code must retain the above copyright
--      notice, this list of conditions and the following disclaimer.
--
--    - Redistributions in binary form must reproduce the above copyright
--      notice, this list of conditions and the following disclaimer in
--      the documentation and/or other materials provided with the
--      distribution.
--
--    - Neither the name of The Numerical ALgorithms Group Ltd. nor the
--      names of its contributors may be used to endorse or promote products
--      derived from this software without specific prior written permission.
--
--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
@
<<*>>=
<<license>>

<<category INS IntegerNumberSystem>>
<<domain SINT SingleInteger>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}