Re: observation on NAF
From: James Muir (noone_at_127.0.0.1)
Date: 10/25/05
 Next message: tomstdenis_at_gmail.com: "Re: observation on NAF"
 Previous message: Douglas Eagleson: "A Number Type Detecting Algorithm"
 In reply to: tomstdenis_at_gmail.com: "observation on NAF"
 Next in thread: tomstdenis_at_gmail.com: "Re: observation on NAF"
 Reply: tomstdenis_at_gmail.com: "Re: observation on NAF"
 Reply: tomstdenis_at_gmail.com: "REPOST: Re: observation on NAF"
 Reply: tomstdenis_at_gmail.com: "REPOST: Re: observation on NAF"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
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 3NAF 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 3digit window from righttoleft across the representation:
n 1 0 0 0 1 0 0 1 0 0 0 0 3 0 0 3
This gives us the 3NAF.
However, you can also slide the window *lefttoright* over the special
signed binary rep and you will get a representation which uses the same
digits as the wNAF and has the same under of nonzero digits. What's
nice about going lefttoright 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 speedup by
constructing your representation lefttoright.
James
 Next message: tomstdenis_at_gmail.com: "Re: observation on NAF"
 Previous message: Douglas Eagleson: "A Number Type Detecting Algorithm"
 In reply to: tomstdenis_at_gmail.com: "observation on NAF"
 Next in thread: tomstdenis_at_gmail.com: "Re: observation on NAF"
 Reply: tomstdenis_at_gmail.com: "Re: observation on NAF"
 Reply: tomstdenis_at_gmail.com: "REPOST: Re: observation on NAF"
 Reply: tomstdenis_at_gmail.com: "REPOST: Re: observation on NAF"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
