-1

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.

Jens
  • 69,818
  • 15
  • 125
  • 179
Mahmut Mahmudov
  • 9
  • 7
  • 4
    Not checking all your code, your `uzunluk` function is wrong because it uses the value of uninitialized `lx` in calculation. – MikeCAT Jun 16 '21 at 15:07
  • 2
    *Integer divisions* are done in `floor(x/ust(10, ceil(n/2)))` and the results are truncated to integers, so the `floor` and `ceil` function won't work as expected. – MikeCAT Jun 16 '21 at 15:09
  • In addition to the bugs in the actual algorithm, try adding the character `'\n'` at the end of the printed string. `printf` is notorious for occasionally refusing to print strings which don't end with a `'\n'`. Hence the line should better be: `printf("%ld\n", karatsuba(837487, 368498));` – Stef Jun 16 '21 at 15:18
  • @MikeCAT has solved the not printing the result part but now it gives the wrong result. The printed result is a negative integer, where I dont even have a negative input :d – Mahmut Mahmudov Jun 16 '21 at 15:23
  • 2
    @MahmutMahmudov Please do not edit your code to fix bugs as people point them out. Now their comments are invalid. – Jonathon Reinhart Jun 16 '21 at 16:17
  • @JonathonReinhart sorry I'm new to this platform. Thanks for pointing that our – Mahmut Mahmudov Jun 16 '21 at 16:20
  • @JonathonReinhart tho only the first comment I've fixed – Mahmut Mahmudov Jun 16 '21 at 16:20
  • @JonathonReinhart Comments are temporary. As long as no one has answered the question, such edits are ok. – klutt Jun 16 '21 at 17:02
  • @MahmutMahmudov This kind of problem is easily solved with a debugger. I _strongly_ recommend that you learn how to use one because it will allow you to execute you code line by line and examine the variables in it to find out exactly where your mistakes are. – dandan78 Jun 16 '21 at 17:56
  • @MahmutMahmudov why all rookie Karatsuba implementation questions almost always use floating point for integer multiplication? and also using `/` or `pow` for multiplication is wrong too ... see [this implementation of karatsuba at the end](https://stackoverflow.com/q/18465326/2521214) for some inspiration – Spektre Jun 17 '21 at 07:38

1 Answers1

0

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

Mahmut Mahmudov
  • 9
  • 7