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

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:
<Figure size 900x600 with 1 Axes>
In [9]:
compare(1, 8196)
Out:
<Figure size 900x600 with 1 Axes>