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

\documentclass{article}
\usepackage{axiom}
\begin{document}
\title{\$SPAD/src/algebra integer.spad}
\author{James Davenport}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{package INTSLPE IntegerSolveLinearPolynomialEquation}
<<package INTSLPE IntegerSolveLinearPolynomialEquation>>=
)abbrev package INTSLPE IntegerSolveLinearPolynomialEquation
++ Author: Davenport
++ Date Created: 1991
++ Date Last Updated:
++ Basic Functions:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ This package provides the implementation for the
++ \spadfun{solveLinearPolynomialEquation}
++ operation over the integers. It uses a lifting technique
++ from the package GenExEuclid
IntegerSolveLinearPolynomialEquation(): C ==T
 where
  ZP ==> SparseUnivariatePolynomial Integer
  C == with
      solveLinearPolynomialEquation: (List ZP,ZP) -> Union(List ZP,"failed")
           ++ solveLinearPolynomialEquation([f1, ..., fn], g)
           ++ (where the fi are relatively prime to each other)
           ++ returns a list of ai such that
           ++ \spad{g/prod fi = sum ai/fi}
           ++ or returns "failed" if no such list of ai's exists.
  T == add
      oldlp:List ZP := []
      slpePrime:Integer:=(2::Integer)
      oldtable:Vector List ZP := empty()
      solveLinearPolynomialEquation(lp,p) ==
         if (oldlp ~= lp) then
            -- we have to generate a new table
            deg:= _+/[degree u for u in lp]
            ans:Union(Vector List ZP,"failed"):="failed"
            slpePrime:=2147483647::Integer   -- 2**31 -1 : a prime
                 -- a good test case for this package is
                 --  ([x**31-1,x-2],2)
            while (ans case "failed") repeat
              ans:=tablePow(deg,slpePrime,lp)$GenExEuclid(Integer,ZP)
              if (ans case "failed") then
                 slpePrime:= prevPrime(slpePrime)$IntegerPrimesPackage(Integer)
            oldtable:=(ans:: Vector List ZP)
         answer:=solveid(p,slpePrime,oldtable)
         answer

@
\section{domain INT Integer}

<<domain INT Integer>>=
)abbrev domain INT Integer
++ Author:
++ Date Created:
++ Change History:
++ Basic Operations:
++ Related Constructors:
++ Keywords: integer
++ Description: \spadtype{Integer} provides the domain of arbitrary precision
++ integers.

Integer: Join(IntegerNumberSystem, ConvertibleTo String, OpenMath) with
    random   : % -> %
      ++ random(n) returns a random integer from 0 to \spad{n-1}.
    canonical
      ++ mathematical equality is data structure equality.
    canonicalsClosed
      ++ two positives multiply to give positive.
    noetherian
      ++ ascending chain condition on ideals.
    infinite
      ++ nextItem never returns "failed".
 == add
      ZP ==> SparseUnivariatePolynomial %
      ZZP ==> SparseUnivariatePolynomial Integer
      x,y: %
      n: NonNegativeInteger

      writeOMInt(dev: OpenMathDevice, x: %): Void ==
        if x < 0 then
          OMputApp(dev)
          OMputSymbol(dev, "arith1", "unary__minus")
          OMputInteger(dev, (-x) pretend Integer)
          OMputEndApp(dev)
        else
          OMputInteger(dev, x pretend Integer)

      OMwrite(x: %): String ==
        s: String := ""
        sp := OM_-STRINGTOSTRINGPTR(s)$Lisp
        dev: OpenMathDevice := OMopenString(sp pretend String, OMencodingXML)
        OMputObject(dev)
        writeOMInt(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)
        writeOMInt(dev, x)
        if wholeObj then
          OMputEndObject(dev)
        OMclose(dev)
        s := OM_-STRINGPTRTOSTRING(sp)$Lisp pretend String
        s

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

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

      zero? x == ZEROP(x)$Lisp
      one? x == x = 1
      0 == 0$Lisp
      1 == 1$Lisp
      base()  == 2$Lisp
      copy x  == x
      inc  x  == x + 1
      dec  x  == x - 1
      hash x == SXHASH(x)$Lisp
      negative? x == MINUSP(x)$Lisp
      coerce(x):OutputForm == outputForm(x pretend Integer)
      coerce(m:Integer):% == m pretend %
      convert(x:%):Integer == x pretend Integer
      length a == INTEGER_-LENGTH(a)$Lisp
      addmod(a, b, p) ==
         (c:=a + b) >= p => c - p
         c
      submod(a, b, p) ==
         (c:=a - b) < 0 => c + p
         c
      mulmod(a, b, p) == (a * b) rem p
      convert(x:%):Float       == coerce(x pretend Integer)$Float
      convert(x:%):DoubleFloat  == coerce(x pretend Integer)$DoubleFloat
      convert(x:%):InputForm   == convert(x pretend Integer)$InputForm
      convert(x:%):String      == string(x pretend Integer)$String

      latex(x:%):String ==
        s : String := string(x pretend Integer)$String
        (-1 < (x pretend Integer)) and ((x  pretend Integer) < 10) => s
        concat("{", concat(s, "}")$String)$String

      positiveRemainder(a, b) ==
        negative?(r := a rem b) =>
           negative? b => r - b
           r + b
        r

      reducedSystem(m:Matrix %):Matrix(Integer) ==
        m pretend Matrix(Integer)

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

      abs(x) == ABS(x)$Lisp
      random() == random()$Lisp
      random(x) == RANDOM(x)$Lisp
      x = y == EQL(x,y)$Lisp
      x < y == (x<y)$Lisp
      x > y == (x > y)$Lisp       -- Don't rely on default; help the inliner
      x <= y == (x <= y)$Lisp     -- Ditto
      x >= y == (x >= y)$Lisp     -- Ditto
      - x == (-x)$Lisp
      x + y == (x+y)$Lisp
      x - y == (x-y)$Lisp
      x * y == (x*y)$Lisp
      (m:Integer) * (y:%) == (m*y)$Lisp -- for subsumption problem
      x ** n == EXPT(x,n)$Lisp
      odd? x == ODDP(x)$Lisp
      max(x,y) == MAX(x,y)$Lisp
      min(x,y) == MIN(x,y)$Lisp
      divide(x,y) == DIVIDE2(x,y)$Lisp
      x quo y == QUOTIENT2(x,y)$Lisp
      x rem y == REMAINDER2(x,y)$Lisp
      shift(x, y) == ASH(x,y)$Lisp
      recip(x) == if one? x or x=-1 then x else "failed"
      gcd(x,y) == GCD(x,y)$Lisp
      UCA ==> Record(unit:%,canonical:%,associate:%)
      unitNormal x ==
         x < 0 => [-1,-x,-1]$UCA
         [1,x,1]$UCA
      unitCanonical x == abs x
      solveLinearPolynomialEquation(lp:List ZP,p:ZP):Union(List ZP,"failed") ==
         solveLinearPolynomialEquation(lp pretend List ZZP,
               p pretend ZZP)$IntegerSolveLinearPolynomialEquation pretend
                     Union(List ZP,"failed")
      squareFreePolynomial(p:ZP):Factored ZP ==
        squareFree(p)$UnivariatePolynomialSquareFree(%,ZP)
      factorPolynomial(p:ZP):Factored ZP ==
         -- GaloisGroupFactorizer doesn't factor the content
         -- so we have to do this by hand
         pp:=primitivePart p
         leadingCoefficient pp = leadingCoefficient p =>
             factor(p)$GaloisGroupFactorizer(ZP)
         mergeFactors(factor(pp)$GaloisGroupFactorizer(ZP),
                        map(#1::ZP,
                            factor((leadingCoefficient p exquo
                                    leadingCoefficient pp)
                                   ::%))$FactoredFunctions2(%,ZP)
                                     )$FactoredFunctionUtilities(ZP)
      factorSquareFreePolynomial(p:ZP):Factored ZP ==
           factorSquareFree(p)$GaloisGroupFactorizer(ZP)
      gcdPolynomial(p:ZP, q:ZP):ZP ==
         zero? p => unitCanonical q
         zero? q => unitCanonical p
         gcd([p,q])$HeuGcd(ZP)
--    myNextPrime: (%,NonNegativeInteger) -> %
--    myNextPrime(x,n) ==
--       nextPrime(x)$IntegerPrimesPackage(%)
--    TT:=InnerModularGcd(%,ZP,67108859 pretend %,myNextPrime)
--    gcdPolynomial(p,q) == modularGcd(p,q)$TT

@


\section{domain NNI NonNegativeInteger}

<<domain NNI NonNegativeInteger>>=
)abbrev domain NNI NonNegativeInteger
++ Author:
++ Date Created:
++ Change History:
++ Basic Operations:
++ Related Constructors:
++ Keywords: integer
++ Description: \spadtype{NonNegativeInteger} provides functions for non
++   negative integers.
NonNegativeInteger: Join(OrderedAbelianMonoidSup,Monoid) with
            _quo : (%,%) -> %
              ++ a quo b returns the quotient of \spad{a} and b, forgetting
              ++ the remainder.
            _rem : (%,%) -> %
              ++ a rem b returns the remainder of \spad{a} and b.
            gcd  : (%,%) -> %
              ++ gcd(a,b) computes the greatest common divisor of two
              ++ non negative integers \spad{a} and b.
            divide: (%,%) -> Record(quotient:%,remainder:%)
              ++ divide(a,b) returns a record containing both
              ++ remainder and quotient.
            _exquo: (%,%) -> Union(%,"failed")
              ++ exquo(a,b) returns the quotient of \spad{a} and b, or "failed"
              ++ if b is zero or \spad{a} rem b is zero.
            shift: (%, Integer) -> %
              ++ shift(a,i) shift \spad{a} by i bits.
            random   : % -> %
              ++ random(n) returns a random integer from 0 to \spad{n-1}.
            commutative("*")
              ++ commutative("*") means multiplication is commutative : \spad{x*y = y*x}.

  == SubDomain(Integer,#1 >= 0) add
      x,y:%
      sup(x,y) == MAX(x,y)$Lisp
      shift(x:%, n:Integer):% == ASH(x,n)$Lisp
      subtractIfCan(x, y) ==
        c:Integer := rep x - rep y
        c < 0 => "failed"
        per c

@

\section{domain PI PositiveInteger}
<<domain PI PositiveInteger>>=
)abbrev domain PI PositiveInteger
++ Author:
++ Date Created:
++ Change History:
++ Basic Operations:
++ Related Constructors:
++ Keywords: positive integer
++ Description: \spadtype{PositiveInteger} provides functions for
++   positive integers.
PositiveInteger: Join(OrderedAbelianSemiGroup,Monoid) with
            gcd: (%,%) -> %
              ++ gcd(a,b) computes the greatest common divisor of two
              ++ positive integers \spad{a} and b.
            commutative("*")
              ++ commutative("*") means multiplication is commutative : x*y = y*x
 == SubDomain(NonNegativeInteger,#1 > 0)

@


\section{domain ROMAN RomanNumeral}
<<domain ROMAN RomanNumeral>>=
)abbrev domain ROMAN RomanNumeral
++ Author:
++ Date Created:
++ Change History:
++ Basic Operations:
++   convert, roman
++ Related Constructors:
++ Keywords: roman numerals
++ Description:  \spadtype{RomanNumeral} provides functions for converting
++   integers to roman numerals.
RomanNumeral(): Join(IntegerNumberSystem,ConvertibleFrom Symbol) with
    canonical
      ++ mathematical equality is data structure equality.
    canonicalsClosed
      ++ two positives multiply to give positive.
    noetherian
      ++ ascending chain condition on ideals.
    roman  : Symbol  -> %
      ++ roman(n) creates a roman numeral for symbol n.
    roman  : Integer -> %
      ++ roman(n) creates a roman numeral for n.

  == Integer add
        import NumberFormats()

        roman(n:Integer) == n::%
        roman(sy:Symbol) == convert sy
        convert(sy:Symbol):%    == ScanRoman(string sy)::%

        coerce(r:%):OutputForm ==
            n := convert(r)@Integer
            -- okay, we stretch it
            zero? n => n::OutputForm
            negative? n => - ((-r)::OutputForm)
            FormatRoman(n::PositiveInteger)::Symbol::OutputForm

@
\section{License}
<<license>>=
--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
--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>>

<<package INTSLPE IntegerSolveLinearPolynomialEquation>>
<<domain INT Integer>>
<<domain NNI NonNegativeInteger>>
<<domain PI PositiveInteger>>
<<domain ROMAN RomanNumeral>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}