Tropical algebra overloading
Tropical algebra overloading is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
In algebra, a max tropical semiring (also called a max-plus algebra) is the semiring (ℝ ∪ -Inf, ⊕, ⊗) containing the ring of real numbers ℝ augmented by negative infinity, the max function (returns the greater of two real numbers), and addition.
In max tropical algebra, x ⊕ y = max(x, y) and x ⊗ y = x + y. The identity for ⊕ is -Inf (the max of any number with -infinity is that number), and the identity for ⊗ is 0.
- Task
- Define functions or, if the language supports the symbols as operators, operators for ⊕ and ⊗ that fit the above description. If the language does not support ⊕ and ⊗ as operators but allows overloading operators for a new object type, you may instead overload + and * for a new min tropical albrbraic type. If you cannot overload operators in the language used, define ordinary functions for the purpose.
Show that 2 ⊗ -2 is 0, -0.001 ⊕ -Inf is -0.001, 0 ⊗ -Inf is -Inf, 1.5 ⊕ -1 is 1.5, and -0.5 ⊗ 0 is -0.5.
- Define exponentiation as serial ⊗, and in general that a to the power of b is a * b. Use either ↑ or similar up arrow or the carat ^, as an exponentiation operator if this can be used to overload such "exponentiation" in the language being used. Show what your program calculates for (-1)↑(1/2) by the above definition.
- Max tropical algebra is distributive, so that
a ⊗ (b ⊕ c) equals a ⊗ b ⊕ b ⊗ c,
where ⊗ has precedence over ⊕. Demonstrate that 5 ⊗ (8 ⊕ 7) equals 5 ⊗ 8 ⊕ 5 ⊗ 7.
- See also
Python
<lang python>from numpy import Inf
class MaxTropical:
""" Class for max tropical algebra. x + y is max(x, y) and X * y is x + y """ def __init__(self, x=0): self.x = x
def __str__(self): return str(self.x)
def __add__(self, other): return MaxTropical(max(self.x, other.x))
def __mul__(self, other): return MaxTropical(self.x + other.x)
def __pow__(self, other): return MaxTropical(self.x * other.x)
def __eq__(self, other): return self.x == other.x
if __name__ == "__main__":
a = MaxTropical(-2) b = MaxTropical(-1) c = MaxTropical(-0.5) d = MaxTropical(-0.001) e = MaxTropical(0) f = MaxTropical(0.5) g = MaxTropical(1) h = MaxTropical(1.5) i = MaxTropical(2) j = MaxTropical(5) k = MaxTropical(7) l = MaxTropical(8) m = MaxTropical(-Inf)
print("2 * -2 == ", i * a) print("-0.001 + -Inf == ", d + m) print("0 * -Inf == ", e * m) print("1.5 + -1 == ", h + b) print("-0.5 * 0 == ", c * e) print("(-1)**(1/2) == ", b**f) print("5 * (8 + 7)) == ", j * (l + k)) print("5 * 8 + 5 * 7 == ", j * l + j * k) print("5 * (8 + 7) == 5 * 8 + 5 * 7", j * (l + k) == j * l + j * k)
</lang>
- Output:
2 * -2 == 0 -0.001 + -Inf == -0.001 0 * -Inf == -inf 1.5 + -1 == 1.5 -0.5 * 0 == -0.5 (-1)**(1/2) == -0.5 5 * (8 + 7)) == 13 5 * 8 + 5 * 7 == 13 5 * (8 + 7) == 5 * 8 + 5 * 7 True