Properties of carry in base $b$ multiplication

48 Views Asked by At

Consider $n$ bit numbers $A$ and $B$.

Let they be represented in base $b$.

When you multiply $A$ and $B$ using school multiplication:

$(1)$ how many carry propagations can one expect?

$(2)$ what is the average length of carry propagation that one can expect?

Example:

$1001 \times 1000000001$ has no carry propagation.

$1000011100000011000011100000011111 \times 1100000110001000011100000011$ has many carry propagations when you multiply but each carry propagation is short.

$11111111 \times 1111$ has one carry propagation and it is long.

1

There are 1 best solutions below

0
On

Too long for a comment: When multiplying in bases other than $2$ you have two different sorts of carries. In base $2$, each individual bit multiplication cannot carry. The only carries you get are when you add the bit multiplications together. In other bases you can get carries in the multiplication step. In base $10$, for example, when multiplying $79 \times 63$ you start with $79 \times 3$ and have a carry $2$ at each digit, then you do $79 \times 6$ and have carries of $5$ and $4$. In this case you don't have any carries during the final addition,but you might. I don't think much can be said about likely carry propagation, except that if you have lots of digits you will have lots of carries.