/usr/share/axiom-20170501/src/algebra/EUCDOM.spad is in axiom-source 20170501-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 | )abbrev category EUCDOM EuclideanDomain
++ Description:
++ A constructive euclidean domain, one can divide producing
++ a quotient and a remainder where the remainder is either zero
++ or is smaller (\spadfun{euclideanSize}) than the divisor.
++
++ Conditional attributes\br
++ \tab{5}multiplicativeValuation\tab{5}Size(a*b)=Size(a)*Size(b)\br
++ \tab{5}additiveValuation\tab{11}Size(a*b)=Size(a)+Size(b)
EuclideanDomain() : Category == SIG where
SIG ==> PrincipalIdealDomain with
sizeLess? : (%,%) -> Boolean
++ sizeLess?(x,y) tests whether x is strictly
++ smaller than y with respect to the
++ \spadfunFrom{euclideanSize}{EuclideanDomain}.
euclideanSize : % -> NonNegativeInteger
++ euclideanSize(x) returns the euclidean size of the element x.
++ Error: if x is zero.
divide : (%,%) -> Record(quotient:%,remainder:%)
++ divide(x,y) divides x by y producing a record containing a
++ \spad{quotient} and \spad{remainder},
++ where the remainder is smaller (see
++ \spadfunFrom{sizeLess?}{EuclideanDomain}) than the divisor y.
"quo" : (%,%) -> %
++ x quo y is the same as \spad{divide(x,y).quotient}.
++ See \spadfunFrom{divide}{EuclideanDomain}.
"rem" : (%,%) -> %
++ x rem y is the same as \spad{divide(x,y).remainder}.
++ See \spadfunFrom{divide}{EuclideanDomain}.
extendedEuclidean : (%,%) -> Record(coef1:%,coef2:%,generator:%)
++ extendedEuclidean(x,y) returns a record rec where
++ \spad{rec.coef1*x+rec.coef2*y = rec.generator} and
++ rec.generator is a gcd of x and y.
++ The gcd is unique only
++ up to associates if \spadatt{canonicalUnitNormal} is not asserted.
++ \spadfun{principalIdeal} provides a version of this operation
++ which accepts an arbitrary length list of arguments.
extendedEuclidean : (%,%,%) -> Union(Record(coef1:%,coef2:%),"failed")
++ extendedEuclidean(x,y,z) either returns a record rec
++ where \spad{rec.coef1*x+rec.coef2*y=z} or returns "failed"
++ if z cannot be expressed as a linear combination of x and y.
multiEuclidean : (List %,%) -> Union(List %,"failed")
++ multiEuclidean([f1,...,fn],z) returns a list of coefficients
++ \spad{[a1, ..., an]} such that
++ \spad{ z / prod fi = sum aj/fj}.
++ If no such list of coefficients exists, "failed" is returned.
add
x,y,z: %
l: List %
sizeLess?(x,y) ==
zero? y => false
zero? x => true
euclideanSize(x)<euclideanSize(y)
x quo y == divide(x,y).quotient --divide must be user-supplied
x rem y == divide(x,y).remainder
x exquo y ==
zero? x => 0
zero? y => "failed"
qr:=divide(x,y)
zero?(qr.remainder) => qr.quotient
"failed"
gcd(x,y) == --Euclidean Algorithm
x:=unitCanonical x
y:=unitCanonical y
while not zero? y repeat
(x,y):= (y,x rem y)
y:=unitCanonical y -- this doesn't affect the
-- correctness of Euclid's algorithm,
-- but
-- a) may improve performance
-- b) ensures gcd(x,y)=gcd(y,x)
-- if canonicalUnitNormal
x
IdealElt ==> Record(coef1:%,coef2:%,generator:%)
unitNormalizeIdealElt(s:IdealElt):IdealElt ==
(u,c,a):=unitNormal(s.generator)
(a = 1) => s
[a*s.coef1,a*s.coef2,c]$IdealElt
extendedEuclidean(x,y) == --Extended Euclidean Algorithm
s1:=unitNormalizeIdealElt([1$%,0$%,x]$IdealElt)
s2:=unitNormalizeIdealElt([0$%,1$%,y]$IdealElt)
zero? y => s1
zero? x => s2
while not zero?(s2.generator) repeat
qr:= divide(s1.generator, s2.generator)
s3:=[s1.coef1 - qr.quotient * s2.coef1,
s1.coef2 - qr.quotient * s2.coef2, qr.remainder]$IdealElt
s1:=s2
s2:=unitNormalizeIdealElt s3
if not(zero?(s1.coef1)) and not sizeLess?(s1.coef1,y)
then
qr:= divide(s1.coef1,y)
s1.coef1:= qr.remainder
s1.coef2:= s1.coef2 + qr.quotient * x
s1 := unitNormalizeIdealElt s1
s1
TwoCoefs ==> Record(coef1:%,coef2:%)
extendedEuclidean(x,y,z) ==
zero? z => [0,0]$TwoCoefs
s:= extendedEuclidean(x,y)
(w:= z exquo s.generator) case "failed" => "failed"
zero? y => [s.coef1 * w, s.coef2 * w]$TwoCoefs
qr:= divide((s.coef1 * w), y)
[qr.remainder, s.coef2 * w + qr.quotient * x]$TwoCoefs
principalIdeal l ==
l = [] => error "empty list passed to principalIdeal"
rest l = [] =>
uca:=unitNormal(first l)
[[uca.unit],uca.canonical]
rest rest l = [] =>
u:= extendedEuclidean(first l,second l)
[[u.coef1, u.coef2], u.generator]
v:=principalIdeal rest l
u:= extendedEuclidean(first l,v.generator)
[[u.coef1,:[u.coef2*vv for vv in v.coef]],u.generator]
expressIdealMember(l,z) ==
z = 0 => [0 for v in l]
pid := principalIdeal l
(q := z exquo (pid.generator)) case "failed" => "failed"
[q*v for v in pid.coef]
multiEuclidean(l,z) ==
n := #l
zero? n => error "empty list passed to multiEuclidean"
n = 1 => [z]
l1 := copy l
l2 := split!(l1, n quo 2)
u:= extendedEuclidean(*/l1, */l2, z)
u case "failed" => "failed"
v1 := multiEuclidean(l1,u.coef2)
v1 case "failed" => "failed"
v2 := multiEuclidean(l2,u.coef1)
v2 case "failed" => "failed"
concat(v1,v2)
|