Essays/NAF

The WikiPedia:Non-adjacent_form (NAF) of a number is a unique signed-digit representation. It is useful when building scalar multipliers of Elliptic Curve points, for which the cost of doubling the point is significantly less, compared to the cost of point addition and subtraction. There can be other applications as well, e.g. for efficiently implementing an algebra with similar relative costs of operations.

In J the NAF can be built with the verb

   NAF =: (}:"1@:-/@([: #: (_1 _3)&(*/))) :. #.

It works as

   NAF 7
1 0 0 _1
   NAF i.8
0 0  0  0
0 0  0  1
0 0  1  0
0 1  0 _1
0 1  0  0
0 1  0  1
1 0 _1  0
1 0  0 _1
   |&.NAF i.8
0 1 2 5 4 5 10 9

This implementation supports array arguments and has obverse defined. Thanks to Oleg Kobchenko for array support and to Raul Miller for mentioning that #. is inverse of NAF.

---

Comments

You can use @SIG@ to sign your comments. This section is possibly temporary(?).

• If NAF is a replacement for #:, it should support any shapes, but

   NAF i.3
|length error: NAF
|       NAF i.3
   #:i.3
0 0
0 1
1 0

One solution is

   NAF2=: 13 : '}:"1-/#:_1 _3*/ y.'
   NAF2
[: }:"1 [: -/ [: #: _1 _3"_ */ ]

Example

   (,: #.&.>) (NAF2 ; #:)i.3 4
+------------+---------+
|0 0  0  0  0|0 0 0 0  |
|0 0  0  0  1|0 0 0 1  |
|0 0  0  1  0|0 0 1 0  |
|0 0  1  0 _1|0 0 1 1  |
|            |         |
|0 0  1  0  0|0 1 0 0  |
|0 0  1  0  1|0 1 0 1  |
|0 1  0 _1  0|0 1 1 0  |
|0 1  0  0 _1|0 1 1 1  |
|            |         |
|0 1  0  0  0|1 0 0 0  |
|0 1  0  0  1|1 0 0 1  |
|0 1  0  1  0|1 0 1 0  |
|1 0 _1  0 _1|1 0 1 1  |
+------------+---------+
|0 1  2  3   |0 1  2  3|
|4 5  6  7   |4 5  6  7|
|8 9 10 11   |8 9 10 11|
+------------+---------+

-- Oleg Kobchenko <<DateTime(2005-11-02T21:17:42Z)>>

• The inverse of NAF2 (and NAF) is #. -- Raul Miller <<DateTime(2005-11-03T00:52:28Z)>>

---

Contributed by Konstantin Metlov.