This is a conceptual question about an algorithm which is related to a problem I'm personally solving.

Any useful CPU architecture stores the overflow bits in a certain register after multiplication, but what if this feature is not available? Is there an efficient way to compute the overflow bits?

Since it's an overflow a * b >> bits is not an option.

CodePudding user response：

I can imagine two basic options.

1. Old CPUs did not support multiplication at all. We had to do it manually. You can always implement multiplication by addition and shifting. This algorithm is quite simple and not limited to any number of bits (because both addition and shifting is easy to do in any number of bits on all CPUs).

2. If your CPU can do multiplication without overflow in N bits, you can use this as a helper to get the result faster than bit-by-bit computation mentioned above. If a and b are N-bit wide each, then the result of a * b is 2N wide. If you split a and b to halves, then each half is N/2 wide, their product is N-bit wide. So you multiply halves with each other and then add them together. If we mark upper half a2/b2 and lower half a1/b1, then lower result is a1 * b1, middle result is a2 * b1 a1 * b2, upper result is a2 * b2, each time plus overflow. I hope it is trivial enough so detailed description is not necessary.