// Elias Delta - More efficient universal code than Gamma for larger integers
More efficient than Elias Gamma for integers > 3.
Works for any positive integer without parameters.
Uses log₂(n) + 2log₂(log₂(n)) + 1 bits.
Elias Delta encodes positive integer n in three parts: 1) Find L = floor(log₂(n)) + 1 (bit length), 2) Encode L using Elias Gamma, 3) Append the last L-1 bits of n. This double logarithmic growth makes it more efficient than Gamma for larger numbers while remaining universal.
n=1: L=1, Gamma(1)='1', bits='', Delta='1' n=2: L=2, Gamma(2)='010', bits='0', Delta='0100' n=3: L=2, Gamma(2)='010', bits='1', Delta='0101' n=4: L=3, Gamma(3)='011', bits='00', Delta='01100' n=16: L=5, Gamma(5)='00101', bits='0000', Delta='001010000' Compare lengths: n | Gamma | Delta | Savings 1 | 1 | 1 | 0 16 | 9 | 9 | 0 100 | 13 | 12 | 1 1000 | 19 | 16 | 3
Elias Delta is an improvement over Elias Gamma that encodes the length of a number using Gamma encoding, then appends the remaining bits. It uses approximately log₂(n) + 2log₂(log₂(n)) + 1 bits, making it more efficient for larger integers.
Gamma uses 2⌊log₂(n)⌋ + 1 bits while Delta uses log₂(n) + 2log₂(log₂(n)) + 1 bits. Delta is better for n > 3, with savings increasing for larger numbers. For very small numbers (1-3), they're comparable.
Use Delta when your data contains mostly integers > 3. For very small integers (1-2), Gamma might be slightly better. For very large integers, consider Elias Omega which improves further on Delta.
Delta is middle ground. Gamma is simplest but least efficient. Delta improves compression. Omega is best for very large numbers but most complex. Choose based on your data distribution and implementation constraints.