Fibonacci coding.
In [2]:
@memoize def fib(n): if n < 2: return n return fib(n - 1) + fib(n - 2)
In [3]:
fib(42)
Out [3]:
267914296
In [4]:
@memoize def largest_fib(target): n = 2 while fib(n + 1) <= target: n += 1 return n, fib(n)
In [5]:
largest_fib(255)
Out [5]:
(13, 233)
In [6]:
@memoize def encode_num(N): digits, f = largest_fib(N) encoded_bits = [0] * digits while N: n, f = largest_fib(N) N = N - f encoded_bits[digits-n-2] = 1 encoded_bits[-1] = 1 return encoded_bits
Useful links and references
- Fibonacci coding on Wikipedia
Appendix A: Comparisons
Let’s compare Fibonacci coding with the baseline and some common solutions. We can plot how many bits are required as the number we encode grows.
In [7]:
def compare(low, high): plt.plot([len(encode_num(x)) for x in range(low, high)], label="Fibonacci") plt.plot([len(varint(x)) * 8 for x in range(low, high)], label="varint") plt.plot([math.ceil(math.log(x, 2)) for x in range(low, high)], label="Direct binary") plt.legend()
In [8]:
compare(1, 256)
Out:
In [9]:
compare(1, 8196)
Out:
