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?

You didn't test your code for enough inputs. If you do that you will see that you are using the wrong type for the input. An `int` cannot hold "l1 l2 [numbers to multiply (at most 10000 decimal digits each)]". — 463035818_is_not_an_ai, Dec 05 '20 at 12:16
Read ["Why should I not #include ?"](https://stackoverflow.com/questions/31816095) and ["Why is “using namespace std;” considered bad practice?"](https://stackoverflow.com/questions/1452721) — JHBonarius, Dec 05 '20 at 12:16
you were optimizing on the wrong end. The trick is to handle numbers with large number of digits, not to beat the built in `*` for integers — 463035818_is_not_an_ai, Dec 05 '20 at 12:18
do you really expect `karatsuba_multiply(x,y)` to be faster than `x*y` for `int`s ? — 463035818_is_not_an_ai, Dec 05 '20 at 12:21
Does this answer your question? [Karatsuba C++ Implementation](https://stackoverflow.com/questions/19841186/karatsuba-c-implementation) — JHBonarius, Dec 05 '20 at 12:27
@JHBonarius not really a dupe. I believe that OPs implementation is correct, it just doesnt do what the problem description is asking for — 463035818_is_not_an_ai, Dec 05 '20 at 12:31
@largest_prime_is_463035818 tagged the dupe because it's about bigint numbers. — JHBonarius, Dec 05 '20 at 12:33
@JHBonarius it is related I agree, but how to implement the bigint part isnt adresses in the answer. Nevermind, I only wrote the answer, because I didn't find the proper close reason, perhaps the dupe is just fine — 463035818_is_not_an_ai, Dec 05 '20 at 12:34
If you read the bold text at the link you posted: **Warning: large Input/Output data, be careful with certain languages** -- That's why your solution may not work for C++. Suggest you use another language, or take the time to write your own big integer class. I could post a solution using `boost::multiprecision`, but I don't know if that online compiler will accept it. — PaulMcKenzie, Dec 05 '20 at 13:34

score 1 · Answer 1 · answered Dec 05 '20 at 19:43

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

score 0 · Answer 2 · answered Dec 05 '20 at 12:23

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.

Fast Multiplication on SPOJ

2 Answers2