Non-adjacent form
Encyclopedia
The non-adjacent form (NAF) of a number is a unique signed-digit representation
. Like the name suggests, non-zero values cannot be adjacent. For example:
2 = 4 + 2 + 1 = 72 = 8 − 2 + 1 = 72 = 8 − 4 + 2 + 1 = 72 = 8 − 1 = 7
All are valid signed-digit representations of 7, but only the final representation (1 0 0 −1) is in NAF.
of the value will be minimal. For regular binary
representations of values, half of all bit
s will be non-zero, on average, but with NAF this drops to only one-third of all digits.
Obviously, at most half of the digits are non-zero, which was the reason it was introduced by G.W. Reitweisner in 1960 for speeding up early multiplication algorithms, much like Booth encoding.
Because every non-zero value has to be adjacent to two 0's, the NAF representation can be implemented such that it only takes a maximum of m + 1 bits for a value that would normally be represented in binary with m bits.
The properties of NAF make it useful in various algorithms, especially some in cryptography
, e.g., for reducing the number of multiplications needed for performing an exponentiation
. In the algorithm exponentiation by squaring
the number of multiplications depends on the number of non-zero bits. If the exponent here is given in NAF form a digit value 1 implies a multiplication by the base, and a digit value -1 by its reciprocal.
Signed-digit representation
Signed-digit representation of numbers indicates that digits can be prefixed with a − sign to indicate that they are negative.Signed-digit representation can be used in low-level software and hardware to accomplish fast addition of integers because it can eliminate carries...
. Like the name suggests, non-zero values cannot be adjacent. For example:
2 = 4 + 2 + 1 = 72 = 8 − 2 + 1 = 72 = 8 − 4 + 2 + 1 = 72 = 8 − 1 = 7
All are valid signed-digit representations of 7, but only the final representation (1 0 0 −1) is in NAF.
Obtaining NAF
There are several algorithms for obtaining the NAF representation of a value given in binary. One such is the following method using repeated division; it works by choosing non-zero coefficients such that the resulting quotient is divisible by 2 and hence the next coefficient a zero.- Input: E = (em − 1 em − 2 ··· e1 e0)2
- Output: E = (zm zm − 1 ··· z1 z0)NAF
- i ← 0
- while E > 0 do
- if E is odd then
- zi ← 2 − (E mod 4)
- else
- zi ← 0
- E ← (E − zi)/2
- i ← i + 1
- if E is odd then
- return z
Properties
NAF assures a unique representation of an integer, but the main benefit of it is that the Hamming weightHamming weight
The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a string of bits, this is the number of 1's in the string...
of the value will be minimal. For regular binary
Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
representations of values, half of all bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
s will be non-zero, on average, but with NAF this drops to only one-third of all digits.
Obviously, at most half of the digits are non-zero, which was the reason it was introduced by G.W. Reitweisner in 1960 for speeding up early multiplication algorithms, much like Booth encoding.
Because every non-zero value has to be adjacent to two 0's, the NAF representation can be implemented such that it only takes a maximum of m + 1 bits for a value that would normally be represented in binary with m bits.
The properties of NAF make it useful in various algorithms, especially some in cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, e.g., for reducing the number of multiplications needed for performing an exponentiation
Exponentiation
Exponentiation is a mathematical operation, written as an, involving two numbers, the base a and the exponent n...
. In the algorithm exponentiation by squaring
Exponentiation by squaring
Exponentiating by squaring is a general method for fast computation of large integer powers of a number. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. In additive notation the appropriate term is double-and-add...
the number of multiplications depends on the number of non-zero bits. If the exponent here is given in NAF form a digit value 1 implies a multiplication by the base, and a digit value -1 by its reciprocal.