1 / 2
Feb 2012

#include<cstdio>
#include<iostream>
#include<string>
#include<cstdlib>
#include<cstring>
using namespace std;
inline int toint(char c)
{
    return c - '0';
}
inline char tochar(int c)
{
    return '0' + c;
}
void mult(string a, string b,int m, int n,int w[][20001],int num)
{
    int k,buff,t;
for(int j = n-1;j>=0;j--)
{
   k = 0;
   for(int i = m-1;i>=0;i--)
   {
        t = toint(a[i])*toint(b[j]) + w[num][i+j+1] + k;
        buff = t%10;
        k = t/10;
        w[num][i+j+1] = buff;
   }
   w[num][j] = k;
}
for (int i = 0;i<m+n;i++)
    cout << w[num][i];
cout << endl;
}
int main(int argc,char** argv){
    string str_num;
    int num,m,n;
    getline(cin,str_num);
    num = atoi(str_num.c_str());
    string s1,s2;
    static int w[1001][20001] = {{0}};
    //static int a[1001][10001] = {{0}};
    //static int b[1001][10001] = {{0}};
    int idx = 0;
    while(idx < num) {
        getline(cin,s1,' ');
        getline(cin,s2);
        m = s1.size();
        n = s2.size();
        mult(s1,s2,m,n,w,idx);
        idx++;
    }
    return 1;
}

I don't get it. Why is this too slow for even TMUL ? I thought this is a algorithm with \theta(m*n) complexity ? Isn't it ?

  • created

    Feb '12
  • last reply

    Feb '12
  • 1

    reply

  • 144

    views

  • 2

    users

Suggested Topics

Topic Category Replies Views Activity
C and C++ 0 17 11d

Want to read more? Browse other topics in C and C++ or view latest topics.