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

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

Answer 2

Here is a patched version of java.lang.BigInteger that uses Karatsuba and Toom-Cook:

And here is a Java class that can multiply BigIntegers using Schönhage-Strassen: