The non-adjacent form (NAF) of a number is a unique
signed-digit representation
In mathematical notation for numbers, a signed-digit representation is a positional numeral system with a set of signed digits used to encode the integers.
Signed-digit representation can be used to accomplish fast addition of integers because ...
, in which non-zero values cannot be adjacent. For example:
:(0 1 1 1)
2 = 4 + 2 + 1 = 7
:(1 0 −1 1)
2 = 8 − 2 + 1 = 7
:(1 −1 1 1)
2 = 8 − 4 + 2 + 1 = 7
:(1 0 0 −1)
2 = 8 − 1 = 7
All are valid signed-digit representations of 7, but only the final representation, (1 0 0 −1), is in non-adjacent form.
The non-adjacent form is also known as "canonical signed digit" representation.
Properties
NAF assures a unique representation of an
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
, but the main benefit of it is that the
Hamming 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 o ...
of the value will be minimal. For regular
binary
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two digits (0 and 1)
* Binary function, a function that takes two arguments
* Binary operation, a mathematical operation that t ...
representations of values, half of all
bit
The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represente ...
s will be non-zero, on average, but with NAF this drops to only one-third of all digits. This leads to efficient implementations of add/subtract networks (e.g. multiplication by a constant) in hardwired
digital signal processing
Digital signal processing (DSP) is the use of digital processing, such as by computers or more specialized digital signal processors, to perform a wide variety of signal processing operations. The digital signals processed in this manner are ...
.
Obviously, at most half of the digits are non-zero, which was the reason it was introduced by G.W. Reitweisner
for speeding up early multiplication algorithms, much like
Booth encoding
Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation. The algorithm was invented by Andrew Donald Booth in 1950 while doing research on crystallography at Birkbeck ...
.
Because every non-zero digit has to be adjacent to two 0s, 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, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
; e.g., for reducing the number of multiplications needed for performing an
exponentiation
Exponentiation is a mathematical operation, written as , involving two numbers, the '' base'' and the ''exponent'' or ''power'' , and pronounced as " (raised) to the (power of) ". When is a positive integer, exponentiation corresponds to re ...
. In the algorithm,
exponentiation by squaring
Exponentiation is a mathematical operation, written as , involving two numbers, the '' base'' and the ''exponent'' or ''power'' , and pronounced as " (raised) to the (power of) ". When is a positive integer, exponentiation corresponds to re ...
, 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.
Other ways of encoding integers that avoid consecutive 1s include
Booth encoding
Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation. The algorithm was invented by Andrew Donald Booth in 1950 while doing research on crystallography at Birkbeck ...
and
Fibonacci coding
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 ...
.
Converting to 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'' = (''e''
''m''−1 ''e''
''m''−2 ··· ''e''
1 ''e''
0)
2
Output ''Z'' = (''z''
''m'' ''z''
''m''−1 ··· ''z''
1 ''z''
0)
NAF
''i'' ← 0
while ''E'' > 0 do
if ''E'' is odd then
''z''
''i'' ← 2 − (''E'' mod 4)
''E'' ← ''E'' − ''z''
''i''
else
''z''
''i'' ← 0
''E'' ← ''E''/2
''i'' ← ''i'' + 1
return ''z''
A faster way is given by Prodinger
where ''x'' is the input, ''np'' the string of positive bits and ''nm'' the string of negative bits:
Input ''x''
Output ''np'', ''nm''
''xh'' = ''x'' >> 1;
''x3'' = ''x'' + ''xh'';
''c'' = ''xh'' ^ ''x3'';
''np'' = ''x3'' & ''c'';
''nm'' = ''xh'' & ''c'';
which is used, for example, in .
External links
Introduction to Canonical Signed Digit Representation*
References
{{DEFAULTSORT:Non-Adjacent Form
Non-standard positional numeral systems