Tag archive
Integers modulo N form a ring, an algebraic structure that determines which algorithms apply. Understanding this structure unlocks algorithms from cryptography to competitive programming.
A homomorphism preserves structure. fold is the universal homomorphism from the free monoid. This is the algebraic reason that fold, evaluation, and parallelism work.
Iterators reduce the NxM algorithm-container problem to N+M by interposing an abstraction layer, following Stepanov's generic programming approach.
A semiring has two monoidal operations linked by distributivity. Matrix multiplication over different semirings gives shortest paths, longest paths, widest paths, reachability, and path counting, all from the same code.
Rational numbers give exact arithmetic where floating-point fails. The implementation connects GCD, the Stern-Brocot tree, and the algebraic structure of fields.
Codecs are not ad-hoc bit formats. They are constructions on the algebraic structure of types.
The free monoid on a set is the type of lists over that set. The universal property says fold is the unique homomorphism from lists to any monoid. This explains why lists, multisets, and polynomials appear everywhere.
Prefix-freeness is the property that lifts the free-monoid construction into bit space.
What if containers wasted zero bits? A C++ library for packing arbitrary value types at the bit level using pluggable codecs.
Online accumulators are monoids. Default construction is the identity, combination via += is the binary operation, and parallel composition gives the product monoid, computing arbitrary statistics in a single pass.
The Russian peasant algorithm computes products, powers, Fibonacci numbers, and more, once you see the underlying algebraic structure.
A lattice has two operations, meet and join, satisfying absorption laws. Tarski's theorem gives a generic fixed-point algorithm. Lattice structure determines the iteration, just as monoid structure determines power-by-squaring.