Multiplication of large numbers represented as arrays?

Question

The numbers are stored in the arrays with their digits in reverse order. Here is a functions that should multiply two numbers, lhs and rhs, and store the product in result:

public static void MultiplyDigitArrays(int[] lhs, int[] rhs, int[] result)
{        
     int length1 = Math.Max(lhs.Length, rhs.Length);
     for (int i = 0; i < length1; i++)
     {
        int[] PartialProduct = new int[result.Length];

        int length2 = Math.Min(lhs.Length, rhs.Length);
        for (int j = 0; j < length2; j++)
        {
            int multiplicand = (lhs.Length < rhs.Length) ? rhs[i] : lhs[i];
            int multiplier = (lhs.Length < rhs.Length) ? lhs[j] : rhs[j];

            int product = PartialProduct[i + j] + multiplicand * multiplier;

            PartialProduct[i + j] = product % 10;
            int carry = product / 10;

            PartialProduct[i + j + 1] = PartialProduct[i + j + 1] + carry;
        }
        SumDigitArrays(PartialProduct, result, result);
    }
}

However, if I multiply:

static void Main(string[] args)
{
    int[] n1 = { 1, 1 };
    int[] n2 = { 1, 1 };
    int[] result = new int[Math.Max(n1.Length, n2.Length) * 2 + 1];

    MultiplyDigitArrays(n1, n2, result);

    PrintArray(result);

    Console.WriteLine();
}

the result is:

00132

instead of the expected:

00121

What am I doing wrong?

---

For the MCVE:

public static void PrintArray(int[] Array)
{
    int length = Array.Length;
    for (int i = length - 1; i >= 0; i--)
    {
        Console.Write(Array[i]);

    }
}

public static void SumDigitArrays(int[] a, int[] b, int[] result)
{
    int length = Math.Max(a.Length, b.Length);
    for (int i = 0; i < length; i++)
    {
        int lhs = (i < a.Length) ? a[i] : 0;
        int rhs = (i < b.Length) ? b[i] : 0;

        int sum = result[i] + lhs + rhs;
        result[i] = sum % 10;

        int carry = sum / 10; 

        if (i + 1 < result.Length)
        {
            result[i + 1] = result[i + 1] + carry;
        }
    }
}

Answer 1

Apart from the two other answers given (which are spot-on and solve your problem), unless you have a very specific need, I'd recommend going for BigInteger if you need to multiply very large numbers.

For your specific needs (in case your numbers must come and go in an array of ints, which is a weird way to store any number), your Multiply could become:

public static void MultiplyDigitArrays(int[] lhs, int[] rhs, int[] result)
{        
    var n1 = BigInteger.Parse(string.Join("", lhs));
    var n2 = BigInteger.Parse(string.Join("", rhs));
    var resultBi = BigInteger.Multiply(n1, n2);     
    Array.Clear(result, 0, result.Length);
    var stResult = resultBi.ToString().PadLeft(result.Length, '0');
    for(int i = 0; i < stResult.Length; i++)
    {
        result[(stResult.Length-1)-i] = int.Parse(stResult[i].ToString());
    }
}

Note that the burden of this function is actually converting your integer array back and forth, since an integer array is a weird format to store a number.

If you work directly with strings (or BigIntegers), this function would just not be necessary. For example, if working with strings containing the numbers, this could become:

public static string MultiplyBigNumbers(string lhs, string rhs)
{        
    var n1 = BigInteger.Parse(lhs);
    var n2 = BigInteger.Parse(rhs);
    return BigInteger.Multiply(n1, n2).ToString();      
}

And just call it: MultiplyBigNumbers("3242", "42349");

Then again, I'd recommend just working with BigInteger all the way down, and have it converted whenever you need to store it (for which a byte array makes more sense, and you can get it with ToByteArray()) or display (which can be easily done with a ToString() call)

Note that passing an array for the result is also pretty weird (for .NET anyway), since you don't need the original values. You'd be better off returning an array and calculating the needed length in the function itself, not having the caller figure it out.

Answer 2

The reason is because the third parameter use you in calling SumDigitArrays should be empty. Instead, you feed it the result variable which contains data on any iteration other than the first.

Implement your method like this:

    public static int[]  MultiplyDigitArrays(int[] lhs, int[] rhs)
    {
        int length1 = Math.Max(lhs.Length, rhs.Length);
        var result = new int[length1* length1];

        for (int i = 0; i < length1; i++)
        {
            int[] PartialProduct = new int[length1 * length1];

            int length2 = Math.Min(lhs.Length, rhs.Length);
            for (int j = 0; j < length2; j++)
            {
                int multiplicand = (lhs.Length < rhs.Length) ? rhs[i] : lhs[i];
                int multiplier = (lhs.Length < rhs.Length) ? lhs[j] : rhs[j];

                int product = PartialProduct[i + j] + multiplicand * multiplier;

                PartialProduct[i + j] = product % 10;
                int carry = product / 10;

                PartialProduct[i + j + 1] = PartialProduct[i + j + 1] + carry;
            }
            result = SumDigitArrays(PartialProduct, result);
        }

        return result;
    }


    public static int[] SumDigitArrays(int[] a, int[] b)
    {
        int length = Math.Max(a.Length, b.Length);
        var result = new int[length];

        for (int i = 0; i < length; i++)
        {
            int lhs = (i < a.Length) ? a[i] : 0;
            int rhs = (i < b.Length) ? b[i] : 0;

            int sum = result[i] + lhs + rhs;
            result[i] = sum % 10;

            int carry = sum / 10;

            if (i + 1 < result.Length)
            {
                result[i + 1] = result[i + 1] + carry;
            }
        }

        return result;
    }

Answer 3

I don't exactly understand the logic you are performing, but

 int product = PartialProduct[i + j] + multiplicand * multiplier;

Gets evaluated as

int product = PartialProduct[i + j] + (multiplicand * multiplier);

Did you intend it to do

int product = (PartialProduct[i + j] + multiplicand) * multiplier;

As that could explain your error.