/usr/share/axiom-20170501/src/algebra/NCODIV.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 | )abbrev package NCODIV NonCommutativeOperatorDivision
++ Author: Jean Della Dora, Stephen M. Watt
++ Date Created: 1986
++ Date Last Updated: May 30, 1991
++ Description:
++ This package provides a division and related operations for
++ \spadtype{MonogenicLinearOperator}s over a \spadtype{Field}.
++ Since the multiplication is in general non-commutative,
++ these operations all have left- and right-hand versions.
++ This package provides the operations based on left-division.\br
++ \tab{5}[q,r] = leftDivide(a,b) means a=b*q+r
NonCommutativeOperatorDivision(P, F) : SIG == CODE where
P : MonogenicLinearOperator(F)
F : Field
SIG ==> with
leftDivide : (P, P) -> Record(quotient: P, remainder: P)
++ leftDivide(a,b) returns the pair \spad{[q,r]} such that
++ \spad{a = b*q + r} and the degree of \spad{r} is
++ less than the degree of \spad{b}.
++ This process is called ``left division''.
leftQuotient : (P, P) -> P
++ leftQuotient(a,b) computes the pair \spad{[q,r]} such that
++ \spad{a = b*q + r} and the degree of \spad{r} is
++ less than the degree of \spad{b}.
++ The value \spad{q} is returned.
leftRemainder : (P, P) -> P
++ leftRemainder(a,b) computes the pair \spad{[q,r]} such that
++ \spad{a = b*q + r} and the degree of \spad{r} is
++ less than the degree of \spad{b}.
++ The value \spad{r} is returned.
leftExactQuotient : (P, P) -> Union(P, "failed")
++ leftExactQuotient(a,b) computes the value \spad{q}, if it exists,
++ such that \spad{a = b*q}.
leftGcd : (P, P) -> P
++ leftGcd(a,b) computes the value \spad{g} of highest degree
++ such that
++ \spad{a = aa*g}
++ \spad{b = bb*g}
++ for some values \spad{aa} and \spad{bb}.
++ The value \spad{g} is computed using left-division.
leftLcm : (P, P) -> P
++ leftLcm(a,b) computes the value \spad{m} of lowest degree
++ such that \spad{m = a*aa = b*bb} for some values
++ \spad{aa} and \spad{bb}. The value \spad{m} is
++ computed using left-division.
CODE ==> add
leftDivide(a, b) ==
q: P := 0
r: P := a
iv:F := inv leadingCoefficient b
while degree r >= degree b and r ^= 0 repeat
h := monomial(iv*leadingCoefficient r,
(degree r - degree b)::NonNegativeInteger)$P
r := r - b*h
q := q + h
[q,r]
-- leftQuotient(a,b) is the quotient from left division, etc.
leftQuotient(a,b) == leftDivide(a,b).quotient
leftRemainder(a,b) == leftDivide(a,b).remainder
leftExactQuotient(a,b) ==
qr := leftDivide(a,b)
if qr.remainder = 0 then qr.quotient else "failed"
-- l = leftGcd(a,b) means a = aa*l b = bb*l. Uses leftDivide.
leftGcd(a,b) ==
a = 0 =>b
b = 0 =>a
while degree b > 0 repeat (a,b) := (b, leftRemainder(a,b))
if b=0 then a else b
-- l = leftLcm(a,b) means l = a*aa l = b*bb Uses leftDivide.
leftLcm(a,b) ==
a = 0 =>b
b = 0 =>a
b0 := b
u := monomial(1,0)$P
v := 0
while leadingCoefficient b ^= 0 repeat
qr := leftDivide(a,b)
(a, b) := (b, qr.remainder)
(u, v) := (u*qr.quotient+v, u)
b0*u
|