phlay

Today I want to write about the famous square-and-multiply (aka double-and-add) algorithm and how we can optimize it with the help of a special kind of signed binary representation: The non-adjacent form (NAF). It turns out, that the non-adjacent form, besides from being useful for speed up arithmetic algorithms, is a very nice topic to study in itself. In many ways the results are parallel to the usual binary-number form, but slightly more involved. [Read More]