Wikipedia:Reference desk/Archives/Mathematics/2013 September 26

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 26

Computing the carry in a multiplication operation

For my own amusement, I work on a C++ program that is intended to solve a particular number theoretic problem. In that program, I need to multiply some numbers. Since the intermediate numbers encountered in the computations can be large I am creating my own functions for the basic arithmetic operations (such as addition, subtraction, multiplication). I chose to represent the numbers I am working with as strings. I already have a working addition and a subtraction function and now want to create a multiplication function. If I want to compute something like 543865864 × 343246, the function would iterate through the digits of the multiplier, convert the digit to an unsigned short and then multiply with each digit of the multiplicand (with proper carry). And here my problem starts:

Suppose I have two multi-digit numbers and the multiplication of two digits results in a carry (like 8 × 9, where the carry would be 7 (since 8 × 9 = 72)). How can I compute the value of that carry, so that I can store it into a variable? (Of course, it is easy to see for us that the carry is 7, but the program has no way of knowing that the value that is to be assigned to my carry variable should be 7).

In the end I want to have two variables (say unsigned shorts); one that contains 2 and one that contains 7. -- Toshio Yamaguchi 12:03, 26 September 2013 (UTC)

There's lots of packages that'll do that sort of thing very rapidly. But if you want to do this the appropriate operation you probably want is the modulo operation.

product = in1 * in2;

tens = product / 10;

units = product % 10;

is a low level way of writing it all. Dmcq (talk) 12:15, 26 September 2013 (UTC)

If I do 8 × 9 = 72 and then 72 / 10, I get 7.2 but I would prefer an algorithm that directly yields 7 (without the decimal part). If I do 72 % 10, I get 2, which is not what I want. -- Toshio Yamaguchi 12:26, 26 September 2013 (UTC)

Facepalm

If I do

int a = 72

int b = 10

int c = a / b

then c would be truncated after the 7 due to the typecast, of course. -- Toshio Yamaguchi 12:31, 26 September 2013 (UTC)

Actually it is not the assignment that truncates it but the fact that you're dividing one integer by another. This can catch people out who do some adding up using an integer variable and then divide by the number of items to give the mean and assign to a float. You need to do something like (float)sum/count or sum/12.0 Dmcq (talk) 12:42, 26 September 2013 (UTC)

You might find our page on Binary_multiplier useful. You can multiply binary numbers of arbitrary size using addition and shifts. The Chinese_remainder_theorem can also be used to store very large numbers: our article mentions that this is used in RSA encryption, which calculates the product of two very large primes. OldTimeNESter (talk) 12:40, 26 September 2013 (UTC)

Thanks for the suggestion. In my algorithm I currently plan to multiply the numbers digit wise (using long multiplication), which I believe will be quite fast, since that way I never have to compute a product larger than 81. -- Toshio Yamaguchi 12:57, 26 September 2013 (UTC)