Editing Non-adjacent form

{{Short description|Signed-digit representation}}

{{Numeral systems}}
The '''non-adjacent form''' ('''NAF''') of a number is a unique [[signed-digit representation]], in which non-zero values cannot be adjacent.  For example:

:(0 1 1 1)<sub>2</sub> = 4 + 2 + 1 = 7
:(1 0 −1 1)<sub>2</sub> = 8 − 2 + 1 = 7
:(1 −1 1 1)<sub>2</sub> = 8 − 4 + 2 + 1 = 7
:(1 0 0 −1)<sub>2</sub> = 8 − 1 = 7

All are valid signed-digit representations of 7, but only the final representation, (1 0 0 −1){{sub|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 numeral system|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. This leads to efficient implementations of add/subtract networks (e.g. multiplication by a constant) in hardwired [[digital signal processing]].<ref>{{cite conference|last1=Hewlitt|first1=R.M.|title=Canonical signed digit representation for FIR digital filters|conference=Signal Processing Systems, 2000. SiPS 2000. 2000 IEEE Workshop on|pages=416–426|doi=10.1109/SIPS.2000.886740|year=2000|isbn=978-0-7803-6488-2|s2cid=122082511}}</ref>

Obviously, at most half of the digits are non-zero, which was the reason it was introduced by G.W. Reitweisner <ref name="Reitweisner">{{cite journal |first=George W. |last=Reitwiesner |title=Binary Arithmetic |journal=Advances in Computers |date=1960 |volume=1 |pages=231–308 |doi=10.1016/S0065-2458(08)60610-5|isbn=9780120121014 }}</ref> 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'' +&thinsp;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.<ref name="gecc">{{cite book |first1=D. |last1=Hankerson |first2=A. |last2=Menezes |first3=S.A. |last3=Vanstone |title=Guide to Elliptic Curve Cryptography |publisher=Springer |isbn=978-0-387-21846-5 |date=2004 |page=98}}</ref>

    '''Input'''     ''E'' = (''e''<sub>''m''−1</sub> ''e''<sub>''m''−2</sub> ··· ''e''<sub>1</sub> ''e''<sub>0</sub>)<sub>2</sub>
    '''Output'''     ''Z'' = (''z''<sub>''m''</sub> ''z''<sub>''m''−1</sub> ··· ''z''<sub>1</sub> ''z''<sub>0</sub>)<sub>NAF</sub>
    ''i'' ← 0
    while ''E'' > 0 do
        if ''E'' is odd then
            ''z''<sub>''i''</sub> ← 2 − (''E'' mod 4)
            ''E'' ← ''E'' − ''z''<sub>''i''</sub>
        else
            ''z''<sub>''i''</sub> ← 0
        ''E'' ← ''E''/2
        ''i'' ← ''i'' + 1
    return ''z''

A faster way is given by Prodinger<ref>{{cite web |last1=Prodinger |first1=Helmut |title=On Binary Representations of Integers with Digits -1, 0, 1 |work=Integers |url=http://math.colgate.edu/~integers/a8/a8.pdf |access-date=25 June 2021}}</ref> 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 {{OEIS link|A184616}}.

==External links==
* [https://www.allaboutcircuits.com/technical-articles/an-introduction-to-canonical-signed-digit-representation/ Introduction to Canonical Signed Digit Representation]
* {{cite conference |last1=Coleman |first1=J.O. |last2=Yurdakul  |first2=A. | title = Fractions in the Canonical-Signed-Digit Number System | conference = Conference on Information Sciences and Systems |publisher= The Johns Hopkins University | date = March 21–23, 2001 |url=https://www.researchgate.net/publication/228922770 |oclc=48052559}}

==References==
<references />

{{DEFAULTSORT:Non-Adjacent Form}}
[[Category:Non-standard positional numeral systems]]