Search for a tool
Fibonacci Encoding

Tool for encoding/decoding numbers using Fibonacci encoding (binary words never having two consecutive 1 values)

Results

Fibonacci Encoding -

Tag(s) : Compression, Mathematics

Share
dCode and more

dCode is free and its tools are a valuable help in games, maths, geocaching, puzzles and problems to solve every day!
A suggestion ? a feedback ? a bug ? an idea ? Write to dCode!

Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!

Thanks to your feedback and relevant comments, dCode has developed the best 'Fibonacci Encoding' tool, so feel free to write! Thank you!

# Fibonacci Encoding

## Number to Fibonacci Coding Encoder

 Mode Fibonacci encoding (N>0) Negafibonacci encoding (N ∈ ℤ)

## Fibonacci Code to Numbers Decoder

 Mode Fibonacci encoding (N>0) Negafibonacci encoding (N ∈ ℤ)

### How to encode using Fibonacci encoding?

The Fibonacci code uses the Zeckendorf theorem (and Zeckendorf's representation of a number) which states that any integer can be written as the sum of non-consecutive Fibonacci numbers.

$$n = \sum_{i=1}^{k} \beta_i F_{i}$$

The Fibonnacci coding consists in noting the coefficients $\beta_i$ (being 0 or 1) to make a binary number.

Example: $123$ is the sum of $F_{11} = 89$ and $F_{9} = 34$ or 1010000000 in binary (the two 1 are in position 8 and 10 starting from the right).

As the Zeckendorf representation never has 2 consecutive Fibonnacci numbers, the binary value will never have 2 times the number 1 consecutively.

### How to decode Fibonacci encoding?

Each 1 of the binary word corresponds to a Fibonacci number, to find the decimal number, add all the Fibonacci numbers corresponding to the 1 of the binary word.

Example: 10100 corresponds to $1 \times F_5 + 0 \times F_4 + 0 \times F_3 + 1 \times F_2 + 0 \times F_1 = F_5 + F_3 = 8 + 3 = 11$

### What are the variants of the Fibonacci encoding?

A variant of Zeckendorf's theorem indicates that it is also possible to write any integer as the sum of non-consecutive Nega-Fibonacci (Generalization of Fibonnacci with negative indices) numbers, this encoding is called NegaFibonacci encoding.

## Source code

dCode retains ownership of the "Fibonacci Encoding" source code. Except explicit open source licence (indicated Creative Commons / free), the "Fibonacci Encoding" algorithm, the applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or the "Fibonacci Encoding" functions (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and all data download, script, or API access for "Fibonacci Encoding" are not public, same for offline use on PC, tablet, iPhone or Android !
The copy-paste of the page "Fibonacci Encoding" or any of its results, is allowed as long as you cite the online source https://www.dcode.fr/fibonacci-encoding
Reminder : dCode is free to use.

## Need Help ?

Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!