Tropical algebra overloading
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, where a is a real number and b must be a positive integer. 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. Calculate 5 ↑ 7 using this 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.
- If the language used does not support operator overloading, you may use ordinary function names such as tropicalAdd(x, y) and tropicalMul(x, y).
- See also
Factor
<lang factor>USING: combinators.short-circuit io kernel math math.functions math.order present prettyprint sequences typed ;
ALIAS: ⊕ max ALIAS: ⊗ + PREDICATE: posint < integer 0 > ; TYPED: ↑ ( x: real n: posint -- y: real ) * ;
- show ( quot -- )
dup present rest but-last "⟶ " append write call . ; inline
{
[ 2 -2 ⊗ ] [ -0.001 -1/0. ⊕ ] [ 0 -1/0. ⊗ ] [ 1.5 -1 ⊕ ] [ -0.5 0 ⊗ ] [ 5 7 ↑ ] [ 8 7 ⊕ 5 ⊗ ] [ 5 8 ⊗ 5 7 ⊗ ⊕ ] [ 8 7 ⊕ 5 ⊗ 5 8 ⊗ 5 7 ⊗ ⊕ = ]
} [ show ] each</lang>
- Output:
2 -2 ⊗ ⟶ 0 -0.001 -1/0. ⊕ ⟶ -0.001 0 -1/0. ⊗ ⟶ -1/0. 1.5 -1 ⊕ ⟶ 1.5 -0.5 0 ⊗ ⟶ -0.5 5 7 ↑ ⟶ 35 8 7 ⊕ 5 ⊗ ⟶ 13 5 8 ⊗ 5 7 ⊗ ⊕ ⟶ 13 8 7 ⊕ 5 ⊗ 5 8 ⊗ 5 7 ⊗ ⊕ = ⟶ t
Julia
<lang julia>⊕(x, y) = max(x, y) ⊗(x, y) = x + y ↑(x, y) = (@assert round(y) == y && y > 0; x * y)
@show 2 ⊗ -2 @show -0.001 ⊕ -Inf @show 0 ⊗ -Inf @show 1.5 ⊕ -1 @show -0.5 ⊗ 0 @show 5↑7 @show 5 ⊗ (8 ⊕ 7) @show 5 ⊗ 8 ⊕ 5 ⊗ 7 @show 5 ⊗ (8 ⊕ 7) == 5 ⊗ 8 ⊕ 5 ⊗ 7
</lang>
- Output:
2 ⊗ -2 = 0 -0.001 ⊕ -Inf = -0.001 0 ⊗ -Inf = -Inf 1.5 ⊕ -1 = 1.5 -0.5 ⊗ 0 = -0.5 5 ↑ 7 = 35 5 ⊗ (8 ⊕ 7) = 13 5 ⊗ 8 ⊕ 5 ⊗ 7 = 13 5 ⊗ (8 ⊕ 7) == 5 ⊗ 8 ⊕ 5 ⊗ 7 = true
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):
assert other.x // 1 == other.x and other.x > 0, "Invalid Operation"
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("5**7 == ", j**k)
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 5 ** 7 == 35 5 * (8 + 7)) == 13 5 * 8 + 5 * 7 == 13 5 * (8 + 7) == 5 * 8 + 5 * 7 True
R
R's overloaded operators, denoted by %_%, have different precedence order than + and *, so parentheses are needed for the distributive example. <lang r>"%+%"<- function(x, y) max(x, y)
"%*%" <- function(x, y) x + y
"%^%" <- function(x, y) {
stopifnot(round(y) == y && y > 0) x * y
}
cat("2 %*% -2 ==", 2 %*% -2, "\n") cat("-0.001 %+% -Inf ==", 0.001 %+% -Inf, "\n") cat("0 %*% -Inf ==", 0 %*% -Inf, "\n") cat("1.5 %+% -1 ==", 1.5 %+% -1, "\n") cat("-0.5 %*% 0 ==", -0.5 %*% 0, "\n") cat("5^7 ==", 5 %^% 7, "\n") cat("5 %*% (8 %+% 7)) ==", 5 %*% (8 %+% 7), "\n") cat("5 %*% 8 %+% 5 %*% 7 ==", (5 %*% 8) %+% (5 %*% 7), "\n") cat("5 %*% 8 %+% 5 %*% 7 == 5 %*% (8 %+% 7))", 5 %*% (8 %+% 7) == (5 %*% 8) %+% (5 %*% 7), "\n")
</lang>
- Output:
2 %*% -2 == 0 -0.001 %+% -Inf == 0.001 0 %*% -Inf == -Inf 1.5 %+% -1 == 1.5 -0.5 %*% 0 == -0.5 5^7 == 35 5 %*% (8 %+% 7)) == 13 5 %*% 8 %+% 5 %*% 7 == 13 5 %*% 8 %+% 5 %*% 7 == 5 %*% (8 %+% 7)) TRUE