Multiplication of very long integers

Question

Is there an algorithm for accurately multiplying two arbitrarily long integers together? The language I am working with is limited to 64-bit unsigned integer length (maximum integer size of 18446744073709551615). Realistically, I would like to be able to do this by breaking up each number, processing them somehow using the unsigned 64-bit integers, and then being able to put them back together in to a string (which would solve the issue of multiplied result storage).

Any ideas?

Solution 1

Most languages have functions or libraries that do this, usually called a Bignum library (GMP is a good one.)

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

Example:

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

Or in binary:

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

Edit: After doing it in binary I realized that it would be much simpler (and faster of course) to code using bitwise operations instead of strings containing the base-10 numbers. I've edited my binary multiplying example to show a pattern: for each 1-bit in the bottom number, add the top number, bit-shifted left the position of the 1-bit times to a variable. At the end, that variable will contain the product.

To store the product, you'll have to have two 64-bit numbers and imagine one of them being the first 64 bits and the other one the second 64 bits of the product. You'll have to write code that carries the addition from bit 63 of the second number to bit 0 of the first number.

Solution 2

If you can't use an existing bignum library like GMP, check out Wikipedia's article on binary multiplication with computers. There are a number of good, efficient algorithms for this.

Solution 3

The simplest way would be to use the schoolbook mechanism, splitting your arbitrarily sized numbers into chunks of 32-bit each.

Given A B C D * E F G H (each chunk 32-bit, for a total 128 bit)
You need an output array 9 dwords wide. Set Out[0..8] to 0

You'd start by doing: H * D + out[8] => 64 bit result.
Store the low 32-bits in out[8] and take the high 32-bits as carry
Next: (H * C) + out[7] + carry
Again, store low 32-bit in out[7], use the high 32-bits as carry
after doing H*A + out[4] + carry, you need to continue looping until you have no carry.

Then repeat with G, F, E.
For G, you'd start at out[7] instead of out[8], and so forth.

Finally, walk through and convert the large integer into digits (which will require a "divide large number by a single word" routine)

Solution 4

Yes, you do it using a datatype that is effectively a string of digits (just like a normal 'string' is a string of characters). How you do this is highly language-dependent. For instance, Java uses BigDecimal. What language are you using?

Solution 5

This is often given as a homework assignment. The algorithm you learned in grade school will work. Use a library (several are mentioned in other posts) if you need this for a real application.

View more solutions

Comments

[Valdemarick]

Freebasic, which I do not think has this feature built in. I am willing to write it though, if I could get an idea of the algorithm used.

[Nick Johnson]

Congratulations, you've just reinvented 'peasant multiplication'. ;) en.wikipedia.org/wiki/…

[DanielOfTaebl]

There are much faster algorithms for multiplication than "peasant multiplicaton"

[phuclv]

your code has a lot of syntax errors that result in compilation failure. I've fixed some of them but the code still doesn't work

[phuclv]

are you sure this works? why do you remove the js tag so that people can verify?

[Pianistprogrammer]

that wasn't deliberate, I just replaced the code afresh with the working one. You can create a plunkr for this or jsfiddle