Talk:Non-adjacent form: Difference between revisions
Content deleted Content added
No edit summary |
mNo edit summary |
||
Line 5: | Line 5: | ||
BUT the Booth algorithm does not generate a NAF representation! Take as an example a binary string with an isolated 1, say ...<math>00100</math>..., which by the Booth Algorithm converts into ...<math>01\bar1</math>... |
BUT the Booth algorithm does not generate a NAF representation! Take as an example a binary string with an isolated 1, say ...<math>00100</math>..., which by the Booth Algorithm converts into ...<math>01\bar1</math>... |
||
The original algorithm for converting a binary number into its equivalent and unique |
The original algorithm for converting a binary number into its equivalent and unique NAF form was given by Reitwiesner in 1960, but normally it is described by the following right-to-left algorithm: |
||
'''Input:''' <math>b_{n-1}\cdots b_1b_0</math> in 2's |
'''Input:''' <math>b_{n-1}\cdots b_1b_0</math> in 2's complement<br> |
||
'''Output:''' <math>e_n e_{n-1}\cdots e_1 e_0</math><br> |
'''Output:''' <math>e_n e_{n-1}\cdots e_1 e_0</math><br> |
||
<math>c_0:=0;\ b_n:=b_{n-1};</math><br> |
<math>c_0:=0;\ b_n:=b_{n-1};</math><br> |
Revision as of 21:41, 9 February 2006
The paragraph on alternating signs is not correct. Just consider the binary representation of decimal 9, being 1001, which is its unique NAF form.
It is however correct that the Booth Algorithm determines a signed digit representation where the signs of the non-zero digits alternate.
BUT the Booth algorithm does not generate a NAF representation! Take as an example a binary string with an isolated 1, say ......, which by the Booth Algorithm converts into ......
The original algorithm for converting a binary number into its equivalent and unique NAF form was given by Reitwiesner in 1960, but normally it is described by the following right-to-left algorithm:
Input: in 2's complement
Output:
for to do
end