Algorithm

problem link- https://www.spoj.com/problems/VFMUL/

VFMUL - Very Fast Multiplication

#simple-math #big-numbers #karatsuba

 

Multiply the given numbers.

Input

n [the number of multiplications <= 101]

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

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

Output

The results of multiplications.

Example

Input:
5
4 2
123 43
324 342
0 12
9999 12345

Output:
8
5289
110808
0
123437655

Warning: large Input/Output data, be careful with certain languages

 

Code Examples

#1 Code Example with Java Programming

Code - Java Programming

import java.util.*;
import java.lang.*;
import java.math.BigInteger;
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
	Scanner s = new Scanner(System.in);
		int t = s.nextInt();
		while(t-- < 0){
			BigInteger n = s.nextBigInteger();
			BigInteger m = s.nextBigInteger();
			System.out.println(m.multiply(n));
		}	
	}
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
5
4 2
123 43
324 342
0 12
9999 12345

Output

x
–
+
cmd
8
5289
110808
0
123437655

#2 Code Example with C++ Programming

Code - C++ Programming

#include <cstdio>
#include <cstring>
#include <complex>
#include <vector>
#include <cmath>

using namespace std;

#define lowbit(x) (((x) ^ (x-1)) & (x))
typedef complex<long double> Complex;

void FFT(vector<Complex> &A, int s){
	int n = A.size(), p = 0;
	
	while(n>1){
	    p++;
	    n >>= 1;
	}
	
	n = (1<<p);
	
	vector<Complex> a = A;
	
	for(int i = 0; i < n; ++i){
		int rev = 0;
		for(int j = 0; j < p; ++j){
			rev <<= 1;
			rev |= ( (i >> j) & 1 );
		}
		A[i] = a[rev];
	}
	
	Complex w, wn;
	
	for(int i = 1; i <= p; ++i){
		int M = 1 << i;
		int K = M >> 1;
		wn = Complex( cos(s*2.0*M_PI/(double)M), sin(s*2.0*M_PI/(double)M) );
		for(int j = 0; j < n; j += M){
			w = Complex(1.0, 0.0);
			for(int l = j; l < K + j; ++l){
				Complex t = w;
				t *= A[l + K];
				Complex u = A[l];
				A[l] += t;
				u -= t;
				A[l + K] = u;
				w *= wn;
			}
		}
	}
	
	if(s==-1){
        for(int i = 0;i<n;++i)
            A[i] /= (double)n;
    }
}

vector<Complex> FFT_Multiply(vector<Complex> &P, vector<Complex> &Q){
    int n = P.size()+Q.size();
    while(n!=lowbit(n)) n += lowbit(n);
    
    P.resize(n,0);
    Q.resize(n,0);
    
    FFT(P,1);
    FFT(Q,1);
    
    vector<Complex> R;
    for(int i=0;i<n;i++) R.push_back(P[i]*Q[i]);
    
    FFT(R,-1);
    
    return R;
}

const long long B = 100000;
const int D = 5;

int main(){
    int n,l1,l2,L;
    char s1[10001],s2[10001];
    vector<Complex> P,Q,ans;
    vector<long long> N;
    
    scanf("%d",&n);
    
    for(int tc = 1;tc<=n;tc++){
        scanf("%s %s",s1,s2);
        l1 = strlen(s1);
        l2 = strlen(s2);
        
        P.clear(); Q.clear();
        
        for(int i = l1-1,val;i>=0;){
            val = 0;
            for(int j = D-1;j>=0;--j) if(i>=j) val = val*10+(s1[i-j]-'0');
            i -= D;
            P.push_back(Complex(val,0));
        }
        
        for(int i = l2-1,val;i>=0;){
            val = 0;
            for(int j = D-1;j>=0;--j) if(i>=j) val = val*10+(s2[i-j]-'0');
            i -= D;
            Q.push_back(Complex(val,0));
        }
        
        ans = FFT_Multiply(P,Q);
        L = ans.size();
        
        N.clear();
        for(int i = 0;i<L;++i) N.push_back((long long)round(real(ans[i])));
        
        for(;L>1 && N[L-1]==0;){
            N.pop_back();
            --L;
        }
        
        for(int i = 0;i<L;++i){
            if(N[i]>=B){
                if(i==L-1){
                    N.push_back(N[i]/B);
                    L++;
                }else N[i+1] += N[i]/B;
                N[i] %= B;
            }
        }
        
        for(int i = L-1;i>=0;--i){
            if(i<L-1){
                int d = 0, aux = N[i];
                
                if(aux>0){
                    while(aux>0){
                        aux /= 10;
                        ++d;
                    }
                }else d = 1;
                
                for(int j = d;j<D;++j) printf("0");
            }
            printf("%lld",N[i]);
        }
        printf("\n");
    }
    
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
5
4 2
123 43
324 342
0 12
9999 12345

Output

x
–
+
cmd
8
5289
110808
0
123437655
Advertisements

Demonstration

SPOJ Solution-Very Fast Multiplication-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python