Fast multiplication of very large integers

Question

How to multiply two very large numbers greater than 32 characters for example multiplication of 100! with 122! or 22^122 with 11^200 by the help of divide and conquer, do any body have java code or C# code?

Answer 1

I wrote one myself that uses Arrays to accomplish just that, just for fun. I believe Java's BigInteger class does the same thing though.

Here is an example in C# that might be useful to you.

Answer 2

Here's some integer multiplication algorithms:

http://en.wikipedia.org/wiki/Multiplication_algorithm

Here's a class library for numbers:

http://www.ginac.de/CLN/

It includes the Karatsuba and Schonhage-Strassen algorithms for multiplying large integers.

Answer 3

You should probably use java.math.BigInteger. This allows representations of integer values well in excess of 2^32 or even 2^64. BigInteger values are essentially limited only by the amount of memory available to the program, i.e. ~4 GB on a 32-bit system and pretty much available physical+virutal memory for 64-bit systems.

import java.math.BigInteger;

class Foo
{
    public static void main(String args[])
    {
        BigInteger bigInteger100Fact = bigFactorial(BigInteger("100")); //where bigFactorial is a user-defined function to calculate a factorial
        BigInteger bigIntegerBar = new BigInteger("12390347425734985347537986930458903458");

        BigInteger product = bigIntegerFact.multiply(bigIntegerBar);
    }
}

EDIT: Here's a BigInteger factorial function if you need one: http://leepoint.net/notes-java/data/numbers/60factorial.html