Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

This is my home work assignment.

Establish a relation between the number of bit-switching in multiplier and the number of addition/subtraction operations performed in Booth’s algorithm.

Now Booth Algorithm is shown below, Booth Algorithm I understand that addition or subtraction will be performed when the LSB of Q and Q-1 are different. But how do I come up with a relation?

Thanks in advance.

share|improve this question
Try a few examples and see what you get. You can consult the Wikipedia article (en.wikipedia.org/wiki/Booth%27s_multiplication_algorithm), which has a more accurate description of the algorithm. – Yuval Filmus Aug 28 '11 at 18:37
Yes I have seen this algo on wikipedia. It was different from the one mentioned here. But this one is what we are following – Fahad Uddin Aug 28 '11 at 19:36
Notice that $Q_{-1}$ is not $Q-1$. It is the bit next to $Q_0$, which is the LSB (least significant bit). So there's a strong connection between sign changes in $Q$ and which path is taken after querying $(Q_0,Q_{-1})$. – Yuval Filmus Aug 28 '11 at 19:53

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.