large integers in c++

general
1

how do i make calculations on large integers in c++???
for eg. 1000000*2000000

i am using long long int but getting a -ve answer…

1 Like
2

You can download or multiply(or add) as strings, like in second or third grade of primary school :slight_smile:

3

yeah i could do that but i need to store my result in some variable and so i will need something like long long int…
To be precise i need to store 12 digits in my variable.

4

I think unsigned long long is up to 10^18, but im not sure :slight_smile:

1 Like
5

Use the Elementary school approach.

For Example ,you want to multiply abcdef and ijkl
.
Store abcdef in char array say S1.

Store ijkl in char array say S2.

Multiply (f,l),(e,l),(d,l),(c,l),(b,l),(a,l) and store the result in R1 array.

Similarly Multiply (f,k),(e,k),(d,k),(c,k),(b,k),(a,k) and store the result in R2 array.

…

Multiply (f,i),(e,i),(d,i),(c,i),(b,i),(a,i) and store the result in R4 array.

Add ith member of each R1,R2,R3 and R4 array ,like the multiplictaion method taught in high school.

This is the c++ code that multiply two 1000(The limit can be maximise by changing MAX macro) digits long number.

     	/****** Big Number Multiplication *********************/
	#include<stdio.h>
	#include<stdlib.h>
	#include<string.h>
	#include<math.h>
	#define MAX 1000
	/******************************************************************/
	void reverse(char *from, char *to )
	{
		int len=strlen(from);
		int l;
		for(l=0;l<len;l++)
			to[l]=from[len-l-1];
		to[len]='\0';
	}
	/******************************************************************/
	void call_mult(char *first,char *sec,char *result){
		char F[MAX],S[MAX],temp[MAX];
		int f_len,s_len,f,s,r,t_len,hold,res;
		f_len=strlen(first);
		s_len=strlen(sec);
		reverse(first,F);
		reverse(sec,S);
		t_len=f_len+s_len;
		r=-1;


		for(f=0;f<=t_len;f++)
			temp[f]='0';
		temp[f]='\0';
		for(s=0;s<s_len;s++){
			hold=0;
			for(f=0;f<f_len;f++){
				res=(F[f]-'0')*(S[s]-'0') + hold+(temp[f+s]-'0');
				temp[f+s]=res%10+'0';
				hold=res/10;
				if(f+s>r) r=f+s;
			}
			while(hold!=0){
				res=hold+temp[f+s]-'0';
				hold=res/10;
				temp[f+s]=res%10+'0';
				if(r<f+s) r=f+s;
				f++;
			}
		}
		for(;r>0 && temp[r]=='0';r--);
		temp[r+1]='\0';
		reverse(temp,result);
	}
	/***************************************************************/
	int main(){
		char fir[MAX],sec[MAX],res[MAX];
		while(scanf("%s%s",&fir,&sec)==2){
			call_mult(fir,sec,res);
			int len=strlen(res);
			for(int i=0;i<len;i++) printf("%c",res[i]);
			printf("\n");
		}
		return 0;
	}
5 Likes
6

try this simple naive approach:


void multiply(string s1,string s2){
	string ss;
	int c = 0;
	for(int i=s2.length()-1;i>=0;i--){
		int carry=0;
		string s;
		for(int j=s1.length()-1;j>=0;j--){
			int n=((s1[j]-48)*(s2[i]-48))+carry;
			s.push_back((n % 10)+48);
			carry=n/10;
		}
		while(carry){
			s.push_back((carry % 10)+48);
			carry /= 10;
		}
		c++;
		if (c > 1) 
		{
			for (int m = 0;m < c - 1;m++)s.insert(s.begin(), '0');
			carry = 0;
			for (int i = 0,j=0;i<s.length();i++,j++) {
				if (j <ss.length())
				{
					int n = (ss[j] - 48) + (s[i] - 48) + carry;
					ss[j] = (n % 10) + 48;
					carry = n / 10;
				}
				else
				{
					int n = (s[i] - 48) + carry;
					ss.push_back((n % 10) + 48);
					carry = n / 10;
				}
			}
			while (carry) {
				ss.push_back((carry % 10) + 48);
				carry /= 10;
			}
		}
		if (c == 1) {
			ss = s;
		}
	}
	reverse(ss.begin(), ss.end());
	cout << ss << endl;;
}