long integer multiplication

Question

I am preparing the interview questions not for homework. There is one question about how to multiple very very long integer. Could anybody offer any source code in C++ to learn from? I am trying to reduce the gap between myself and others by learning other's solution to improve myself.

Thanks so much!

Sorry if you think this is not the right place to ask such questions.

Answer 1

This solution is good for very very big numbers but not so effective for factorial calculation of very big numbers. Hope it will help someone.

#include <iostream>
#include <string>

using namespace std;

string addition(string a, string b) {

    string ans = "";
    int i, j, temp = 0;

    i = a.length() - 1;
    j = b.length() - 1;

    while (i >= 0 || j >= 0) {
        if (i >= 0 && a[i])
            temp += a[i] - '0';
        if (j >= 0 && b[j])
            temp += b[j] - '0';
            int t = (temp % 10);
            char c = t + '0';
            ans = ans + c;
            temp = temp / 10;
            i--;
            j--;
    }
    while (temp > 0) {
        int t = (temp % 10);
        char c = t + '0';
        ans = ans + c;
        temp = temp / 10;
    }
    string fnal = "";

    for (int i = ans.length() - 1;i >= 0;i--) {
        fnal = fnal + ans[i];
    }

   return fnal;
}

string multiplication(string a, string b) {
    string a1, b1 = "0";
    int i, j, temp = 0, zero = 0;
    i = a.length() - 1;

    int m1, m2;
    while (i >= 0) {
        a1 = "";
        m1 = a[i] - '0';
        j = b.length() - 1;
        while (j >= 0) {
            m2 = b[j] - '0';
            temp = temp + m1*m2;
            int t = temp % 10;
            char c = t + '0';
            a1 = a1 + c;
            temp = temp / 10;
            j--;
        }
        while (temp > 0) {
            int t = (temp % 10);
            char c = t + '0';
            a1 = a1 + c;
            temp = temp / 10;
        }

        string fnal = "";
        // reverse string
        for (int i = a1.length() - 1;i >= 0;i--) {
            fnal = fnal + a1[i];
        }
        a1 = fnal;
        //add zero
        for (int p = 0;p < zero;p++)
            a1 = a1 + '0';
        b1 = addition(a1, b1);
        i--;
        zero++;
    }

    return b1;
}

 // upto 50 is ok
int factorial(int n) {
    string a = "1";
    for (int i = 2;i <= n;i++) {
        string b = to_string(i);
        a = multiplication(a, b);
    }
    cout << a << endl;
    return a.length();
}

int main() {
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    int n;
    cin >> n;
    //cout << factorial(n) << endl;

    string a, b;
    a = "1281264836465376528195645386412541764536452813416724654125432754276451246124362456354236454857858653";
    b = "3767523857619651386274519192362375426426534237624548235729562582916259723586347852943763548355248625";

    //addition(a, b);
    cout << multiplication(a, b);

    return 0;
}

Answer 2

Try this:

//------------DEVELOPED BY:Ighit F4YSAL-------------
#include<iostream>
#include<string>
#include<sstream>


#define BIG 250 //MAX length input

using namespace std;

int main(){
    int DUC[BIG][BIG*2+1]={0},n0[BIG],n1[BIG],i,t,h,carry=0,res;
    string _n0,_n1;
    while(1){
    //-----------------------------------get data------------------------------------------
    cout<<"n0=";
    cin>>_n0;
    cout<<"n1=";
    cin>>_n1;
    //--------------------string to int[]----------------------------------------
    for(i=_n0.length()-1,t=0;i>=0,t<=_n0.length()-1;i--,t++){
    n0[i]=_n0[t]-'0';
    }
    i=0;
    for(i=_n1.length()-1,t=0;i>=0,t<=_n1.length()-1;i--,t++){
    n1[i]=_n1[t]-'0';
    }
    i=0;t=0;
    //--------------------------produce lines of multiplication----------------
    for(i=0;i<=_n1.length()-1;i++){
        for(t=0;t<=_n0.length()-1;t++){
          res=((n1[i]*n0[t])+carry);
          carry=(res/10);
          DUC[i][t+i]=res%10;
         }
      DUC[i][t+i]=carry;
      carry=0;
    }
    i=0;t=0;res=0;carry=0;
    //-----------------------------add the lines-------------------------------
    for(i=0;i<=_n0.length()*2-1;i++){
       for(t=0;t<=_n1.length()-1;t++){
         DUC[BIG-1][i]+=DUC[t][i];
          //cout<<DUC[t][i]<<"-";
        }
        res=((DUC[BIG-1][i])+carry);
        carry=res/10;
        DUC[BIG-1][i]=res%10;
        //cout<<" ="<<DUC[BIG-1][i]<<endl;
    }
    i=0;t=0;
    //------------------------print the result------------------------------------
    cout<<"n1*n0=";
    for(i=_n0.length()*2-1;i>=0;i--){
        if((DUC[BIG-1][i]==0) and (t==0)){}else{cout<<DUC[BIG-1][i];t++;}
       //cout<<DUC[BIG-1][i];
    }
    //-------------------------clear all-------------------------------------
    for(i=0;i<=BIG-1;i++){
       for(t=0;t<=BIG*2;t++){
        DUC[i][t]=0;
    }
    n0[i]=0;n1[i]=0;
    }
    //--------------------------do it again-------------------------------------
    cout<<"\n------------------------------------------------\n\n";
    }
  return 0;
}

Answer 3

you can use GNU Multiple Precision Arithmetic Library for C++.

If you just want an easy way to multiply huge numbers( Integers ), here you are:

#include<iostream>

#include<string>
#include<sstream>
#define SIZE 700

using namespace std;



class Bignum{

    int no[SIZE];   


    public:

        Bignum operator *(Bignum& x){ // overload the * operator
        /*
            34 x 46
            -------
               204          // these values are stored in the
              136           // two dimensional array mat[][];
            -------
             1564   // this the value stored in "Bignum ret"
        */                              
    Bignum ret;             
    int carry=0;
    int mat[2*SIZE+1][2*SIZE]={0};
    for(int i=SIZE-1;i>=0;i--){
        for(int j=SIZE-1;j>=0;j--){
            carry += no[i]*x.no[j];
            if(carry < 10){
                mat[i][j-(SIZE-1-i)]=carry;
                carry=0;
            }
            else{
                mat[i][j-(SIZE-1-i)]=carry%10;
                carry=carry/10;
            }
        }
    }
    for(int i=1;i<SIZE+1;i++){
        for(int j=SIZE-1;j>=0;j--){
            carry += mat[i][j]+mat[i-1][j];

            if(carry < 10){

                mat[i][j]=carry;

                carry=0;

            }

            else{

                mat[i][j]=carry%10;

                carry=carry/10;

            }
        }
    }
    for(int i=0;i<SIZE;i++)
        ret.no[i]=mat[SIZE][i];
    return ret;
}

Bignum (){

    for(int i=0;i<SIZE;i++)

        no[i]=0;

}


Bignum (string _no){

    for(int i=0;i<SIZE;i++)

        no[i]=0;

    int index=SIZE-1;

    for(int i=_no.length()-1;i>=0;i--,index--){

        no[index]=_no[i]-'0';

    }

}


void print(){

    int start=0;

    for(int i=0;i<SIZE;i++)

    if(no[i]!=0){

        start=i;

        break;      // find the first non zero digit. store the index in start.

    }

    for(int i=start;i<SIZE;i++) // print the number starting from start till the end of array.

        cout<<no[i];

    cout<<endl;

    return;

}
 };


 int main(){

Bignum n1("100122354123451234516326245372363523632123458913760187501287519875019671647109857108740138475018937460298374610938765410938457109384571039846");
Bignum n2("92759375839475239085472390845783940752398636109570251809571085701287505712857018570198713984570329867103986475103984765109384675109386713984751098570932847510938247510398475130984571093846571394675137846510874510847513049875610384750183274501978365109387460374651873496710394867103984761098347609138746297561762234873519257610");

Bignum n3 = n1*n2;
n3.print();

return 0;

  }

as you can see, it's multiply 2 huge integer :) ... (up to 700 digits)