时间戳

首页 > 解决方案 > 你能发现我在 Karatsuba 算法的 C 实现中犯的错误吗

c - 你能发现我在 Karatsuba 算法的 C 实现中犯的错误吗

问题描述

我需要将 karatsuba 算法实现为我的家庭作业的 ac 代码，我进行了研究并提出了以下代码：

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) 是获得数 x 幂的函数：

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

uzunluk(x) 获取给定输入中的位数：

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

问题是这段代码什么也没打印：D如果有人能发现我犯的错误，我会很高兴。

标签： calgorithmmultiplicationkaratsuba

解决方案

所以问题是在长整数识别下，7位数字的乘法不正确。当我将其更改为 long long int 时，它开始正常工作。谢谢大家的帮助

推荐阅读