Negafibonacci coding

The following steps describe how to encode a nonzero integer $x$. Note that $f$ denotes the Negafibonacci sequence.

1. If $x$ is positive, compute the greatest odd negative integer $n$ such that the sum of the odd negative terms of the Negafibonacci sequence from -1 to $n$ with a step of -2, is greater than or equal to $x$:
   
   If $x$ is negative, compute the greatest even negative integer $n$ such that the sum of the even negative terms of the Negafibonacci sequence from 0 to $n$ with a step of -2, is less than or equal to $x$:
   $n\; \backslash in\; \backslash \{\; -\; 2k\; ,\; k\; \backslash in\; [2,\; \backslash infty\; [\; \backslash \}\; ,\; \backslash quad\; \backslash sum\_\{i=-2,\; \backslash ;\; i\; \backslash ;\; even\}^\{n-2\}\; f(i)\; >\; x\; \backslash geq\; \backslash sum\_\{i=-2,\; \backslash ;\; i\; \backslash ;\; even\}^\{n\}\; f(i)$
2. Add a 1 at the $|n|^\{\backslash text\{th\}\}$ bit of the binary word. Subtract $f(n)$ from $x$.
3. Repeat the process from step 1 with the new value of x, until it reaches 0.
4. Add a 1 on the left of the resulting binary word to finish the encoding.

To decode an encoded binary word, remove the leftmost 1 from the binary word, since it is used only to denote the end of the encoded number. Then assign the remaining bits the values of the Negafibonacci sequence from -1 (1, −1, 2, −3, 5, −8, 13...), and sum the all the values associated with a 1.

{{numeral systems}}

Negafibonacci coding is closely related to negafibonacci representation, a positional numeral system sometimes used by mathematicians. The negafibonacci code for a particular nonzero integer is exactly that of the integer's negafibonacci representation, except with the order of its digits reversed and an additional "1" appended to the end. The negafibonacci code for all negative numbers has an odd number of digits, while those of all positive numbers have an even number of digits.

The code for the integers from −11 to 11 is given below.

• Fibonacci numbers
• Golden ratio base
• Zeckendorf's theorem

{{No footnotes|date=September 2022}}

{{Reflist}}

{{Refbegin}}

• {{Cite conference |last=Knuth |first=Donald |year=2008 |title=Negafibonacci Numbers and the Hyperbolic Plane |conference=Annual meeting of the Mathematical Association of America |location=San Jose, California}}
• {{Cite book |last=Knuth |first=Donald |title=The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams |year=2009 |publisher=Addison-Wesley |isbn=978-0-321-58050-4}} In the [https://www-cs-faculty.stanford.edu/~uno/fasc1a.ps.gz pre-publication draft of section 7.1.3] see in particular pp. 36–39.
• {{Cite book |last=Margenstern |first=Maurice |url=https://books.google.com/books?id=eEgvfic3A4kC&pg=PA79 |title=Cellular Automata in Hyperbolic Spaces |publisher=Archives contemporaines |year=2008 |isbn=9782914610834 |series=Advances in unconventional computing and cellular automata |volume=2 |page=79}}

{{Refend}}

{{Compression Methods}}

{{DEFAULTSORT:Negafibonacci Coding}}

Category:Non-standard positional numeral systems

Category:Lossless compression algorithms

Category:Fibonacci numbers

Category:Data compression

fr:Codage de Fibonacci