Search for a tool
NegaFibonacci Encoding

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

Results

NegaFibonacci 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 'NegaFibonacci Encoding' tool, so feel free to write! Thank you!

# NegaFibonacci Encoding

## NegaFibonacci Code to Numbers Decoder

### How to encode using NegaFibonacci encoding?

The NegaFibonacci code uses a variant of Zeckendorf's theorem which states that any integer (relative) can be written as the sum of non-consecutive generalized (positive or negative) Fibonnacci numbers.

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

(note the negative index $i$) with $\beta_i$ (equal to 0 or 1)

Example: $12$ is the sum of $F_{-7} = 13$ and $F_{-2} = -1$ or 1000010 in binary (the two 1 are in position 7 and 2 starting from the right).

This representation similar to Zeckendorf never has 2 consecutive Fibonnacci numbers and therefore the binary value never has 2 consecutive digit 1.

### How to decode NegaFibonacci encoding?

Each 1 of the binary word corresponds to a NegaFibonacci number (number of the Fibonacci sequence generalized to negative numbers). So, to calculate the original decimal number, add all the NegaFibonacci 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} = 5 + 2 = 7$

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

NegaFibonacci encoding is already a variant of Fibonacci encoding. It has the advantage of being generalizable to relative numbers (positive or negative integers).

## Source code

dCode retains ownership of the online "NegaFibonacci Encoding" tool source code. Except explicit open source licence (indicated CC / Creative Commons / free), any "NegaFibonacci Encoding" algorithm, applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any "NegaFibonacci Encoding" function (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and no data download, script, copy-paste, or API access for "NegaFibonacci Encoding" will be for free, same for offline use on PC, tablet, iPhone or Android ! dCode is free and online.

## Need Help ?

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