Karatsuba 实现 C++

Question

所以我决定尝试用 C++ 实现 Karatsuba 的算法（自从我上辈子第二次编码 class 以来就没有使用过这种语言，所以我非常非常生疏）。好吧，无论如何，我相信我已经逐行遵循了伪代码，但我的算法仍然不断弹出错误答案。


    x = 1234, y = 5678
    Actual Answer: x*y ==> 7006652
    Program output: x*y ==> 12272852

*注意：我在运行上 mac 并使用以下命令创建运行 c++ -std=c++11 -stdlib=libc++ karatsuba.cpp

的可执行文件

任何人，这是起草的代码，请随时指出我做错了什么或如何改进 c++。

谢谢！

代码：

    #include <iostream>
    #include <tuple>
    #include <cmath>
    #include <math.h>
    
    using namespace std;
    
    /** Method signatures **/
    tuple<int, int> splitHalves(int x);
    int karatsuba(int x, int y, int n);
    
    int main()
    {
        int x = 5678;
        int y = 1234;
        int xy = karatsuba(x, y, 4);
        cout << xy << endl;
        return 0;
    }
    
    int karatsuba(int x, int y, int n)
    {
        if (n == 1)
        {
            return x * y;
        }
        else
        {
            int a, b, c, d;
            tie(a, b) = splitHalves(x);
            tie(c, d) = splitHalves(y);
            int p = a + b;
            int q = b + c;
            int ac = karatsuba(a, c, round(n / 2));
            int bd = karatsuba(b, d, round(n / 2));
            int pq = karatsuba(p, q, round(n / 2));
            int acbd = pq - bd - ac;
            return pow(10, n) * ac + pow(10, round(n / 2)) * acbd + bd;
        }
    }
    
    
    /** 
     * Method taken from 
     */
    tuple<int, int> splitHalves(int x)
    {
        const unsigned int Base = 10;
        unsigned int divisor = Base;
        while (x / divisor > divisor)
            divisor *= Base;
        return make_tuple(round(x / divisor), x % divisor);
    }

Answer 1

你的代码有很多问题...

首先，你这里的系数有误：

            int q = b + c;

必须是：

            int q = c + d;

接下来，splitHalves 的实现不做这项工作。试试看：

tuple<int, int> splitHalves(int x, int power)
{
        int divisor = pow(10, power);
        return make_tuple(x / divisor, x % divisor);
}

这将为您的输入提供“正确”答案，但是...这不是 Karatsuba 方法。

首先，请记住您不需要“一分为二”。考虑 12 * 3456。将第一个数字分成两半意味着 a = 0、b = 12，而您的实现给出 a = 1、b = 2.

总体而言，Karastuba 使用数组，而不是整数。

Karatsuba 实现 C++

Karatsuba Implementation C++

c++

implementation

karatsuba