# Fibonacci coding

July 6, 2022 - Reading time: ~1 minute

### Implementation

In :

``````
import functools

@functools.cache
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
``````

In :

``````
fib(42)
``````

Out :

``````
267914296
``````

In :

``````
@functools.cache
def largest_fib(target):
n = 2
while fib(n + 1) ``````

In :

``````
largest_fib(255)
``````

Out :

``````
(13, 233)
``````

In :

``````
@memoize
def encode_num(N):
digits, f = largest_fib(N)
encoded_bits =  * digits
while N:
n, f = largest_fib(N)
N = N - f
encoded_bits[digits-n-2] = 1
encoded_bits[-1] = 1
return encoded_bits
``````

### 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 :

``````
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 :

``````
compare(1, 256)
``````