For the life of me I cannot understand binary multiplication or booths algorithm.

This is topic I have just been introduced to in my computer architectures class and it makes 0 sense.

In: 0

Share & grow the world's knowledge!

For the life of me I cannot understand binary multiplication or booths algorithm.

This is topic I have just been introduced to in my computer architectures class and it makes 0 sense.

In: 0

- [deleted] on Are electric toothbrushes really better than manual ones, or is technique paramount?
- ElfMage83 on eli5 In Lower-class Neighborhoods why can’t we stream more money through and create jobs and more opportunities to the people?
- SaiphSDC on How can water evaporate from a pool in the summer when it is supposed to evaporate at 100°C ?
- todlee on eli5 In Lower-class Neighborhoods why can’t we stream more money through and create jobs and more opportunities to the people?
- Jozer99 on eli5: why can’t we intercept nuclear missiles?

Copyright © 2022 AnswerCult

First, remember decimal multiplication. When we multiply `A*B`, we separate `B` into sum of decimal places and distribute `A` over sum. So `A*3456 = A * (3000 + 400 + 50 + 6) = A*3000 + A*400 + A*50 + A*6`. And of course, `A*400` is the same as `A*4, shift left 2`. So, we only need to know multiplication on single digits to multiply any numbers.

Binary multiplication works the same way: `A*1011 = A*1000 + A*000 + A*10 + A*1`. Again, `A*1000` is just `A*1, shift left 4`. Actually, because there are only two digits in binary – 0 and 1 – you only ever need to add either `A shift left X`, or nothing!

Now to understand Booth’s, let’s again start from decimal. Can you multiply `A*999`? You can use the usual algorithm (`999 = 900 + 90 + 9`), but you can do it simpler: `999 = 1000 – 1`, so `A * 999 = A * (1000 – 1) = A*1000 – A`! By allowing subtraction we can calculate the answer easier!

Booth’s does the same, but in binary: it detects strings of 1s and replaces them with subtraction – `1111 = 10000 – 1`, `1110 = 10000 – 10`, etc. So `A*110111 = A*(100000 – 10000 + 1000 – 1)`, which can be converted in adding either `A` or `-A`, shifted left. Booth’s algorithm reads numbers from right to left:

* each time you see `10` – you at the right end of 1s string: subtract,

* each time you see `01` – you at the left end of 1s string: add,

* `00` is the 0s – do nothing

* `11` is the middle of 1s string: do nothing