Return to Level1Techs.com

What Are "Carries" in Operand Multiplication?


#1

“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.


#2

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

I’d like to also know


#3

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):

multiply with carry:

   1111 · 
    101 =
   ----
   1111 +
  0000
 1111
-------
1001011
multiply without carry:

   1111 · 
    101 =
   ----
   1111 +
  0000
 1111
-------
 110011

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. :thinking:


#4

these might help

https://www.doc.ic.ac.uk/~eedwards/compsys/arithmetic/index.html


#5

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.

https://codebite.xyz/blog/post/2017/3/14/Let's%20Make%20a%20CPU%3A%20Part%202%20-%20NAND%20Logic%20and%20Addition

https://codebite.xyz/blog/post/2017/3/23/Let's%20Make%20a%20CPU%3A%20Part%203%20-%208-Bit%20Integers%2C%20Two's%20Complement%2C%20and%20ALU%20Design


#6

Oh, so it only refers to the most significant bit? In that case I’ll have to remove my post because it is misleading. :frowning:


#7

It’s not misleading multiplication result is always 2x the bits than operands bitwise, my post is more simplistic.


#8

okay, thanks I just don’t want to confuse anyone with a wrong lead


#9

the carry is a fairly simple operation.
5x10
5x0

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.


#10

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.


#11

#12

It seems these instructions, instead of doing full addition, when multiplying 2 numbers, use XOR, which is what addition without carry is.


#13

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.