Non-adjacent form

Last updated

The non-adjacent form (NAF) of a number is a unique signed-digit representation, in which non-zero values cannot be adjacent. For example:

Contents

(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)2, 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, but the main benefit of it is that the Hamming weight of the value will be minimal. For regular binary representations of values, half of all bits 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. [1]

Obviously, at most half of the digits are non-zero, which was the reason it was introduced by G.W. Reitweisner [2] for speeding up early multiplication algorithms, much like Booth encoding.

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; 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.

Other ways of encoding integers that avoid consecutive 1s include Booth encoding and Fibonacci coding.

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. [3] 

InputE = (em−1em−2 ··· e1e0)2OutputZ = (zmzm−1 ··· z1z0)NAFi ← 0    while E > 0 do        if E is odd then            zi ← 2 − (E mod 4)            E ← E − zi        else            zi ← 0        E ← E/2        i ← i + 1    return z

A faster way is given by Prodinger [4] where x is the input, np the string of positive bits and nm the string of negative bits:

InputxOutputnp, nmxh = x >> 1;    x3 = x + xh;    c = xh ^ x3;    np = x3 & c;    nm = xh & c;

which is used, for example, in A184616.

Related Research Articles

<span class="mw-page-title-main">Binary-coded decimal</span> System of digitally encoding numbers

In computing and electronic systems, binary-coded decimal (BCD) is a class of binary encodings of decimal numbers where each digit is represented by a fixed number of bits, usually four or eight. Sometimes, special bit patterns are used for a sign or other indications.

In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number, or more generally of an element of a semigroup, like a polynomial or a square matrix. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. These can be of quite general use, for example in modular arithmetic or powering of matrices. For semigroups for which additive notation is commonly used, like elliptic curves used in cryptography, this method is also referred to as double-and-add.

<span class="mw-page-title-main">Floating-point arithmetic</span> Computer approximation for real numbers

In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can be represented as a base-ten floating-point number:

<span class="mw-page-title-main">Modular arithmetic</span> Computation modulo a fixed integer

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" (zero) and "1" (one).

Two's complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with equivalent value, using the binary digit with the greatest place value to indicate whether the binary number is positive or negative. It is used in computer science as the most common method of representing signed integers on computers, and more generally, fixed point binary values. When the most significant bit is a one, the number is signed as negative. (see Converting from two's complement representation, below).

<span class="mw-page-title-main">Power of two</span> Two raised to an integer power

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

The IEEE Standard for Floating-Point Arithmetic is a technical standard for floating-point arithmetic established in 1985 by the Institute of Electrical and Electronics Engineers (IEEE). The standard addressed many problems found in the diverse floating-point implementations that made them difficult to use reliably and portably. Many hardware floating-point units use the IEEE 754 standard.

In computing, fixed-point is a method of representing fractional (non-integer) numbers by storing a fixed number of digits of their fractional part. Dollar amounts, for example, are often stored with exactly two fractional digits, representing the cents. More generally, the term may refer to representing fractional values as integer multiples of some fixed small unit, e.g. a fractional amount of hours as an integer multiple of ten-minute intervals. Fixed-point number representation is often contrasted to the more complicated and computationally demanding floating-point representation.

In mathematics, finite field arithmetic is arithmetic in a finite field contrary to arithmetic in a field with an infinite number of elements, like the field of rational numbers.

In computing, signed number representations are required to encode negative numbers in binary number systems.

Modular exponentiation is exponentiation performed over a modulus. It is useful in computer science, especially in the field of public-key cryptography, where it is used in both Diffie-Hellman Key Exchange and RSA public/private keys.

In modular arithmetic computation, Montgomery modular multiplication, more commonly referred to as Montgomery multiplication, is a method for performing fast modular multiplication. It was introduced in 1985 by the American mathematician Peter L. Montgomery.

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 College in Bloomsbury, London. Booth's algorithm is of interest in the study of computer architecture.

A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of Euclidean division. Some are applied by hand, while others are employed by digital circuit designs and software.

Non-standard positional numeral systems here designates numeral systems that may loosely be described as positional systems, but that do not entirely comply with the following description of standard positional systems:

In computing, bit numbering is the convention used to identify the bit positions in a binary number.

Kochanski multiplication is an algorithm that allows modular arithmetic to be performed efficiently when the modulus is large. This has particular application in number theory and in cryptography: for example, in the RSA cryptosystem and Diffie–Hellman key exchange.

A redundant binary representation (RBR) is a numeral system that uses more bits than needed to represent a single binary digit so that most numbers have several representations. An RBR is unlike usual binary numeral systems, including two's complement, which use a single bit for each digit. Many of an RBR's properties differ from those of regular binary representation systems. Most importantly, an RBR allows addition without using a typical carry. When compared to non-redundant representation, an RBR makes bitwise logical operation slower, but arithmetic operations are faster when a greater bit width is used. Usually, each digit has its own sign that is not necessarily the same as the sign of the number represented. When digits have signs, that RBR is also a signed-digit representation.

Elliptic curve scalar multiplication is the operation of successively adding a point along an elliptic curve to itself repeatedly. It is used in elliptic curve cryptography (ECC) as a means of producing a one-way function. The literature presents this operation as scalar multiplication, as written in Hessian form of an elliptic curve. A widespread name for this operation is also elliptic curve point multiplication, but this can convey the wrong impression of being a multiplication between two points.

References

  1. ↑ Hewlitt, R.M. (2000). Canonical signed digit representation for FIR digital filters. Signal Processing Systems, 2000. SiPS 2000. 2000 IEEE Workshop on. pp. 416–426. doi:10.1109/SIPS.2000.886740. ISBN   978-0-7803-6488-2. S2CID   122082511.
  2. ↑ Reitwiesner, George W. (1960). "Binary Arithmetic". Advances in Computers. 1: 231–308. doi:10.1016/S0065-2458(08)60610-5. ISBN   9780120121014.
  3. ↑ Hankerson, D.; Menezes, A.; Vanstone, S.A. (2004). Guide to Elliptic Curve Cryptography. Springer. p. 98. ISBN   978-0-387-21846-5.
  4. ↑ Prodinger, Helmut. "On Binary Representations of Integers with Digits -1, 0, 1" (PDF). Integers. Retrieved 25 June 2021.
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.