long integer multiplication

Question

Hi,

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 article shows conceptually how you would multiply large integers

http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=641

Answer 2

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)