diff options
Diffstat (limited to 'macros/luatex/latex/luacas/tex/algebra/ring.lua')
-rw-r--r-- | macros/luatex/latex/luacas/tex/algebra/ring.lua | 326 |
1 files changed, 326 insertions, 0 deletions
diff --git a/macros/luatex/latex/luacas/tex/algebra/ring.lua b/macros/luatex/latex/luacas/tex/algebra/ring.lua new file mode 100644 index 0000000000..4903b9c912 --- /dev/null +++ b/macros/luatex/latex/luacas/tex/algebra/ring.lua @@ -0,0 +1,326 @@ +--- @class Ring +--- Interface for an element of a ring with unity. +Ring = {} +__Ring = {} + +-------------------------- +-- Static functionality -- +-------------------------- + +--- Determines which ring the output of a binary operation with inputs in ring1 and ring2 should be, if such a ring exists. +--- If one of the rings is a subring of another ring, the result should be one of the two rings. +--- @param ring1 RingIdentifier +--- @param ring2 RingIdentifier +--- @return RingIdentifier +function Ring.resultantring(ring1, ring2) + if ring1 == ring2 then + return ring1 + end + + if ((ring1 == PolynomialRing.getring() and ring2 == Rational.getring()) or + (ring2 == PolynomialRing.getring() and ring1 == Rational.getring())) + and ring1.symbol == ring2.symbol then + return Rational.makering(ring1.symbol, Ring.resultantring(ring1.child, ring2.child)) + end + + if ring1 == PolynomialRing.getring() or ring2 == PolynomialRing.getring() then + if ring1 == ring2.child then + return ring2 + end + if ring2 == ring1.child then + return ring1 + end + + if ring1 == PolynomialRing.getring() and ring2 == PolynomialRing.getring() and ring1.symbol == ring2.symbol then + return PolynomialRing.makering(ring1.symbol, Ring.resultantring(ring1.child, ring2.child)) + end + + -- If none of the above conditions are satisfied, recusion is a pain, so we just strip all of the variables off of both rings. + -- TODO: Make this properly recursive, or just use a multivariable polynomial ring class + local symbols = {} + while ring1 == PolynomialRing.getring() do + symbols[#symbols+1] = ring1.symbol + ring1 = ring1.child + end + while ring2 == PolynomialRing.getring() do + if not Contains(symbols, ring2.symbol) then + symbols[#symbols+1] = ring2.symbol + end + ring2 = ring2.child + end + local ring = Ring.resultantring(ring1, ring2) + + if ring == Rational.getring() and Contains(symbols, ring.symbol) then + symbols = Remove(symbols, ring.symbol) + end + for i = #symbols, 1, -1 do + ring = PolynomialRing.makering(symbols[i], ring) + end + return ring + end + + if ring1 == Integer.getring() then + if ring2 == Integer.getring() then + return ring2 + end + + if ring2 == Rational.getring() then + return ring2 + end + + if ring2 == IntegerModN.getring() then + return ring2 + end + end + + if ring1 == Rational.getring() then + if ring2 == Integer.getring() then + return ring1 + end + + if ring2 == Rational.getring() then + if not ring1.symbol then + return Rational.makering(ring2.symbol, Ring.resultantring(ring1, ring2.child)) + end + if not ring2.symbol then + return Rational.makering(ring1.symbol, Ring.resultantring(ring1.child, ring2)) + end + if ring1.symbol and ring2.symbol and ring1.symbol == ring2.symbol then + return Rational.makering(ring1.symbol, Ring.resultantring(ring1.child, ring2.child)) + end + return ring2 + end + + if ring2 == IntegerModN.getring() then + return nil + end + end + + if ring1 == IntegerModN.getring() then + if ring2 == Integer.getring() then + return ring1 + end + + if ring2 == Rational.getring() then + return nil + end + + if ring2 == IntegerModN.getring() then + return IntegerModN.makering(Integer.gcd(ring1.modulus, ring2.modulus)) + end + end + + return nil +end + +--- Returns a particular instantiation of a ring. +--- Does the same thing as getring() if there is only one possible ring for a class, i.e., the integers and rationals. +--- @return RingIdentifier +function Ring.makering() + error("Called unimplemented method : makering()") +end + +---------------------- +-- Required methods -- +---------------------- + +--- Returns the ring this element is part of. +--- @return RingIdentifier +function Ring:getring() + error("Called unimplemented method : getring()") +end + +--- Explicitly converts this element to an element of another ring. +--- @param ring RingIdentifier +--- @return Ring +function Ring:inring(ring) + error("Called unimplemented method : in()") +end + +--- Returns whether the ring is commutative. +--- @return boolean +function Ring:iscommutative() + error("Called unimplemented method : iscommutative()") +end + +--- @return Ring +function Ring:add(b) + error("Called unimplemented method : add()") +end + +--- @return Ring +function Ring:sub(b) + return(self:add(b:neg())) +end + +--- @return Ring +function Ring:neg() + error("Called unimplemented method : neg()") +end + +--- @return Ring +function Ring:mul(b) + error("Called unimplemented method : mul()") +end + +--- Ring exponentiation by definition. Specific rings may implement more efficient methods. +--- @return Ring +function Ring:pow(n) + if(n < Integer.zero()) then + error("Execution error: Negative exponentiation is undefined over general rings") + end + local k = Integer.zero() + local b = self:one() + while k < n do + b = b * self + k = k + Integer.one() + end + return b +end + +--- @return boolean +function Ring:eq(b) + error("Execution error: Ring does not have a total order") +end + +--- @return boolean +function Ring:lt(b) + error("Execution error: Ring does not have a total order") +end + +--- @return boolean +function Ring:le(b) + error("Execution error: Ring does not have a total order") +end + +--- The additive identitity of the ring. +--- @return Ring +function Ring:zero() + error("Called unimplemented method : zero()") +end + +--- The multiplicative identitity of the ring. +--- @return Ring +function Ring:one() + error("Called unimplemented method : one()") +end + +-------------------------- +-- Instance metamethods -- +-------------------------- +__RingOperations = {} + +-- Each of these methods just handles coverting each element in the ring to an instance of the proper ring, if possible, +-- then passing the arguments to the function in a specific ring. + +__RingOperations.__unm = function(a) + return a:neg() +end + +__RingOperations.__add = function(a, b) + if not b.getring then + return BinaryOperation.ADDEXP({a, b}) + end + + local aring, bring = a:getring(), b:getring() + local oring = Ring.resultantring(aring, bring) + if not oring then + error("Attempted to add two elements of incompatable rings") + end + return a:inring(oring):add(b:inring(oring)) +end + +__RingOperations.__sub = function(a, b) + if not b.getring then + return BinaryOperation.SUBEXP({a, b}) + end + + local aring, bring = a:getring(), b:getring() + local oring = Ring.resultantring(aring, bring) + if not oring then + error("Attempted to subtract two elements of incompatable rings") + end + return a:inring(oring):sub(b:inring(oring)) +end + +-- Allows for multiplication by writing two expressions next to each other. +__RingOperations.__call = function (a, b) + return a * b +end + +__RingOperations.__mul = function(a, b) + if not b.getring then + return BinaryOperation.MULEXP({a, b}) + end + + local aring, bring = a:getring(), b:getring() + local oring = Ring.resultantring(aring, bring) + if not oring then + error("Attempted to muliply two elements of incompatable rings") + end + return a:inring(oring):mul(b:inring(oring)) +end + +__RingOperations.__pow = function(a, n) + if (not n.getring) or (n.getring and n:getring().ring ~= Integer) then + return BinaryOperation.POWEXP({a, n}) + end + + -- if a == a:zero() and n == Integer.zero() then + -- error("Cannot raise 0 to the power of 0") + -- end + + return a:pow(n) +end + +-- Comparison operations assume, of course, that the ring operation is equipped with a total order +-- All elements of all rings need these metamethods, since in Lua comparisons on tables only fire if both objects have the table +__RingOperations.__eq = function(a, b) + -- This shouldn't be needed, since __eq should only fire if both metamethods have the same function, but for some reason Lua always runs this anyway + if not a.getring or not b.getring then + return false + end + local aring, bring = a:getring(), b:getring() + if aring == bring then + return a:eq(b) + end + local oring = Ring.resultantring(aring, bring) + if not oring then + error("Attempted to compare two elements of incompatable rings") + end + return a:inring(oring):eq(b:inring(oring)) +end + +__RingOperations.__lt = function(a, b) + local aring, bring = a:getring(), b:getring() + if aring == bring then + return a:lt(b) + end + local oring = Ring.resultantring(aring, bring) + if not oring then + error("Attempted to compare two elements of incompatable rings") + end + return a:inring(oring):lt(b:inring(oring)) +end + +__RingOperations.__le = function(a, b) + local aring, bring = a:getring(), b:getring() + if aring == bring then + return a:le(b) + end + local oring = Ring.resultantring(aring, bring) + if not oring then + error("Attempted to compare two elements of incompatable rings") + end + return a:inring(oring):le(b:inring(oring)) +end + +----------------- +-- Inheritance -- +----------------- + +__Ring.__index = ConstantExpression +Ring = setmetatable(Ring, __Ring) + +--- Used for comparing and converting between rings. +--- @class RingIdentifier |