Reputation: 352
i created a small console app that multiply 2 long int number. i don't know where my problem is. this app work fine until the number of digits is 3.
but if number of digit was bigger than 3 , the app's output is wrong. :(
please show me where my problem is that i solve it.
here is my code:
int digits (int n)
{
int counter = 0;
while (n > 0)
{
n/=10;
counter++;
}
return counter;
}
long longMultiply(long a, long b)
{
const int S = 3;
int w,x,y,z;
int n = max(digits(a),digits(b));
if(a == 0 || b ==0) {
return 0;
} else if (n <= S) {
return a*b;
} else {
int m = (n/2);
//first number
x = a/(10^m);
y = a%(10^m);
//second number
w = b/(10^m);
z = b%(10^m);
return (longMultiply(x,w)*(10^(2*m)) + (longMultiply(x,z) + longMultiply(w,y)))*(10^m) + longMultiply(y,z) ;
}
}
int main() {
//digits(12345);
cout << longMultiply(100,100);
return 0;
}
Upvotes: 1
Views: 2597
Reputation: 1
It seems like your problem is in the logic of the else portion. It works up to 3 digits because it is simply outputting the product when that fails it runs your else block which I am not sure I understand. What exactly is setting m = n/2
trying to do?
Upvotes: 0
Reputation: 1517
If the product is less than or equal to 10 ^ 18 ; you can simply use
long long product = a * b ;
If a or b are greater than the range of long long ; one can simply take one as long long and another as string . Suppose a > 10^18 and b < 10^18 . The below code is valid only when b * 9 is in the range of long long .
string a ; long long b ;
cin >> a >> b ;
reverse ( a.begin() , a.end() ) ;
string prod ;
long long temp ,carry ;
temp = carry = 0 ;
for ( i = 0 ; i < a.length() ; i++ ){
temp = (a[i] - '0') * b + carry ;
prod += ( temp % 10 ) + '0' ;
carry = temp / 10 ;
}
while ( carry != 0 ){
prod += ( carry % 10 ) + '0' ;
carry /= 10 ;
}
reverse ( prod.begin() , prod.end() ) ;
cout << prod ; // this string contains the required product .
However if both are very big you can consider using a third party Big Integer Library. For external Big Integer Library you can consider using BOOST BigInteger Library , which is quite fast and highly tested.
Upvotes: 0
Reputation: 7068
10^m is not the m-th power of 10, in fact this is 10 xor'ed by m
You can use the pow
function from cmath library instead (http://www.cplusplus.com/reference/cmath/pow/), but it works on floating-point numbers.
Alternatively to get 10^m, you could simply multiply 1 m times by 10.
int m = (n/2);
long tenToM = 1;
for (int i=0; i<m; i++)
tenToM *= 10;
long tenToTwoM = tenToM * tenToM;
and then instead of 10^m
use tenToM
and instead of 10^(2*m)
use tenToTwoM
Upvotes: 8