Negafibonacci coding

Last updated December 06, 2024

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

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

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$ :
$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).$
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$ :
$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)$
Add a 1 at the $|n|^{\text{th}}$ bit of the binary word. Subtract $f(n)$ from $x$ .
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, 2, −3, 5, −8, 13...), and sum the all the values associated with a 1.

Negafibonacci representation

Negafibonacci 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

The 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

Related Research Articles

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers, the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements . It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.

In mathematics, the Fibonacci sequence is a sequence in which each number is the sum of the two preceding ones. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted $F n$ . Many writers begin the sequence with 0 and 1, although some authors start it from 1 and 1 and some from 1 and 2. Starting from 0 and 1, the sequence begins

In mathematics, the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers $x$ , $y$ , the greatest common divisor of $x$ and $y$ is denoted $. For example, the GCD of 8 and 12 is 4, that is, gcd(8, 12) = 4 .$

In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members. The number of elements is called the length of the sequence. Unlike a set, the same elements can appear multiple times at different positions in a sequence, and unlike a set, the order does matter. Formally, a sequence can be defined as a function from natural numbers to the elements at each position. The notion of a sequence can be generalized to an indexed family, defined as a function from an arbitrary index set.

In mathematics and computing, Fibonacci coding is a universal code which encodes positive integers into binary code words. It is one example of representations of integers based on Fibonacci numbers. Each code word ends with "11" and contains no other instances of "11" before the end.

Elias $code$ or Elias gamma code is a universal code encoding positive integers developed by Peter Elias. It is used most commonly when coding integers whose upper-bound cannot be determined beforehand.

Golden ratio base is a non-integer positional numeral system that uses the golden ratio as its base. It is sometimes referred to as base-φ, golden mean base, phi-base, or, colloquially, phinary. Any non-negative real number can be represented as a base-φ numeral using only the digits 0 and 1, and avoiding the digit sequence "11" – this is called a standard form. A base-φ numeral that includes the digit sequence "11" can always be rewritten in standard form, using the algebraic properties of the base φ — most notably that φ^$n$ + φ^{$n -1$} = φ^{$n +1$}. For instance, 11_φ = 100_φ.

Golomb coding is a lossless data compression method using a family of data compression codes invented by Solomon W. Golomb in the 1960s. Alphabets following a geometric distribution will have a Golomb code as an optimal prefix code, making Golomb coding highly suitable for situations in which the occurrence of small values in the input stream is significantly more likely than large values.

In mathematics, a square number or perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 9 is a square number, since it equals $32$ and can be written as $3 \times 3$ .

A power of two is a number of the form $2 n$ where $n$ is an integer, that is, the result of exponentiation with number two as the base and integer $n$ as the exponent.

In mathematics, Zeckendorf's theorem, named after Belgian amateur mathematician Edouard Zeckendorf, is a theorem about the representation of integers as sums of Fibonacci numbers.

Bijective numeration is any numeral system in which every non-negative integer can be represented in exactly one way using a finite string of digits. The name refers to the bijection that exists in this case between the set of non-negative integers and the set of finite strings using a finite set of symbols.

In number theory, an odious number is a positive integer that has an odd number of 1s in its binary expansion. Non-negative integers that are not odious are called evil numbers.

In mathematics, the Fibonacci numbers form a sequence defined recursively by:

A negative base may be used to construct a non-standard positional numeral system. Like other place-value systems, each position holds multiples of the appropriate power of the system's base; but that base is negative—that is to say, the base $b$ is equal to $-r$ for some natural number $r$ .

In arithmetic, a complex-base system is a positional numeral system whose radix is an imaginary or complex number.

In mathematics, a sequence of natural numbers is called a complete sequence if every positive integer can be expressed as a sum of values in the sequence, using each value at most once.

In number theory, the Moser–de Bruijn sequence is an integer sequence named after Leo Moser and Nicolaas Govert de Bruijn, consisting of the sums of distinct powers of 4. Equivalently, they are the numbers whose binary representations are nonzero only in even positions.

In mathematics, the fibbinary numbers are the numbers whose binary representation does not contain two consecutive ones. That is, they are sums of distinct and non-consecutive powers of two.

References

Works cited

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.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.