Multiplication of very long integers

Question

Is there an algorithm for accurately multiplying two arbitrarily long integers? The language I'm working with is limited to a 64-bit unsigned integer length (maximum integer size is 18446744073709551615). Actually, I would like to be able to do this by breaking each number, processing them somehow using unsigned 64-bit integers, and then being able to combine them into a string (to solve the problem of multiplied storage result).

Any ideas?

Answer 1

Most languages ​​have functions or libraries that do this, commonly called the Bignum library ( GMP is good.)

If you want to do it yourself, I will do it the same way people do long multiplication on paper. To do this, you can either work with strings containing a number, or do it in binary format using bitwise operations.

Example:

45 x67 --- 315 +270 ---- 585 

Or in binary format:

  101 x101 ---- 101 000 +101 ------ 11001 

Edit: After doing this in binary, I realized that it would be much easier (and rather faster) to encode using bitwise operations instead of strings containing base-10 numbers. I edited my binary multiplication example to show a pattern: for each 1-bit lower number, add the upper number, the bit shifted to the left of the 1-bit time position of the variable. At the end, this variable will contain the product.

To save the product, you will need to have two 64-bit numbers and imagine that one of them is the first 64-bit and the second a second 64-bit product. You will have to write a code that transfers the addition from bit 63 of the second number to bit 0 of the first number.

Answer 2

If you cannot use an existing bignum library such as GMP, see the Wikipedia article on binary multiplication with computers . There are a number of good, efficient algorithms for this.

Answer 3

The simplest way would be to use the textbook mechanism, breaking your randomly sized numbers into pieces of 32 bits each.

Given ABCD * EFGH (each piece is 32-bit, only 128 bits)
You need a 9 word output array. Set Out [0..8] - 0

You will begin by doing: H * D + out [8] => the result is 64 bits.
Keep low 32-bit outputs [8] and take 32-bit bits as carry
Next: (H * C) + out [7] + carry
Again, keep the low 32-bit output [7], use 32-bit bits as a carry
after doing H * A + out [4] + transfer, you need to continue the cycle until you have a transfer.

Then repeat with G, F, E.
For G, you start with exit [7], not from [8], etc.

Finally, go through and convert a large integer into numbers (which would require "divide a large number by one word")

Answer 4

Yes, you do this using a data type that is actually a string of numbers (just like a normal "string" is a string of characters). How you do this depends on the language. For example, Java uses BigDecimal. What language do you use?

Answer 5

This is often given as homework. The algorithm you learned in high school will work. Use the library (some of them are mentioned in other posts) if you need it for a real application.

Answer 6

here is my code snippet in C. Nice old multiplication method

 char *multiply(char s1[], char s2[]) { int l1 = strlen(s1); int l2 = strlen(s2); int i, j, k = 0, c = 0; char *r = (char *) malloc (l1+l2+1); // add one byte for the zero terminating string int temp; strrev(s1); strrev(s2); for (i = 0;i <l1+l2; i++) { r[i] = 0 + '0'; } for (i = 0; i <l1; i ++) { c = 0; k = i; for (j = 0; j < l2; j++) { temp = get_int(s1[i]) * get_int(s2[j]); temp = temp + c + get_int(r[k]); c = temp /10; r[k] = temp%10 + '0'; k++; } if (c!=0) { r[k] = c + '0'; k++; } } r[k] = '\0'; strrev(r); return r; }