While Integer inherits from IntegerNumberSystem the category
StepThrough, the domains NNI and PI do not share this natural property.
I have added this, however, while init() overwrites the inherited
functiom init() (as a subdomain of Integer), this is not the case for
the correct nextItem, i.e. the interpreter chooses the function from
Integer and not from the domain PI itsself:
(1) -> init()$Integer
(1) 0
Type: Integer
(2) -> nextItem %
(2) 1
Type: Union(Integer,...)
(3) -> nextItem %
(3) - 1
Type: Union(Integer,...)
(4) -> nextItem %
(4) 2
Type: Union(Integer,...)
after compilation of integer-jg.spad, which I include:
(6) -> init()$NNI
(6) 0
Type: NonNegativeInteger
(7) -> nextItem %
(7) 1
Type: Union(Integer,...)
(8) -> nextItem %
(8) - 1
Type: Union(Integer,...)
(9) -> init()$PI
(9) 1
Type: PositiveInteger
(10) -> nextItem %
(10) - 1
Type: Union(Integer,...
--
Mit freundlichen Grüßen
Johannes Grabmeier
Prof. Dr. Johannes Grabmeier
Köckstraße 1, D-94469 Deggendorf
Tel. +49-(0)-991-2979584, Tel. +49-(0)-151-681-70756
Tel. +49-(0)-991-3615-141 (d), Fax: +49-(0)-32224-192688
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/fricas-devel/7ba1d628-1857-6239-b18f-f757b0ff8df6%40grabmeier.net.
For more options, visit https://groups.google.com/d/optout.
)abbrev package INTSLPE IntegerSolveLinearPolynomialEquation
++ Author: Davenport
++ Date Created: 1991
++ 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
)abbrev domain INT Integer
++ Author:
++ Basic Operations:
++ Related Constructors:
++ Keywords: integer
++ Description: \spadtype{Integer} provides the domain of arbitrary precision
++ integers.
Integer : Join(IntegerNumberSystem, LinearlyExplicitOver Integer,
PolynomialFactorizationExplicit, ConvertibleTo String,
OpenMath, Canonical, canonicalsClosed) with
random : % -> %
++ random(n) returns a random integer from 0 to \spad{n-1}.
== add
ZP ==> SparseUnivariatePolynomial %
ZZP ==> SparseUnivariatePolynomial Integer
x, y : %
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(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
hashUpdate!(hs, s) == update!(hs, SXHASH(s)$Lisp)$HashState
negative? x == MINUSP(x)$Lisp
positive? x == PLUSP(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
(0 <= (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 %, vec : Vector %):
Record(mat : Matrix(Integer), vec : Vector(Integer)) ==
[m pretend Matrix(Integer), vec pretend Vector(Integer)]
abs(x) == ABS(x)$Lisp
random(x) == RANDOM(x)$Lisp
x = y == EQL(x, y)$Lisp
x < y == (x<y)$Lisp
x > y == (x>y)$Lisp
-- critical for coercions to NonNegativeInteger
x >= y == (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
(m : PositiveInteger) * (y : %) == (m*y)$Lisp
(m : NonNegativeInteger) * (y : %) == (m*y)$Lisp
(x : %) ^ (n : NonNegativeInteger) == EXPT(x, n)$Lisp
(x : %) ^ (n : PositiveInteger) == EXPT(x, n)$Lisp
odd? x == ODDP(x)$Lisp
even? x == EVENP(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 == REM(x, y)$Lisp
shift(x, y) == ASH(x, y)$Lisp
x exquo y ==
zero? y => "failed"
z : SExpression := INTEXQUO(x, y)$Lisp
integer?(z) => z pretend %
"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))
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)
opposite?(x,y) == x = -y
annihilate?(x,y) == zero? x or zero? y
-- copied from IntegerNumberSystem to get inline optimization,
-- speeds up functions like 'primes'
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)
-- copied from IntegerNumberSystem to get inline optimization
symmetricRemainder(x, n) ==
r := x rem n
r = 0 => 0
if n < 0 then n := -n
r > 0 =>
2 * r > n => r - n
r
2 * r + n <= 0 => r + n
r
)abbrev domain NNI NonNegativeInteger
++ Author:
++ Basic Operations:
++ Related Constructors:
++ Keywords: integer
++ Description: \spadtype{NonNegativeInteger} provides functions for non
++ negative integers.
NonNegativeInteger : Join(OrderedAbelianMonoidSup, SemiRing,
CommutativeStar, ConvertibleTo InputForm,
StepThrough) 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}.
qcoerce : Integer -> %
++ qcoerce(n) coerces \spad{n} to \spad{%} trusting that
++ \spad{n} is nonnegative
== SubDomain(Integer, #1 >= 0) add
x, y : %
sup(x, y) == MAX(x, y)$Lisp
shift(x : %, n : Integer) : % == ASH(x, n)$Lisp
qcoerce(n) == n pretend %
subtractIfCan(x, y) ==
c : Integer := (x pretend Integer) - (y pretend Integer)
c < 0 => "failed"
c pretend %
nextItem(n: %): Union(%, "failed") == n+1
)abbrev domain PI PositiveInteger
++ Author:
++ Basic Operations:
++ Related Constructors:
++ Keywords: positive integer
++ Description: \spadtype{PositiveInteger} provides functions for
++ positive integers.
PositiveInteger : Join(OrderedAbelianSemiGroup, Monoid, CommutativeStar,
ConvertibleTo InputForm, StepThrough) with
gcd : (%, %) -> %
++ gcd(a, b) computes the greatest common divisor of two
++ positive integers \spad{a} and b.
qcoerce : Integer -> %
++ qcoerce(n) coerces \spad{n} to \spad{%} trusting that
++ \spad{n} is positive
== SubDomain(NonNegativeInteger, #1 > 0) add
qcoerce(n) == n pretend %
init(): % == 1
nextItem(n: %): Union(%, "failed") == n+1
)abbrev domain ROMAN RomanNumeral
++ Author:
++ Basic Operations:
++ convert, roman
++ Related Constructors:
++ Keywords: roman numerals
++ Description: \spadtype{RomanNumeral} provides functions for converting
++ integers to roman numerals.
RomanNumeral() : Join(IntegerNumberSystem, Canonical, canonicalsClosed) with
convert : Symbol -> %
++ convert(n) creates a roman numeral for symbol n.
roman : Symbol -> %
++ roman(n) creates a roman numeral for symbol n.
roman : Integer -> %
++ roman(n) creates a roman numeral for n.
== Integer add
import from 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
--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.
