18

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.

3
  • 1
    Out of curiosity, is there a reason you're not using java.math.BigInteger? Jan 22, 2010 at 21:06
  • 5
    For homework, I imagine that BigInteger is prohibited. This is a classic programming assignment. My prof talked about doing it when he was a student in the 1960s. Jan 22, 2010 at 21:14
  • Michael Easter is correct - homework.
    – sasklacz
    Jan 22, 2010 at 21:20

11 Answers 11

29

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).

7
  • 3
    +1 interesting algo. Does it have a name? Can't seem to find it in wikipedia.
    – BalusC
    Jan 23, 2010 at 2:04
  • great algo, will try it later.
    – sasklacz
    Jan 23, 2010 at 3:33
  • @BalusC: No idea if it has an actual name; I've just always called it "the diagonal method". I used to teach high school (physics) and had actually never seen this approach to multiplication until a student showed me. Jan 23, 2010 at 5:09
  • 9
    Found it, it's called "Lattice Multiplication" or "Gelosia Multiplication": en.wikipedia.org/wiki/…
    – BalusC
    Jan 24, 2010 at 4:16
  • @BalusC: Thanks for finding this! Jan 24, 2010 at 16:09
4

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;
    }
2

I would avoid the headaches of writing your own and just use the java.math.BigInteger class. It should have everything you need.

3
  • 1
    Indeed: no need to reinvent the wheel.
    – Bart Kiers
    Jan 22, 2010 at 21:06
  • 7
    unfortunately it's a homework and BigInteger as well as BigDecimal is prohibited :/
    – sasklacz
    Jan 22, 2010 at 21:20
  • 2
    Good answer, wrong question given the homework requirements.. Could you maybe remove your answer to solicit new answers, Mike?
    – Tim
    Jan 22, 2010 at 21:33
1

Separating out the carrying and the digit multiplication:

def carries(digitlist):
    digitlist.reverse()
    for idx,digit in enumerate(digitlist):
        if digit>9:
            newdigit = digit%10
            carry = (digit-newdigit)/10
            digitlist[idx] = newdigit
            if idx+1 > len(digitlist)-1:
                digitlist.append(carry)
            else:
                digitlist[idx+1] += carry
    digitlist.reverse()
    return True

def multiply(first,second):
    digits = [0 for place in range(len(first)+len(second))]
    for fid,fdig in enumerate(reversed(first)):
        for sid,sdig in enumerate(reversed(second)):
            offset = fid+sid
            mult = fdig*sdig
            digits[offset] += mult
    digits.reverse()
    carries(digits)
    return digits

def prettify(digitlist):
    return ''.join(list(`i` for i in digitlist))

Then we can call it:

a = [1,2,3,4,7,6,2]
b = [9,8,7,9]
mult = multiply(a,b)
print prettify(a)+"*"+prettify(b)
print "calc:",prettify(mult)
print "real:",int(prettify(a))*int(prettify(b))

Yields:

1234762*9879
calc: 12198213798
real: 12198213798

Of course the 10s in the carries function and the implicit decimal representation in prettify are the only thing requiring this to be base 10. Adding an argument could make this base n, so you could switch to base 1000 in order to reduce the numbers of blocks and speed up the calculation.

1

I have implemented this in C++. refer to this for logic...

#include <iostream>
#include <deque>

using namespace std;

void print_num(deque<int> &num) {
  for(int i=0;i < num.size();i++) {
    cout<<num[i];
  }
  cout<<endl;
}

deque<int> sum(deque<int> &oppA, deque<int> &oppB) {
  if (oppA.size() == 0) return oppB;
  if (oppB.size() == 0) return oppA;

  deque<int> result;
  unsigned int carry = 0;

  deque<int>::reverse_iterator r_oppA = oppA.rbegin();
  deque<int>::reverse_iterator r_oppB = oppB.rbegin();
  while ((r_oppA != oppA.rend()) && (r_oppB != oppB.rend())) {

    int tmp = *r_oppA + *r_oppB + carry;
    result.push_front(tmp % 10);
    carry = tmp / 10;

    r_oppB++;
    r_oppA++;

  }
  while (r_oppA != oppA.rend()) {
    int tmp = *r_oppA + carry;
    result.push_front(tmp % 10);
    carry = tmp / 10;
    r_oppA++;
  }

  while (r_oppB != oppB.rend()) {
    int tmp = *r_oppB + carry;
    result.push_front(tmp % 10);
    carry = tmp / 10;
    r_oppB++;
  }

  return result;
}

deque<int> multiply(deque<int>& multiplicand, deque<int>& multiplier) {

  unsigned int carry = 0;
  deque<int> result;
  int deci_cnt = 0;

  deque<int>::reverse_iterator r_multiplier = multiplier.rbegin();
  deque<int> tmp_result;

  while (r_multiplier != multiplier.rend()) {

    for (int i=0; i<deci_cnt ;i++) {
      tmp_result.push_front(0);
    }

    deque<int>::reverse_iterator r_multiplicand = multiplicand.rbegin();
    while (r_multiplicand != multiplicand.rend()) {
      int tmp = (*r_multiplicand) * (*r_multiplier) + carry;
      tmp_result.push_front(tmp % 10);
      carry = tmp / 10;
      r_multiplicand++;
    }

    if (carry != 0) {
      tmp_result.push_front(carry);
      carry = 0;
    }

    result = sum(result, tmp_result);

    deci_cnt++;
    tmp_result.clear();
    r_multiplier++;
  }

  return result;
}

deque<int> int_to_deque(unsigned long num) {
  deque<int> result;

  if (num == 0) {
    result.push_front(0);
  }

  while (num > 0) {
    result.push_front(num % 10);
    num = num / 10;
  }

  return result;
}

int main() {

  deque<int> num1 = int_to_deque(18446744073709551615ULL);
  deque<int> num2 = int_to_deque(18446744073709551615ULL);

  deque<int> result = multiply(num1, num2);
  print_num(result);

  return 0;
}

Output: 340282366920928463426481119284349108225

0

You're going to have to treat each int in the array as a single "digit". Instead of using base 10 where each digit goes from 0 to 9, you'll have to use base 2^32 = 4294967296, where every digit goes from 0 to 4294967295.

I would first implement addition, as your algorithm for multiplication might use addition as an auxiliary.

0
0

As this is for homework I'll give a few hints.

You could approach it the same way you show your example, using strings to hold numbers of any length and implementing:

  • add one number to another
  • multiply as your example by appending zeroes and calling the addition method per step (so for multiply with 20, append the "0" and addd that number twice

The addition method you can build by retrieving the char[] from the strings, allocate a result char[] that is 1 longer than the longest and add like you would do on paper from the end back to the start of both arrays.

The end result will not be the best performing solution, but it it easy to show it is correct and will handle any length numbers (as long they will fit a Java string.)

Update

Ok, if you solved adding two numbers, you could:

  • implement multiplication by 10
  • implement multiplication by repeated addition like in your example

or:

  • implement multiplication by 2 (left shift)
  • implement a binary multiplication via the same concept, only this time x 2 and add once

to illustrate the latter,

  13
   5 x
----
  13 x 1
  26 x 0
  52 x 1
---- +
  65

note that the 1 0 1 are the bits in the number (5) you multiply with and 26 = 13 x 2, 52 = 26 x 2. Your get the idea :-)

1
  • I would like to avoid returning to strings as my add methods also operate on int and they're pretty quick :)
    – sasklacz
    Jan 22, 2010 at 21:38
0

did it my own way :

    int bigger = t1.length;
    int smaller = t2.length;
    int resultLength = bigger + smaller;
    int []resultTemp = new int[resultLength];
    int []result = new int[bigger + smaller];
    int []temporary = new int[resultLength+1];

    int z = resultLength-1;
    int zet = z;
    int step = 0;
    int carry = 0;
    int modulo = 0;

    for(int i=smaller-1; i>=0; i--){
        for(int k = bigger-1; k>= -1; k--){
            if(k == -1 && carry != 0 ){
                resultTemp[z] = carry;
                carry = 0;
                break;
            }
            else if(k == -1 && carry == 0){
                resultTemp[z] = 0;
                break;
            }
            resultTemp[z] = carry + t1[k]*t2[i];
            carry = 0;
            if( resultTemp[z] > 9 ){
               modulo = resultTemp[z] % 10;
               carry = resultTemp[z]/10;
               resultTemp[z] = modulo;
            }
            else{
                resultTemp[z] = resultTemp[z];
            }
            z--;
        }
        temporary = add(resultTemp, result);
        result = copyArray(temporary);
        resultTemp = clear(resultTemp);

        z = zet;
        step++;
        z = z - step;
    }

then I check the sign.

2
  • Your numbers are stored in int arrays with one digit per index. This makes it equivalent to the string method I described. Your inner loop implements a multiplication by the current multiplyer digit, and could be replaced by calling your add() method a few times on an array with the digits moved left (multiplied by 10) on each iteration. The result is a much smaller method which uses only the add method to implement multiplication.
    – rsp
    Jan 23, 2010 at 9:57
  • just found that it crashes when multiplied numbers end in 0 or both have zeros, ie 100*110 :/
    – sasklacz
    Jan 24, 2010 at 17:49
0

Since this is homework... Are you sure using an int array is your best shot?
I tried to implement something similar a year ago for performance in a research
project, and we ended up going with concatenated primitives..

Using this you can take advantage of what's already there, and "only" have to worry about overflows near the ends.. This might prove to be fairly simple when you implement your multiplication with <<'s (bit shift lefts) and additions..

Now if you want a real challenge try to implement a modulo... ;)

3
  • concatenated primitives.. page not found.
    – Pacerier
    Dec 5, 2011 at 5:44
  • @Pacerier Fixed: Apparently SE broke one of it's own internal links.. That's bad.
    – Tim
    Dec 5, 2011 at 8:35
  • The link to concatenated primitives says "question removed due to reasons of moderation". Jun 23, 2012 at 10:57
0

You can check the below solution which teaches us both multiplication and addition of bigger numbers. Please comment if it can be improved.

public static void main(String args[]) {

    String s1 = "123666666666666666666666666666666666666666666666669999999999999999999999999666666666666666666666666666666666666666666666666666666666666666666";
    String s2 = "45688888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888";
    System.out.println(multiply(s1, s2));
}

private static String multiply(String s1, String s2) {

    int[] firstArray = convert(s1);
    int[] secondArray = convert(s2);
    //System.out.println(Arrays.toString(firstArray));
    //System.out.println(Arrays.toString(secondArray));
    // pass the arrays and get the array which is holding the individual
    // rows while we multiply using pen and paper
    String[] result = doMultiply(firstArray, secondArray);
    //System.out.println(Arrays.toString(result));

    // Now we are almost done lets format them as we like

    result = format(result);
    //System.out.println(Arrays.toString(result));

    //Add elements now and we are done
    String sum="0";
    for(String s:result){
        sum=add(sum,s);
    }

    return sum;
}

private static String[] doMultiply(int[] firstArray, int[] secondArray) {

    String[] temp = new String[secondArray.length];

    for (int i = secondArray.length - 1; i >= 0; i--) {

        int result = 0;
        int carry = 0;
        int rem = 0;
        temp[secondArray.length - 1 - i] = "";
        for (int j = firstArray.length - 1; j >= 0; j--) {
            result = (secondArray[i] * firstArray[j]) + carry;
            carry = result / 10;
            rem = result % 10;
            temp[secondArray.length - 1 - i] = rem
                    + temp[secondArray.length - 1 - i];
        }
        // if the last carry remains in the last digit
        if (carry > 0)
            temp[secondArray.length - 1 - i] = carry
                    + temp[secondArray.length - 1 - i];
    }

    return temp;
}

public static int[] convert(String str) {

    int[] arr = new int[str.length()];
    for (int i = 0; i < str.length(); i++) {
        arr[i] = Character.digit(str.charAt(i), 10);
    }

    return arr;
}

private static String[] format(String[] result) {

    for (int i = 0; i < result.length; i++) {
        int j = 0;
        while (j < i) {
            result[i] += "0";
            j++;
        }
    }

    return result;
}

public static String add(String num1, String num2) {

    //System.out.println("First Number :" + num1);
    //System.out.println("Second Number :" + num2);

    int max = num1.length() > num2.length() ? num1.length() : num2.length();

    int[] numArr1 = new int[max];
    int[] numArr2 = new int[max];

    for (int i = 0; i < num1.length(); i++) {
        numArr1[i] = Integer.parseInt(""
                + num1.charAt(num1.length() - 1 - i));
    }
    for (int i = 0; i < num2.length(); i++) {
        numArr2[i] = Integer.parseInt(""
                + num2.charAt(num2.length() - 1 - i));
    }

    int carry = 0;
    int[] sumArr = new int[max + 1];

    for (int k = 0; k < max; k++) {
        int tempsum = numArr1[k] + numArr2[k] + carry;
        sumArr[k] = tempsum % 10;
        carry = 0;
        if (tempsum >= 10) {
            carry = 1;
        }
    }
    sumArr[max] = carry;

/*  System.out.println("Sum :"
            + new StringBuffer(Arrays.toString(sumArr)).reverse()
            .toString().replaceAll(",", "").replace("[", "")
            .replace("]", "").replace(" ", ""));*/
    return new StringBuffer(Arrays.toString(sumArr)).reverse().toString()
            .replaceAll(",", "").replace("[", "").replace("]", "")
            .replace(" ", "");
}
0

I think this will help you

import java.util.ArrayList;
import java.util.List;

public class Multiply {


static int len;
public static void main(String[] args) {
      System.out.println(multiply("123456789012345678901","123456789012345678901");
}

private static ArrayList<Integer> addTheList(List<ArrayList<Integer>> myList) {
    ArrayList<Integer> result=new ArrayList<>();

    for(int i=0;i<len;i++)
    {
        result.add(0);

    }
    int index=0;
    for(int i=0;i<myList.size();i++)
    {
        ArrayList<Integer> a=new ArrayList<>(myList.get(index));
        ArrayList<Integer> b=new ArrayList<>(myList.get(index+1));
        for (int j = 0; j < a.size()||j < b.size(); i++) {
            result.add(a.get(i) + b.get(i));
    }

    }

    return result;
}

private static ArrayList<Integer> multiply(ArrayList<Integer> list1, Integer integer) {
    ArrayList<Integer> result=new ArrayList<>();
    int prvs=0;
    for(int i=0;i<list1.size();i++)
    {
        int sum=(list1.get(i)*integer)+prvs;
        System.out.println(sum);
        int r=sum/10;
        int m=sum%10;

        if(!(r>0))
        {

            result.add(sum);                
        }
        else
        {
            result.add(m);
            prvs=r;
        }
        if(!(i==(list1.size()-1)))
        {
            prvs=0;
        }

    }
    if(!(prvs==0))
    {
        result.add(prvs);
    }
    return result;
}

private static ArrayList<Integer> changeToNumber(String str1) {
    ArrayList<Integer> list1=new ArrayList<>();
    for(int i=0;i<str1.length();i++)
    {

        list1.add(Character.getNumericValue(str1.charAt(i)));
    }
    return list1;

}
public static String multiply(String num1, String num2) {
    String n1 = new StringBuilder(num1).reverse().toString();
    String n2 = new StringBuilder(num2).reverse().toString();

    int[] d = new int[num1.length()+num2.length()];

    //multiply each digit and sum at the corresponding positions
    for(int i=0; i<n1.length(); i++){
        for(int j=0; j<n2.length(); j++){
            d[i+j] += (n1.charAt(i)-'0') * (n2.charAt(j)-'0');
        }
    }

    StringBuilder sb = new StringBuilder();

    //calculate each digit
    for(int i=0; i<d.length; i++){
        int mod = d[i]%10;
        int carry = d[i]/10;
        if(i+1<d.length){
            d[i+1] += carry;
        }
        sb.insert(0, mod);
    }

    //remove front 0's
    while(sb.charAt(0) == '0' && sb.length()> 1){
        sb.deleteCharAt(0);
    }

    return sb.toString();
}
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.