“Carry-less multiplication is the operation of multiplying two operands without generating
and propagating carries”
-Intel Corporation
Can someone please explain to me what “carries” are exactly? Feel free to leave any other unique bits of knowledge that you have on the subject. I only hope that I have chosen the proper sub-topic for this post.
I have absolutely no idea and everything I look into starts from expectation that I know what that “carry” is by saying “carry-less” and going on to rant about it
Caution: I am guessing that the term has the same meaning here as in mathematics. The rest is pure speculation.
A carry is a term used in arithmetic for the value generated when the result in a mathematical operation is too big to be stored in the current significant digit and “flows over” into the next significant digit.
Example in binary (I hope I didn’t make a mistake):
A carry-less multiplication is essentially an XOR of the bits of same significance in the addition.
I believe I have come across random number generator before that uses carry-less products. No idea where this is used in the real world. There are mathematical operations that could be written as carry-less multiplications. My guess is that it is cheaper from a register/hardware perspective to do carry less multiply and this is the reason it is available as an operation.
You store numbers in registers (internal CPU memory) before you can operate on them (multiply, add, whatever). When you add or multiply numbers represented by finite amount of bits (64 in case of x86_64) you run out of space in those registers. So you what you can do is store the incomplete result and set a carry flag (a single bit). You can use that flag to chain operations with result that take more than 1 register.
This let’s you multiply numbers that are larger than native word size of the machine (register size).
You can check my blog on basic bitwise mathematics in CPU, although I only talk abotu addition and subtractions.
5x1+0
gives 5+0 so 50(yea seems stupid but thats how it works)
5x100
5x0
5x0
5x1
= 5x1+0+0=500
basically when you carry a number it means if you multiplying 222x5 then you say.
2x5 carry the 1
so next it is.
2x5+1 carry the one.
and finally.
2x5 carry the 1.
so.
1110
You can do it with divisions as well.
I am guessing intel has done some implementation/registers which does the same.
At least with adders (not sure about multipliers coz there are different designs of varying complexity) you add the bits one with the other, and if you add say 0b1 + 0b1 = 0b10 you can’t represent that as single bit, so you return “partial product” and a carry. So prod = 0b0 + carry = 0b1. You also actually take the previous carry in so actually:
carry + op1 + op2 = prod and carry
0b0 + 0b1 + 0b1 = 0b0 and 0b1
As you can see since you have both carry in and carry out you can chain addition to arbitrary word size. (again, word as in the native register size)
multiplication is much more complex, involved shifting and adding at minimum and the product is always 2xbits of the op bit width.
I only implemented multiplication once, and I just cut it half way (didn’t compute the full product) to save “die” size.
Thank you, guys! All of these responses were very helpful! I had tried a Google search myself, but I could not find anything helpful so I turned to the community for help! As always, you guys delivered! Level1Techs is a great community and I seriously appreciate the clarification and detail.