Fast Multiplication on SPOJ

Question

I am solving FAST MULTIPLICATION on SPOJ. My solution looks like this:

#include<bits/stdc++.h>
using namespace std;
int max(int a,int b)
{
    if(a>b) return a;
    return b;
}
long karatsuba_multiply(int x,int y)
{
    if(x<10 or y<10) return x*y;
    int n=max(to_string(x).length(),to_string(y).length());
    int m=(int)ceil(n/2.0);
    long p=(long)pow(10,m);
    long a=(long)(floor(x/p));
    long b=x%p;
    long c=(long)(y/p);
    long d=y%p;
    long ac=karatsuba_multiply(a,c);
    long bd=karatsuba_multiply(b,d);
    long adbc=karatsuba_multiply(a+b,c+d)-ac-bd;
    return (long)(pow(10*1,2*m)*ac+pow(10*1,m)*adbc+bd);
}
int main()
{
    int a,b,t;
    cin>>t;
    while(t--)
    {
        cin>>a>>b;
        cout<<karatsuba_multiply(a,b)<<endl;
    }
    return 0;
}

This code is giving correct output on coding blocks IDE as well as other IDEs. But this solution is being marked wrong on SPOJ. Can anyone tell me what I am doing wrong?

Answer 1

From the problem description:

Input

n [the number of multiplications <= 1000]

l1 l2 [numbers to multiply (at most 10000 decimal digits each)]

Text grouped in [ ] does not appear in the input file.

A number with 10000 decimal digits is too large to fit in an int for typical sizes of int. You need to use a differnt type for the input and to carry out the multiplication. There is no built in type that can store integers that large.

Answer 2

C++ originally only supports the maximum length of unsigned long long integers as about 1.8e19.

According to the problem, the answer can shoot up to 1e100000000 which is far larger.

Ways to solve this are:

• Use Strings to store integers and use the operations on strings to multiply. You can check this article
• Use C++ boost library. This library supports integer operations beyond 1e19 limit.

Another method would be to use some other language which supports greater than 64-bit integer like Python or use BigInteger Class in Java