Geek Answers Handbook

Long integer multiplication

I am not preparing interview questions for homework. There is one question about how a multiple is very long integer. Can anyone suggest C ++ source code for learning? I am trying to narrow the gap between myself and others by exploring another solution to improve myself.

Many thanks!

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

+4
source share
2 answers

you can use the GNU multicast arithmetic library for C ++.

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

#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 multiplies 2 huge integers:) ... (up to 700 digits)

+4
source

Try the following:

 //------------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; }
+1
source

More articles:


All Articles