Negafibonacci coding: Difference between revisions

Revision as of 22:15, 23 November 2024

Latest revision as of 16:25, 12 July 2025

(One intermediate revision by one other user not shown)

Line 5:

The following steps describe how to encode a nonzero integer <math> x </math>. Note that <math> f </math> denotes the Negafibonacci sequence.

# If <math> x </math> is positive, compute the greatest odd negative integer <math> n </math> such that the sum of the odd negative terms of the Negafibonacci sequence from -1−1 to <math> n </math> with a step of -2−2, is greater than or equal to <math> x </math>: <br /> <math> n \in \{ - \left( 2k + 1 \right) , k \in [0, \infty [ \} , \quad \sum_{i=-1, \; i \; odd}^{n-2} f(i) < x \leq \sum_{i=-1, \; i \; odd}^{n} f(i). </math> <br /> If <math> x </math> is negative, compute the greatest even negative integer <math> n </math> such that the sum of the even negative terms of the Negafibonacci sequence from 0 to <math> n </math> with a step of -2−2, is less than or equal to <math> x </math>: <br /> <math> n \in \{ - 2k , k \in [2, \infty [ \} , \quad \sum_{i=-2, \; i \; even}^{n-2} f(i) > x \geq \sum_{i=-2, \; i \; even}^{n} f(i) </math>

# Add a 1 at the <math> |n|^{\text{th}} </math> bit of the binary word. Subtract <math> f(n) </math> from <math> x </math>.

# Repeat the process from step 1 with the new value of ''x'', until it reaches 0.

# 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, −1, 2, −3, 5, −8, 13...), and sum the all the values associated with a 1.

== Negafibonacci representation ==

Line 96:

[[Category:Lossless compression algorithms]]

[[Category:Fibonacci numbers]]

[[Category:Data compression]]

[[fr:Codage de Fibonacci]]