# 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 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

**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 ]