axiom-source 20170501-3 / usr / share / axiom-20170501 / src / algebra / INT.spad

)abbrev domain INT Integer
++ Author: Mark Botch
++ References:
++ Corl00 According to Abramowitz and Stegun or arccoth needn't be Uncouth
++ Fate01a A Critique of OpenMath and Thoughts on Encoding Mathematics
++ Description: 
++ \spadtype{Integer} provides the domain of arbitrary precision integers.

Integer() : SIG == CODE where

  SIG ==> 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".

  CODE ==> 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 == 
        (-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

      x exquo y ==
         zero? y => "failed"
         zero?(x rem y) => x quo y
         "failed"

      recip(x) == 
        if (x = 1) 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((x1:%):ZP+->x1::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)