Negafibonacci coding: Difference between revisions

Revision as of 05:27, 4 November 2011

Revision as of 08:59, 5 November 2011

Line 33:

To encode an integer ''X'':

# FindCalculate the largest [[negafibonacci]](or smallest) encodeable number with a''N'' valuebits equalby tosumming the odd (or lesseven) than[[negafibonacci]] ''X'';numbers subtractfrom this1 number fromto ''XN'', keeping track of the remainder.

# IfWhen theit numberis wedetermined subtractedthat was''N'' bits is just enough to contain the ''NX''th, uniquesubtract the ''Nth'' negaFibonacci number from ''X'' , keeping track of the remainder, and put a one in the ''NNth''th digitbit of ourthe output.

# 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 closer to zero, 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.

# Repeat the previous steps, substituting our remainder for ''X'', until we reach a remainder of 0.

# PlacePut a one afterin the last''N+1th'' naturally occurring one inbit ourto outputfinish.

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.