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

NegaFibonacci Encoding - dCode

Tag(s) : Compression, Mathematics

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*!

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

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 $

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

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.

Please, check our dCode Discord community for help requests!

NB: for encrypted messages, test our automatic cipher identifier!

negafibonacci,fibonacci,coding,binary,compression

Source : https://www.dcode.fr/negafibonacci-encoding

© 2021 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaching / CTF.

Feedback

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