Can you please spot the error I made in C implementation of the Karatsuba algorithm

192 Views Asked by At

I need to implement the karatsuba algortihm into a c code for my homework and I did my research and came up with the following code:

long int karatsuba(long int x,long int y)
{
    if((x<10)||(y<10)) \\if the numbers have 1 digit, I just multiply them
        return x*y;
    else
    {
        long int a, b, c, d, ac, bd, z;
        int n=uzunluk(x);
        
        a=floor(x/ust(10, ceil(n/2)));
        b=x%ust(10, ceil(n/2));;
        c=floor(y/ust(10, ceil(n/2)));
        d=y%ust(10, ceil(n/2));;
        
        ac=a*c;
        bd=b*d;
        z=(a+b)*(c+d)-ac-bd;
    
        long int res=ust(10, 2*ceil(n/2))*ac+ust(10, ceil(n/2))*z+bd;
    
        return res;
    }       
}

int main(void)
{
    printf("%ld", karatsuba(837487, 368498));
    return 0;
}

ust(x, n) is the function to get the power of number x:

long int ust(long x, long n)
{
    long int res=1;
    int i;
    for(i=0; i<n; i++)
    {
        res*=x;
    }
    return res;
}

And the uzunluk(x) gets the number of digits in the given input:

int uzunluk(long int x)
{
    int lx;
    while(x>0)
    {
        x/=10;
        lx+=1;
    }
    return lx;      
}

the problem is this code prints nothing :D I would be glad if someone could spot the mistake I made.

1

There are 1 best solutions below

0
Mahmut Mahmudov On

So it comes out the problem was 7 digits numbers' multiplication does not result proper under the long integer identification. As I changed it to long long int, it started working properly. Thank you all for your help