Tropical arithmetic replaces addition with minimization and multiplication with addition.
Tropical arithmetic is just like regular arithmetic but with two operations swapped out. Instead of addition you use min or max, and instead of multiplication you use addition. See also Lunar Arithmetic.
- tropical_add(a, b) = min(a, b) or max(a, b)
- tropical_mul(a, b) = a + b
The notation gives a way to rewrite mathematical expressions programmatically, which are easier for me to manipulate and reason about. Multisets are more natural than sets, counting multiplicities reduces everything to integer arithmetic which is a space I like.
+ 123 × 153 260 61 --- --- 263 1b4
The positional encoding does not allow for doing this kind of representation as numbers do not carry over. I could writedigits beyond 9 as hex: a=10, b=11 .. but the trick of representing arithmetic that does not work well, for that reason I'll use a linear postfix notation where bags are within brackets for the documentation. Each line is a step of the transformation, here is the evaluation of the example above 153 × 61:
[a b^5 c^3] [b^6 c] mul [a^1 b^11 c^4]
Tropical Multisets
If you have a bag of items and track how many times each item appears, then all the operations you'd want to do on those bags correspond exactly to max, min, and addition. So manipulating multisets in tropical arithmetic reduces to manipulating plain integers.
a ∪ b is max
[red green blue^2] [red blue^3] max [red green blue^3]
You can think of max as the smallest bag that covers both bags, or the LCM.
[apple orange^2] [apple^2 orange] max [apple^2 orange^2]
a ∩ b is min
[red green blue^2] [red blue^3] min [red blue^2]
To check if a set contains a specific item, it comes down to looking up whether the min of an item is greater than zero, or the GCD:
[red green blue^2] [green] min [green]
[red green blue^2] [yellow] min []
a + b is mul
[red green blue^2] [red blue^3] mul [red^2 green blue^5]
To combine, or add to a multiset:
[red green] [yellow] mul [red green yellow]
A bag can contain a negative amount of an item, extending the capabilities of the tropical multisets to easily remove items:
[red^3 green] [red^-1] mul [red^2 green]
To dive deeper, see Fractran, Bagel and Rejoice.
incoming: lunar arithmetic