Negafibonacci coding: Difference between revisions

Revision as of 01:40, 24 October 2023

Revision as of 21:53, 23 November 2024

Line 2:

== Encoding method ==

{{How-to|section|date=September 2022}}

To encode a nonzero integer ''X'':

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

# Calculate the largest (or smallest) encodeable number with ''N'' bits by summing the odd (or even) negafibonacci numbers from 1 to ''N''.

# When it is determined that ''N'' bits is just enough to contain ''X'', subtract the ''Nth'' negafibonacci number from ''X'', keeping track of the remainder, and put a one in the ''Nth'' bit of the output.

# 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'': <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> 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'': <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>

# Working downward from the ''Nth'' bit to the first one, compare each of the corresponding negafibonacci numbers to the remainder. Subtract it from the remainder if the absolute value of the difference is less, AND if the next higher bit does not already have a one in it. A one is placed in the appropriate bit if the subtraction is made, or a zero if not.

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

# Put a one in the ''N+1th'' bit to finish.

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

# Add a 1 at the beginning of the resulting binary word to finish the encoding.

To decode a token in the code, remove the last "1", assign the remaining bits the values 1, −1, 2, −3, 5, −8, 13... (the negafibonacci numbers), and add the "1" bits.