Created
August 5, 2012 11:06
-
-
Save jargnar/3263916 to your computer and use it in GitHub Desktop.
Ridiculously Large Number Multiplication (with C++ Strings)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <string> | |
#define OVERFLOW 2 | |
#define ROW b_len | |
#define COL a_len+b_len+OVERFLOW | |
using namespace std; | |
int getCarry(int num) { | |
int carry = 0; | |
if(num>=10) { | |
while(num!=0) { | |
carry = num %10; | |
num = num/10; | |
} | |
} | |
else carry = 0; | |
return carry; | |
} | |
int num(char a) { | |
return int(a)-48; | |
} | |
string mult(string a, string b) { | |
string ret; | |
int a_len = a.length(); | |
int b_len = b.length(); | |
int mat[ROW][COL]; | |
for(int i =0; i<ROW; ++i) { | |
for(int j=0; j<COL; ++j) { | |
mat[i][j] = 0; | |
} | |
} | |
int carry=0, n,x=a_len-1,y=b_len-1; | |
for(int i=0; i<ROW; ++i) { | |
x=a_len-1; | |
carry = 0; | |
for(int j=(COL-1)-i; j>=0; --j) { | |
if((x>=0)&&(y>=0)) { | |
n = (num(a[x])*num(b[y]))+carry; | |
mat[i][j] = n%10; | |
carry = getCarry(n); | |
} | |
else if((x>=-1)&&(y>=-1)) mat[i][j] = carry; | |
x=x-1; | |
} | |
y=y-1; | |
} | |
carry = 0; | |
int sum_arr[COL]; | |
for(int i =0; i<COL; ++i) sum_arr[i] = 0; | |
for(int i=0; i<ROW; ++i) { | |
for(int j=COL-1; j>=0; --j) { | |
sum_arr[j] += (mat[i][j]); | |
} | |
} | |
int temp; | |
for(int i=COL-1; i>=0; --i) { | |
sum_arr[i] += carry; | |
temp = sum_arr[i]; | |
sum_arr[i] = sum_arr[i]%10; | |
carry = getCarry(temp); | |
} | |
for(int i=0; i<COL; ++i) { | |
ret.push_back(char(sum_arr[i]+48)); | |
} | |
while(ret[0]=='0'){ | |
ret = ret.substr(1,ret.length()-1); | |
} | |
return ret; | |
} | |
void printhuge(string a) { | |
cout<<"\n"; | |
for(string::iterator i = a.begin(); i!=a.end(); ++i) { | |
cout<<*i; | |
} | |
} | |
int main() { | |
string a,b; | |
cin>>a>>b; | |
printhuge(mult(a,b)); | |
return 0; | |
} |
Your code does not work properly. It has some bug.
I tested your code for the following two numbers:
3141592653589793238462643383279502884197169399375105820974944592
2718281828459045235360287471352662497757247093699959574966967627
Expected answer:
8539734222673567065463550869546574495034888535765114961879601127067743044893204848617875072216249073013374895871952806582723184
(result from https://defuse.ca/big-number-calculator.htm and cross checked on many other sites)
Your answer:
8539734222673567053353449726313700648237079222442681415309610037168088680449950537516095083561704540812373905871952806582723184
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Thank you...saved a few hours!...c++ should just integrate this into standard iostream like python and java....but I'm too lazy to email them and see what their response is...