In mathematics, negafibonacci coding is a universal code which encodes nonzero 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.
Encoding method
editThis section contains instructions, advice, or how-to content. (September 2022) |
To encode a nonzero integer X:
- 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.
- 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.
- Put a one in the N+1th bit to finish.
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.
Negafibonacci representation
editNegafibonacci 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.
Table
editThe code for the integers from −11 to 11 is given below.
| Number | 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 | (cannot be encoded) |
| 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 |
See also
editReferences
editThis article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (September 2022) |
Works cited
edit- Knuth, Donald (2008). Negafibonacci Numbers and the Hyperbolic Plane. Annual meeting of the Mathematical Association of America. San Jose, California.
- Knuth, Donald (2009). The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams. Addison-Wesley. ISBN 978-0-321-58050-4. In the pre-publication draft of section 7.1.3 see in particular pp. 36–39.
- Margenstern, Maurice (2008). Cellular Automata in Hyperbolic Spaces. Advances in unconventional computing and cellular automata. Vol. 2. Archives contemporaines. p. 79. ISBN 9782914610834.