NegaFibonacci coding
From Wikipedia, the free encyclopedia
| Numeral systems by culture | |
|---|---|
| Hindu-Arabic numerals | |
| Indian Eastern Arabic Khmer |
Indian family Brahmi Thai |
| East Asian numerals | |
| Chinese Suzhou Counting rods |
Japanese Korean |
| Alphabetic numerals | |
| Abjad Armenian Cyrillic Ge'ez |
Hebrew Greek (Ionian) Āryabhaṭa |
| Other systems | |
| Attic Babylonian Egyptian Etruscan |
Mayan Roman Urnfield |
| List of numeral system topics | |
| Positional systems by base | |
| Decimal (10) | |
| 2, 4, 8, 16, 32, 64 | |
| 1, 3, 9, 12, 20, 24, 30, 36, 60, more… | |
In mathematics, negaFibonacci coding is a universal code which encodes integers into binary code words. It is similar to Fibonacci coding, except that it allows both positive and negative integers to be represented. All codes end with "11" and have no "11" before the end. The code for the integers from -11 to 11 is given below:
xx negaFibonacci representation negaFibonacci code -11 101000 0001011 -10 101001 1001011 -9 100010 0100011 -8 100000 0000011 -7 100001 1000011 -6 100100 0010011 -5 100101 1010011 -4 1010 01011 -3 1000 00011 -2 1001 10011 -1 10 011 0 0 01 1 1 11 2 100 0011 3 101 1011 4 10010 010011 5 10000 000011 6 10001 100011 7 10100 001011 8 10101 101011 9 1001010 01010011 10 1001000 00010011 11 1001001 10010011
The Fibonacci code is closely related to negaFibonacci representation, a positional numeral system sometimes used by mathematicians. The negaFibonacci code for a particular 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.
To encode an integer X:
- Find the largest negafibonacci number with a value equal to or less than X; subtract this number from X, keeping track of the remainder.
- If the number we subtracted was the Nth unique negaFibonacci number, put a one in the Nth digit of our output.
- Repeat the previous steps, substituting our remainder for X, until we reach a remainder of 0.
- Place a one after the last naturally occurring one in our output.
To decode a token in the code, remove the last "1", assign the remaining bits the values -1,2,-3,5,-8,13... (the negafibonacci numbers), and add the "1" bits.
[edit] See also
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
