How can I multiply really big numbers c++ [duplicate]

Question

I have the following code

int i, a, z;  
i = 2343243443;  
a = 5464354324324324;  
z = i * a;  
cout << z << endl;  

When these are multiplied it gives me -1431223188 which is not the answer. How can I make it give me the correct answer?

Jetta

Start by looking at #269768. If you don;t want to roll our own: boost.org/doc/libs/1_56_0/libs/multiprecision/doc/html/… – Shewmaker

You can try long int and long long int. If those are not big enough then you may want some kind of special library like: GNU MP (GMP) – Hydrofoil

Answer 1

As Jarod42 suggested is perfectly okay, but i am not sure whether overflow will take place or not ?

Try to store each and every digit of number in an array and after that multiply. You will definitely get the correct answer.

For more detail how to multiply using array follow this post http://discuss.codechef.com/questions/7349/computing-factorials-of-a-huge-number-in-cc-a-tutorial

Creath

2343243443 already overflows an int32 (but not an uint32), so yes, there is an overflow. – Ortegal

I'm interested in storing every number in an array then multiplying, but I can't figure it out. Pretty complex. – Jetta

Answer 2

The result overflows the int (and also std::uint64_t)

You have to use some BigInt library.

Ortegal

Answer 3

Use pan paper approach as we used in 2nd standard. Store two numbers in two different array in reverse order. And take ans array as size of (arr1.size + arr2.size).And also initilize ans array to zero.

In your case arr1[10]={3,4,4,3,4,2,3,4,3,2}, arr2[15]={4,2,3,4,2,3,,4,5,3,4,5,3,4,6,4,5};

for(int i=0;i<arr1_length;i++)
{
    for(int j=0;j<arr2_length;j++)
    {

        ans[i+j]+=arr1[i]*arr2[j];
        ans[i+j+1]=ans[i+j+1]+ans[i+j]/10;
        ans[i+j]%=10;
    }
}

Then ans array contain the result.Please print carefully ans array. it may contain leading zero.

Pendulum

Answer 4

ints only hold 32 bits. When the result of a multiplication is larger than 2^31 - 1, the result rolls over to a large negative value. Instead of using the int data type, use long long int, which holds 64 bits.

Floatation

Answer 5

You should first try to use 64-bit numbers (long or better, unsigned long if everything is positive). With unsigned long you can operate between 0 and 18446744073709551615, with long between -9223372036854775808 and 9223372036854775807.

If it is not enough, then there is no easy solution, you have to perform your operation at software level using arrays of unsigned long for instance, and overload "<<" operator for display. But this is not that easy, and I guess you are a beginner (no offense) considering the question you asked.

If 64-bit representation is not enough for you, I think you should consider floating-point representation, especially "double". With double, you can represent numbers between about -10^308 and 10^308. You won't be able to have perfectly accurate computatiosn on very large number (the least significant digits won't be computed), but this should be a good-enough option for whatever you want to do here.

Joell

Answer 6

First, you have to make your value long longs Second, you would want to add a (long long) in front of the multiplication. This is because when you have (ab) it returns an int therefore if you want it to return a long long you would want (long long)(ab).

Dogmatism

Hello! Couple of tips: please consider looking at unanswered questions before the answered ones; when considering to answer a question with an already accepted answer, please have a look at other answers before giving your own. – Turbo

Answer 7

I would like to elaborate on, and clarify Shravan Kumar's Answer using a full-fledged code. The code starts with a long integers a & b, which are multiplied using array, converted to a string and then back into the long int.

#include <iostream>
#include <string>
#include<algorithm>

using namespace std;

int main()
{
//Numbers to be multiplied
long a=111,b=100;

//Convert them to strings (or character array)
string arr1 = to_string(a), arr2 = to_string(b); 

//Reverse them
reverse(arr1.begin(), arr1.end());
reverse(arr2.begin(), arr2.end());

//Getting size for final result, just to avoid dynamic size
int ans_size = arr1.size() + arr2.size();

//Declaring array to store final result
int ans[ans_size]={0};

//Multiplying 
//In a reverse manner, just to avoid reversing strings explicitly 
for(int i=0; i<arr1.size();i++)
{
    for(int j=0; j<arr2.size();j++)
    {
        //Convert array elements (char -> int)
        int p = (int)(arr1[i]) - '0';
        int q = (int)(arr2[j]) - '0';

        //Excerpt from Shravan's answer above
        ans[i+j]+=p*q;
        ans[i+j+1]=ans[i+j+1]+ans[i+j]/10;
        ans[i+j]%=10;
    }
}

//Declare array to store string form of final answer
string s="";

for(auto i=0;i<ans_size; ++i)
    s += to_string(ans[i]); 

reverse(s.begin(), s.end() );

//If last element is 0, it should be skipped
if(s[0] =='0')
{
   string ss(s,1,s.size()-1);
   s=ss;
}

//Final answer
cout<< s;

return 0;
}

Primaveras

Answer 8

Use float instead. It can go up to about 3.4028235 × 10³⁸

Hypotaxis

Answer 9

// its may heplfull for you
#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;
}

Lewison

Answer 10

You can use queue data structure to find the product of two really big numbers with O(n*m). n and m are the number of digits in a number.

Familist

Wouldn't it be even cooler if you provided a C++ code snippet backing your answer? – Archespore