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!

Feedback and suggestions are welcome so that dCode offers the best 'NegaFibonacci Encoding' tool for free! 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 "NegaFibonacci Encoding" source code. Except explicit open source licence (indicated Creative Commons / free), the "NegaFibonacci Encoding" algorithm, the applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or the "NegaFibonacci 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 "NegaFibonacci Encoding" are not public, same for offline use on PC, mobile, tablet, iPhone or Android app!
Reminder : dCode is free to use.

## Cite dCode

The copy-paste of the page "NegaFibonacci Encoding" or any of its results, is allowed as long as you cite dCode!
Cite as source (bibliography):
NegaFibonacci Encoding on dCode.fr [online website], retrieved on 2022-12-09, https://www.dcode.fr/negafibonacci-encoding

## Need Help ?

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