Homework: how to write own multiplication of big numbers?

Question

In my project I have to deal with multiplication of big numbers ( greater then java.long ) stared in my own BigNumber class as int[]. Basically I need to implement something like this :

    157 x
    121 y
   ----
    157 result1
   314  + result2
  157   + result3
 ------
 18997  finalResult

But how do I implement it?

I thought about expanding result2,3 with zeros (3140, 15700) and adding them. But first I somehow need to navigate between each digit of y and multiply it by each digit of x.

Answer 1

Use the diagonal approach. Make an array, and multiply each digit by each other digit and fill in the numbers in each cell.

36 x 92

       3     6
    +-----+-----+
    | 2 / | 5 / |
9   |  /  |  /  |
    | / 7 | / 4 |
    +-----+-----+
    | 0 / | 1 / |
2   |  /  |  /  |
    | / 6 | / 2 |
    +-----+-----+

Add the numbers on each diagonal. Move from the least-significant digit (at the lower right) to the most (upper left).

2                                                                    2 (least-significant)
(6 + 1 + 4) = 11 (make this 1, and carry the 1 to the next digit)    1
(5 + 7 + 0 + 1(carried)) = 13 (make this 3, and carry the 1)         3
2 + 1(carried) = 3                                                   3 (most-significant)

The answer's 3312.

Make a two-dimensional array of your digits. Fill the array with the multiplications of the single digits together.

Write some logic to scrape the diagonals as I did above.

This should work for arbitrarily large numbers (as long as you still have memory left).

Answer 2

Here's the code I had written. Basically same as manual multiplication. Pass the two big numbers as strings to this function, the result is returned as a string.

public String multiply(String num1, String num2){
        int product, carry=0, sum=0;
        String result = new String("");
        String partial = new String("");
        ArrayList<String> partialList = new ArrayList<String>();

        /* computing partial products using this loop. */
        for(int j=num2.length()-1 ; j>=0 ; j--) {
            for(int i=num1.length()-1 ; i>=0 ; i--) {       

                product = Integer.parseInt((new Character(num1.charAt(i))).toString()) * 
                                Integer.parseInt((new Character(num2.charAt(j))).toString()) + carry;               
                carry = product/10;
                partial = Integer.toString(product%10) + partial;               
            }       

            if(carry != 0)
                partial = Integer.toString(carry) + partial;

            partialList.add(partial);
            partial = "";
            carry = 0;
        }                           

        /* appending zeroes incrementally */
        for(int i=0 ; i<partialList.size() ; i++)
            partialList.set(i, partialList.get(i) + (Long.toString( (long)java.lang.Math.pow(10.0,(double)i))).substring(1)   );        

        /* getting the size of the largest partial product(last) */
        int largestPartial = partialList.get(partialList.size()-1).length();

        /* prefixing zeroes */
        int zeroes;
        for(int i=0 ; i<partialList.size() ; i++) {
            zeroes =  largestPartial - partialList.get(i).length();

            if(zeroes >= 1)
            partialList.set(i, (Long.toString( (long)java.lang.Math.pow(10.0,(double)zeroes))).substring(1) + partialList.get(i)   );
        }

        /* to compute the result */
        carry = 0;
        for(int i=largestPartial-1 ; i>=0 ; i--) {

            sum = 0;
            for(int j=0 ; j<partialList.size() ; j++)
                sum = sum + Integer.parseInt(new Character(partialList.get(j).charAt(i)).toString());

            sum = sum + carry;
            carry = sum/10;         
            result = Integer.toString(sum%10) + result;     
        }

        if(carry != 0)
            result = Integer.toString(carry) + result;

        return result;
    }