Fibonacci Coding

I have recently been looking into different encoding schemes, and just be chance, came across Fibonacci Encoding. Although I think the usefulness of Fibonacci encoding is limited, it is – mathematically speaking – quite interesting.

Fibonacci encoding of positive integers is an interesting encoding method that uses the fact (theory) that any positive integer can be written uniquely as the sum of fibonacci numbers where no two numbers in the summand are consecutive.
As an example, let’s consider the following integers 2,6,8,20.

Well, 2 is a fibonacci number itself, so we don’t need to do anything. We need to express the encoding as a binary string with zeros representing fibonacci numbers not in the summand, and 1 representing fibonacci number in the summand. So 2 can become

01

Similarly,

6 = 1+5 = 1001;

8 = 8 = 00001;

20 = 2 + 5 + 13 = 010101.

Notice, that no two 1’s are consecutive in any of the above encodings. This is important as we can use two consecutive 1’s to denote the end of one encoding and the beginning of another. That way, we can pack the integer encodings into a single byte stream, to more efficiently pack the bytes.

For instance, if we want to encode the number 7 and 11:

First, note that 7 = 2 + 5 = 01011, and 11 = 3 + 8 = 001011;
So we can concatenat the encodings, using 5 +6 = 11 bits, to get 01011001011;
As we want to put the encodings into bytes we pad with zeros up to the nearest multiple of 8, to get 0101100101100000.

Here, we have encoded two integers using 2 bytes.
Let’s have a look at one implementation of encoding and decoding, in the J language.
First, we need to generate Fibonacci numbers. This is an easy verb to write:

genfibs=: 3 : 0
r=. 1 2
i1=. 1
i2=. 2
c=. 2
while. y > c=. c+1 do.
  t=. i1 + i2
  i1=. i2
  i2=. t
  r=. r, x: t
end.
)


Fibs=: genfibs 1400

With Fibs, we have a list of the first 1400 Fibonacci numbers, where we define the first two as “1, 2”. ie. we ignore the “1,1” first 1.

Let’s encode:

encode=: 3 : 0
d=. > (>@:,&:>)/ (<@encode1)"0 y
r=. d,'0' #~ (#d) -~ 8 * >. 8 %~ # d
pack r
)

encode1=: 3 : 0
n=. x: y
r=. ''
k=: ''
fl=. x: Fibs{~ I. Fibs <: y
i=. <:#fl
while. n do.
  r=. r,'1'
  n=. n - i{fl
  k=: k,i{fl
  i=. i-1
  while. (i >: 0) *. (n<i{fl) do.
    r=. r,'0'
    i=. i-1
  end.
end.
(|.r),'1'
)

pack=: 3 : 0
a.{~ #. _8 ] \"."0 y
)

Here we have 3 verbs:

1. encode
2. encode1
3. pack

encode1 will encode a single positive integer into the Fibonacci representation. Example:

encode 3452
101000100001010011

Here, the result ing representation is a string literal, for the sake of readability. The encoding is “101000100001010011”. Note the final “11”, denoting the delimitation of this encoding.

The verb “encode” and “pack” are used to encode multiple integers to a single output.

#: a.i. encode 10 11 12 13 14
L���

The result is not readable just 4 bytes. We can read the bits:

#: a.i. encode 10 11 12 13 14
0 1 0 0 1 1 0 0
1 0 1 1 1 0 1 0
1 1 0 0 0 0 0 1
1 1 0 0 0 0 1 1

As you can see, this encoding of 4 integers results in a 4 byte encoding. Not bad, compression.

What about decoding? Once encoded, we would like to get the original integer(s) back again. Here is the “decode” verb which operates an a single byte array.

decode=: 3 : 0
i=. , #: a.i. y
n=. ''
while. 1 e. 1 1 E. i do.
  idx=. {. I. 1 1 E. i
  n=. n, +/ Fibs {~ I. i {~ i. >: idx
  i=. (2+idx) }. i
end.
n
)

An example:

decode encode 10 11 12 13 14
10 11 12 13 14

The encoding and decoding works perfectly, as long as the input are positive integers.

We now have our encoded integer array, but would want to represent as a string, so we can encode the bytes further using (for example) base-64 encoding. Note that base-64 encoding will increase the byte count by 1.33.

load 'convert/misc/base64'
]str=: tobase64 encode 10 100 300
TKHUTA==

]nums=: decode frombase64 str
10 100 300

That worked very well. Note that we can this for very large integers too.

require 'convert/misc/base64'
enc =: encode 22338938348348348357675630030349235752291183838232x
# enc
30  NB. encoded a 164-bit (~ 20 bytes) integer with 30 bytes
str=: tobase64 enc
decode frombase64 str 
22338938348348348357675630030349235752291183838232 NB. get the original input.

This was an interesting exercise and might be worth rewriting in other languages.
The encoder and decoder were very easy to write (especially in J), so this probably wouldn’t take too long in another language. I will put it on my to-do list.

The entirety of the source code:

genfibs=: 3 : 0
r=. 1 2
i1=. 1
i2=. 2
c=. 2
while. y > c=. c+1 do.
  t=. i1 + i2
  i1=. i2
  i2=. t
  r=. r, x: t
end.
)


Fibs=: genfibs 1400

encode=: 3 : 0
d=. > (>@:,&:>)/ (<@encode1)"0 y
r=. d,'0' #~ (#d) -~ 8 * >. 8 %~ # d
pack r
)

encode1=: 3 : 0
n=. x: y
r=. ''
k=: ''
fl=. x: Fibs{~ I. Fibs <: y
i=. <:#fl
while. n do.
  r=. r,'1'
  n=. n - i{fl
  k=: k,i{fl
  i=. i-1
  while. (i >: 0) *. (n<i{fl) do.
    r=. r,'0'
    i=. i-1
  end.
end.
(|.r),'1'
)



pack=: 3 : 0
a.{~ #. _8 ] \"."0 y
)

decode=: 3 : 0
i=. , #: a.i. y
n=. ''
while. 1 e. 1 1 E. i do.
  idx=. {. I. 1 1 E. i
  n=. n, +/ Fibs {~ I. i {~ i. >: idx
  i=. (2+idx) }. i
end.
n
)

Useful links:
Fibonacci coding
Zeckendorf’s theorem

Leave a Reply Cancel reply