Choosing the Algebra

The rest of this series asks: given a structure, what algorithms does it support? This post inverts the question.

The Flip Side

The peasant post showed that power() works on any monoid. The semirings post showed that matrix multiplication over different semirings solves six graph problems. The thread running through the whole series is: algorithms arise from algebraic structure.

But there's a flip side that we haven't addressed directly.

Sometimes you're stuck with an expensive algorithm not because the problem is hard, but because you're working in the wrong algebra. Change the algebra, and the algorithm becomes trivial. The cost shows up somewhere else, always. But if the cheap operation is the one you actually need, you win.

This is a very old idea. Napier invented logarithms in 1614 to turn multiplication into addition. What's worth noticing is that logarithms, odds ratios, tropical semirings, and quaternions are all doing the same thing.

The Pattern

A computational basis transform takes values from one domain and represents them in another, where different operations are cheap:

Each row follows the same structure. A transform \(\varphi: D \to D'\) makes some operations cheaper and others more expensive. There is no free lunch.

This is not a deep theorem. It's almost tautological: if you could make everything cheaper by relabeling, the labels would already be the standard ones. But making the pattern explicit helps you recognize when you're paying for an operation you don't need.

Three Examples

Log Space

The most familiar example. You have a million small probabilities and need their product.

// Standard: underflows to 0 after ~30 terms
double product = 1.0;
for (double p : probs) product *= p;  // 0.0

// Log domain: addition instead of multiplication
mutatio::lgd product(1.0);
for (double p : probs) product = product * mutatio::lgd(p);
// product.log() is finite. product.value() would overflow,
// but you stay in log space.

The algebra changed from \((\mathbb{R}^+, \times)\) to \((\mathbb{R}, +)\). Multiplication became addition. The isomorphism is \(\log\).

Tropical Semirings

The semirings post showed this already. Replace \((+, \times)\) with \((\min, +)\) and matrix multiplication becomes shortest-path computation. That's the same move: you changed the semiring to make the algorithm you wanted (all-pairs shortest paths) fall out of a generic operation (matrix power) that you already had.

mutatio::tropical_min<double> a(3.0), b(5.0);
auto sum = a + b;   // min(3, 5) = 3
auto prod = a * b;  // 3 + 5 = 8

The semirings post covers why this works in more detail than I'll repeat here.

Odds Ratios

Bayesian inference in probability space requires normalization after every update. In odds space, it's just multiplication:

// Prior: 1% disease prevalence
auto prior = mutatio::odds_ratio<double>::from_probability(0.01);

// Positive test with likelihood ratio 18
auto posterior = prior * mutatio::odds_ratio<double>(18.0);

posterior.to_probability();  // ~15.4%

The transform \(p \mapsto p/(1-p)\) is a homomorphism from Bayesian updates to multiplication. Sequential updates compose by multiplying likelihood ratios. No normalization needed until you want a probability back.

Connection to the Series

The Stepanov perspective says: find the structure, then the algorithm follows. The flip side: if the algorithm you need is expensive in the current structure, maybe you're in the wrong one.

The modular arithmetic post already showed this implicitly. Working in \(\mathbb{Z}/p\mathbb{Z}\) instead of \(\mathbb{Z}\) gives you multiplicative inverses (when \(p\) is prime) and bounded arithmetic. The rational arithmetic post showed how working in \(\mathbb{Q}\) instead of floating point eliminates rounding error at the cost of GCD computation.

Those were choosing algebras too. This post just names the pattern.

The Library

The six transforms live in lib/mutatio in the stepanov repo. Header-only, like everything else in the series.

Logarithmic, odds ratio, Stern-Brocot rationals, tropical, modular, and quaternion. Each one follows the same interface pattern: construct from the base domain, operate cheaply in the transformed domain, convert back when needed.

This is not a production numerical library. Eigen does quaternions better. GMP does rationals better. The point is making the pattern visible, not replacing specialized tools.

#include <mutatio.hpp>  // All six transforms

What I Left Out

I originally tried to write an academic paper about this, complete with a "No Free Lunch theorem" and category-theoretic formalization. The theorem was trivially true and the formalism didn't add anything the pattern didn't already say. So I deleted it.

Some things are better as observations than as theorems. "Choose the algebra that makes your dominant operation cheap" is one of them.