How to check if multiplication requires carries?

Question

For some purposes I need to know if there are there any carries in the multiplication of two numbers, especially in base-2.

How can we do this in Mathematica?

Thanks

to all, very interesting answers!
I use one for my purposes, but can't choose single "answer", so just vote to all )

Answer 1

If you are looking for something like the Carry-less product, for the binary case you can do this with the new FiniteField stuff in Mathematica 14.0:

n = 2^8;
f = FiniteField[2, n];
toPoly[k_] := Reverse@IntegerDigits[k, 2, n];

a = 162; b = 150;
result = f[toPoly[a]]*f[toPoly[b]]
result["Index"] != a*b

If you don't have that, you can implement a carry-less multiply yourself:

multiplyCarryless[a_, b_] := Module[{i, t},
  i = BitLength[a] - 1;
  t = 0;
  While[i >= 0,
   t = BitXor[t, BitGet[a, i]*BitShiftLeft[b, i]];
   i--;
   ]; t
  ]

Then just check if the standard product and the carry-less product are different:

a = 162; b = 150;
mc = multiplyCarryless[a, b]
mc != a*b
IntegerDigits[mc, 2]

Answer 2

Whether any carries occurred is equivalent to whether any "digits" in the convolution are at least as large as the base. I show an example in base 2. First I take a couple of numbers of three (decimal) digits and get the bit lists.

i1 = IntegerDigits[n1 = 223, 2]
i2 = IntegerDigits[n2 = 412, 2]

(* Out[865]= {1, 1, 0, 1, 1, 1, 1, 1}

Out[866]= {1, 1, 0, 0, 1, 1, 1, 0, 0} *)

Check that convolving, with appropriate parameters, is equivalent to multiplication.

n1*n2
FromDigits[ListConvolve[i1, i2, {1, -1}, 0], 2]

(* Out[870]= 91876

Out[871]= 91876 *)

Now let's see what the convolution contains.

lc = ListConvolve[i1, i2, {1, -1}, 0]

(* Out[872]= {1, 2, 1, 1, 3, 4, 4, 4, 3, 3, 3, 3, 2, 1, 0, 0} *)

There are digits that exceed 1 (the base less 1), so there had to be carries.

Answer 3

I offer the following - I'm not sure it is simple. I define a recursive helper function that determines whether a carry is needed in binary addition.

addcarryq[0, _] := False
addcarryq[_, 0] := False
addcarryq[a_?EvenQ, b_] := addcarryq[a/2, Floor[b/2]]
addcarryq[a_, b_?EvenQ] := addcarryq[Floor[a/2], b/2]
addcarryq[a_?OddQ, b_?OddQ] := True

Testing this, I believe that it behaves as expected

With[{n = 7}, Table[addcarryq[i, j], {i, n}, {j, n}]] // 
  TableForm[#, TableHeadings -> Automatic] & // BaseForm[#, 2] &

The logic for multiplication is a little more complicated. Note that the algorithm follows a different path for a*b and b*a. I hope it gives the same answer!

multcarryq[0, _] := False
multcarryq[_, 0] := False
multcarryq[a_?EvenQ, b_] := multcarryq[a/2, b]
multcarryq[a_, b_?EvenQ] := multcarryq[a, b/2]
multcarryq[a_?OddQ, b_?OddQ] := 
 addcarryq[b, 2 Floor[a/2] b] || multcarryq[Floor[a/2], b]

With[{n = 7}, Table[multcarryq[i, j], {i, n}, {j, n}]] // 
  TableForm[#, TableHeadings -> Automatic] & // BaseForm[#, 2] &

Answer 4

Assume we multiply 2 binary numbers, a and b, of length n. The multiplication can be done by appending n-1 zeros to a creating a matrix: mat, whose first row is a with the appended zeros. The second row is equal to the first row rotated 1 digit to the right. The third row is equal to the first row rotated 2 digts to the right, etc. The rows of mat are now multiplied by the digits of b: if the i-th digit of b is zero, the i-th row of mat is nullified. Finally, the rows of mat are added. If there are carries, some numbers in the sum vector are larger than 1:

Here is an example with n=5;

SeedRandom[2];
len = 5;
a = RandomInteger[{0, 1}, len];
b = RandomInteger[{0, 1}, len];
mat = RotateRight[Join[a, Table[0, len - 1]], #] & /@ 
   Range[0, len - 1];
mat = b  mat;
If[Max[Total[mat]] > 1, Print["There are carries"], 
 Print["There are no carries"]]

There are carries

Answer 5

Clear[CarryQ]
CarryQ[a_Integer, b_Integer] := 
 Length@IntegerDigits@(a  b) > Max@(Length@*IntegerDigits /@ {a , b})

SeedRandom[2];
list = RandomInteger[{20}, {5, 2}]~Join~RandomInteger[{1, 10}, {5, 2}]

{#1, #2, #1 #2, CarryQ[#1, #2]} & @@@ list //
 Grid[#, Alignment -> Left] &

---

For the binary case, you can make minor changes given that IntegerDigits has an argument for base and len. If you want to use 2s-complement arithmetic, then you can preferably add more context about the task that requires this calculation.

EDIT (for the binary case)

Let's introduce register length reg that I can arbitrarily set at 8 for the default case; although the function takes it as a parameter. If the sum can fit in the assigned register space then no carry is generated.

Clear[Base2CarryQ]
Base2CarryQ[a_Integer, b_Integer, reg_Integer : 8] := Module[
  {abin = IntegerDigits[a, 2, reg]
   , bbin = IntegerDigits[b, 2, reg]
   },
  Echo[abin];
  Echo[bbin];
  FromDigits[Echo@IntegerDigits[a b, 2, reg], 2] != a b
  ]

Usage: (remove Echo statements if not needed)

a = 2;
b = 128;
Base2CarryQ[a, b] 
(* carry out from the 
default 8 bit register *)
    
Base2CarryQ[a, b, 9] 
(* carry out? of a
 9-bit register *)

---