@james curran: I was trying to solve the TMUL problem in spoj. I think
requires Karatsuba algorithm. I'm sure that my algorithm is fine. But
i get runtime error SIGABRT. that's y i'm asking.
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
class bigint{
public:
int len;
int *num;
bigint(){
len=1;
num=new int[1];
num[0]=0;
}
bigint(int x){
num=new int[x];
len=x;
}
bigint(char *str){
int i;
len=strlen(str);
num=new int[len];
for(i=0;i<len;i++)
num[i]=((int)str[i])-48;
}
void clear(){
int i,j;
for(i=0;i<len && num[i]==0 ;i++);
len-=i;
for(j=0;j<len;j++)
num[j]=num[j+i];
if(len==0)
{
len=1;
num[0]=0;
}
}
bigint( bigint & copy){
int i;
len=copy.len;
num=new int[len];
for(i=0;i<len;i++)
num[i]=copy.num[i];
}
void operator =(bigint & another){
int i;
len=another.len;
free(num);
num=new int[len];
for(i=0;i<len;i++)
num[i]=another.num[i];
}
void operator = ( char *s){
int i;
len=strlen(s);
num=new int[len];
for(i=0;i<len;i++)
num[i]=(int)(s[i])-48;
}
void print(){
int i;
for(i=0;i<len;i++)
cout<<num[i];
}
char* operator + (bigint other){
int swapped=0,carry=0,i,j,k,resultlength=
len>other.len? len+1 : other.len+1;
bigint result(resultlength),temp(resultlength);
k=result.len-1;
//making the number having more length as the first
number
if(len<other.len) {
swapped=1;
temp=(*this);
(*this)=other;
other=temp;
}
//adding until equal length
for(i=len-1,j=other.len-1;j>=0;j--,i--,k--)
{
result.num[k]=num[i]+other.num[j]+carry;
if(result.num[k]>9){
result.num[k]-=10;
carry=1;
}
else carry=0;
}
//remaining numbers in the first number...
for(;i>=0;i--,k--){
result.num[k]=carry+num[i];
if(result.num[k]>9){
result.num[k]-=10;
carry=1;
}
else carry=0;
}
if(carry==0){
for(i=0;i<result.len-1;i++)
result.num[i]=result.num[i+1];
result.len--;
}
else
result.num[0]=1;
// result.print(); cout<<endl;
char * resultstring=new char[result.len+1];
for(i=0;i<result.len;i++)
resultstring[i]=(char)(result.num[i]+48);
resultstring[i]='\0';
if(swapped==1){
bigint temp= (*this);
*this= other;
other= temp;
swapped=0;
}
return resultstring;
}
void operator * (bigint other){
bigint result(other.len+len);
int carry,l,i,j,k,tempnum;
char * resultstring;
bigint tempresults[other.len]; //declaring an
for(i=0;i<result.len;i++)
result.num[i]=0;
for(i=0;i<other.len;i++) //finding all the
tempresults
{ carry=0;
tempnum=other.num[other.len-i-1];
//current multiplier
//cout<<"tempnum=" <<tempnum<<endl;
tempresults[i].len=len+i+1;
//allocating memory for tempbigints
tempresults[i].num=new
int[tempresults[i].len];
for(k=tempresults[i].len-1,l=len-1;
l>=0;k--){
if(k>len)
{
tempresults[i].num[k]=0;
continue;
}
else{
tempresults[i].num[k]=(tempnum*num[l--])+carry;
if(tempresults[i].num[k]>9){
carry=tempresults[i].num[k]/10;
//
cout<<"carry="<<carry<<endl;
tempresults[i].num[k]
%=10;
}
else
carry=0;
}
}
if(carry==0){
tempresults[i].len--;
for(j=0;j<tempresults[i].len;j
++)
tempresults[i].num[j]=tempresults[i].num[j+1];
}
else
tempresults[i].num[0]=carry;
// tempresults[i].();
}
for(i=0;i<other.len;i++){
result=result+tempresults[i];
free(tempresults[i].num);
}
result.clear();
result.print();
// free(result.num);
}
// ~bigint(){free(num);}
};
char s1[10005],s2[10005];//=new char[2000],*s2=new char [2000];
int main(){
int t;
cin>>t;
while(t--){
fflush(NULL);
cin>>s1>>s2;
bigint A(s1), B(s2);
A*B;
cout<<endl;
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
