// Elias Omega - Asymptotically optimal code for arbitrarily large integers
Approaches theoretical minimum for large integers.
Elegantly encodes length of length recursively.
Works for any positive integer without parameters.
Elias Omega recursively encodes the length of a number until reaching 1. Starting with n, it encodes log₂(n), then log₂(log₂(n)), continuing until reaching 1. The code consists of these values in reverse order, terminated by 0. This achieves log(n) + log(log(n)) + log(log(log(n))) + ... bits.
n=16: 16 → binary: 10000 (length 5) 5 → binary: 101 (length 3) 3 → binary: 11 (length 2) 2 → binary: 10 (length 2) 1 → stop Build code backwards: Start with 0 (terminator) Prepend 10 (encodes 2) Prepend 11 (encodes 3) Prepend 101 (encodes 5) Prepend 10000 (encodes 16) Result: 10 11 101 10000 0 Compare efficiency: n=100: Gamma=13, Delta=12, Omega=10 bits n=1000: Gamma=19, Delta=16, Omega=14 bits
Elias Omega is the most sophisticated Elias code, using recursive length encoding to achieve asymptotic optimality. It encodes each length using the previous length, continuing until reaching 1, creating the most efficient code for very large integers.
For small numbers (< 10), Gamma is often best. For medium numbers (10-1000), Delta improves on Gamma. For large numbers (> 1000), Omega becomes increasingly superior. Omega uses log*(n) iterations, achieving optimal asymptotic behavior.
A code is asymptotically optimal if the ratio of its length to the theoretical minimum approaches 1 as numbers grow large. Omega achieves this: length(n)/log₂(n) → 1 as n → ∞.
Despite theoretical superiority, Omega is complex to implement and decode. For practical data with bounded integers, simpler codes like Exp-Golomb or Rice often perform better. Omega shines in theoretical analysis and unbounded integer scenarios.