An interview question - implement Biginteger Multiply

Question

Implement Biginteger Multiply

1. use integer array to store a biginteger like 297897654 will be stored as {2,9,7,8,9,7,6,5,4}
2. implement the multiply function for bigintegers
   Expamples: {2, 9, 8, 8, 9, 8} * {3,6,3,4,5,8,9,1,2} = {1,0,8,6,3,7,1,4,1,8,7,8,9,7,6}

I failed to implement this class and thought it for a few weeks, couldn't get the answer.

Anybody can help me implement it using C#/Java? Thanks a lot.

Answer 1

Do you know how to do multiplication on paper?

  123
x 456
-----
  738
 615
492
-----
56088

I would just implement that algorithm in code.

Answer 2

If you do it the long-hand way, you'll have to implement an Add() method too to add up all the parts at the end. I started there just to get the ball rolling. Once you have the Add() down, the Multipy() method gets implemented along the same lines.

public static int[] Add(int[] a, int[] b) {
   var maxLen = (a.Length > b.Length ? a.Length : b.Length);
   var carryOver = 0;
   var result = new List<int>();
   for (int i = 0; i < maxLen; i++) {
      var idx1 = a.Length - i - 1;
      var idx2 = b.Length - i - 1;
      var val1 = (idx1 < 0 ? 0 : a[idx1]);
      var val2 = (idx2 < 0 ? 0 : b[idx2]);

      var addResult = (val1 + val2) + carryOver;
      var strAddResult = String.Format("{0:00}", addResult);
      carryOver = Convert.ToInt32(strAddResult.Substring(0, 1));
      var partialAddResult = Convert.ToInt32(strAddResult.Substring(1));
      result.Insert(0, partialAddResult);
   }
   if (carryOver > 0) result.Insert(0, carryOver);
   return result.ToArray();
}

Answer 3

C++ Implementation:

Source Code:

#include <iostream>

using namespace std;

int main()
{
    int a[10] = {8,9,8,8,9,2};
    int b[10] = {2,1,9,8,5,4,3,6,3};

    // INPUT DISPLAY
    for(int i=9;i>=0;i--) cout << a[i];
    cout << " x ";
    for(int i=9;i>=0;i--) cout << b[i];
    cout << " = ";

    int c[20] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

    for(int i=0;i<10;i++)
    {
            int carry = 0;
            for(int j=0;j<10;j++)
            {
                    int t = (a[j] * b[i]) + c[i+j] + carry;
                    carry = t/10;
                    c[i+j] = t%10;
            }
    }

    // RESULT DISPLAY
    for(int i=19;i>=0;i--) cout << c[i];
    cout << endl;
}

Output:

0000298898 x 0363458912 = 00000108637141878976