Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I only tenuously understand this so feel free to ignore the question if it's too asinine but:

> (What about ×5? If you can compute ×3, you can subtract that from ×8 to get ×5.)

Why can't you do the same to subtract x4 from x7 to get x3?



Because x8 is simply shifting 3 bits left so it's "free" (fixed-sized shifts are very simple to implement), whereas generating the x7 would require the additional circuitry, which additionally will be more expensive than the x3 was (since it's another shift+add beyond what x3 required)


x7 is computed by x8 - x, so you get x8 - x - x4 which is 2 subtractions (and 2 delays). You only want 1 delay.


The question would be why isn't it 4x - 1x?


The trick is that Booth's algorithm gives you the ×8 term for free; you multiply by one more in the next base-8 digit. You can put either ×4 or -×1 into a term, but you can't put both of them into one term. So you can do ×8 - ×1 but you can't do ×4 - ×1.


I guess the decimal equivalent would be multiplying by 10 vs multiplying by 5.

Or for hexadecimal: multiplying by 0x10 (16) or by 2, 4 or 8.


I suspect it's logically equivalent, but one bit wider in hardware.

Binary 4x is left shift by 2, rather than 2x which is by one.

Adding or subtracting in 2's compliment space is the same operation for the bits of the word.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: