Re: observation on NAF

From: James Muir (noone_at_127.0.0.1)
Date: 10/25/05 

Date: Tue, 25 Oct 2005 10:36:28 -0400

> I've tried 3NAF and 5NAF [it's easily switchable] and their doesn't
> seem to be an improvement. It's also a bit annoying that you can't
> compute NAF directly like you can for the unsigned window [e.g. just
> take the bits verbatim].

There is a neat trick for constructing the wNAF that you might find
useful. It is based on a special {0,1,-1} radix 2 representation of an
integer.

Suppose we want to build the 3-NAF of an integer n which has the binary
representation 111011100010101. First, we construct the special signed
binary representation by doing a digitwise subtraction of n from 2n

2n 1 1 1 0 1 1 1 0 0 0 1 0 1 0 1 0
  n 1 1 1 0 1 1 1 0 0 0 1 0 1 0 1

n 1 0 0 -1 1 0 0 -1 0 0 1 -1 1 -1 1 -1

Now we slide a 3-digit window from right-to-left across the representation:
        
n 1 0 0 0 1 0 0 -1 0 0 0 0 3 0 0 -3

This gives us the 3-NAF.

However, you can also slide the window *left-to-right* over the special
signed binary rep and you will get a representation which uses the same
digits as the w-NAF and has the same under of nonzero digits. What's
nice about going left-to-right is that you don't need to store the
digits of the new representation before you compute a scalar
multiplication -- you can just process them on the fly.

I would be interested to know if you observe any speed-up by
constructing your representation left-to-right.

-James

Relevant Pages

  • Re: observation on NAF
    ... > There is a neat trick for constructing the wNAF that you might find ... > binary representation by doing a digitwise subtraction of n from 2n ... > digits as the w-NAF and has the same under of nonzero digits. ... I used the trick of generating the digits right-to-left using the ...
    (sci.crypt)
  • Re: Gentler Decimal Floating-Point
    ... effectively change the radix of a decimal floating point ... under the heading "Logarithms all the time", ... logarithmic representation of numbers to be made workable for all the ... The middle digits are shifted only when the exponent, ...
    (comp.arch.arithmetic)
  • Re: Smart number formatting
    ... but a highly unlikely scenario in this program. ... anything the user inputs after the 8th decimal point renders ... > I have also considered counting the number of digits the user inputs to ... representation of a float or double. ...
    (comp.lang.java.help)
  • REPOST: Re: observation on NAF
    ... > There is a neat trick for constructing the wNAF that you might find ... > binary representation by doing a digitwise subtraction of n from 2n ... > digits as the w-NAF and has the same under of nonzero digits. ... My hunch is the density isn't as low as they suspect or my naf ...
    (sci.crypt)
  • REPOST: Re: observation on NAF
    ... > There is a neat trick for constructing the wNAF that you might find ... > binary representation by doing a digitwise subtraction of n from 2n ... > digits as the w-NAF and has the same under of nonzero digits. ... I used the trick of generating the digits right-to-left using the ...
    (sci.crypt)