Karatsuba乘法改进

-1

我实施了Karatsuba乘法算法来达到我的教育目标。现在我正在寻找更多的改进。我已经实现了某种长算术，并且它能够很好地工作，不管我使用的整数表示的基数是否超过。含底座和范围[10^50000, 10^50001]与clang++ -O3乘两个随机整数编译需要：Karatsuba乘法改进

Naive algorithm took me 1967 cycles (1.967 seconds) 
Karatsuba algorithm took me 400 cycles (0.4 seconds)

而基础相同的数字：

Naive algorithm took me 409 cycles (0.409 seconds) 
Karatsuba algorithm took me 140 cycles (0.14 seconds)

是否有改善的方法这个结果？现在我使用这些函数来完成我的结果：

void finalize(vector<int>& res) { 
    for (int i = 0; i < res.size(); ++i) { 
     res[i + 1] += res[i]/base; 
     res[i] %= base; 
    } 
}

正如你可以看到它进行计算，并把它推到下一个数字的每一步。如果我以>=1000为基数，结果将会溢出。

如果您在我的代码中看到我使用int向量来表示长整数。根据我的基数，一个数字将分成不同的部分。现在我看到几个选项：

使用long long类型载体，但它可能也将被溢出了广大长度整数
实现长期算术

随身携带的表示我参观过之后我决定扩大这个问题。假设我们想要将我们的长整数表示为一个整数的向量。对于instanse：

ULLONG_MAX = 18446744073709551615

而对于输入我们通过第210号Fibonacci数34507973060837282187130139035400899082304280不适合任何类型stadard。如果我们在基础千万为int的矢量代表它就会像：

v[0]: 2304280 
v[1]: 89908 
v[2]: 1390354 
v[3]: 2187130 
v[4]: 6083728 
v[5]: 5079730 
v[6]: 34

当我们做乘法，我们可能会（为简单起见，让它成为两个相同的数字） (34507973060837282187130139035400899082304280)^2：

v[0] * v[0] = 5309706318400 
... 
v[0] * v[4] = 14018612755840 
...

这只是第一行，我们必须做这六个步骤。当然，某些步骤会在乘法或进位计算后引起溢出。

如果我错过了什么，请告诉我，我会改变它。如果你想看到完整的版本，它是我的github

来源

2015-07-10 vpetrigo

如果你有工作代码，那么也许你的问题更适合http://codereview.stackexchange.com/？ – EdChum

我投票结束这个问题作为题外话，因为它属于codereview。在那里，你需要在你的帖子中发布代码，而不是链接到你的github。你只需要发布相关的部分。 – UmNyobe

如果你真的想加速，那么你应该使用另一种更快的算法：例如Toom-Cook或者傅立叶变换。 –

基地2^64和基地2^32是做高精度运算最受欢迎的基地。通常，这些数字存储在未签名的整型中，因为它们在溢出方面具有良好的语义。

例如，一种可以从除了检测进位，如下所示：

uint64_t x, y; // initialize somehow 
uint64_t sum = x + y; 
uint64_t carry = sum < x; // 1 if true, 0 if false

另外，汇编语言通常具有几个指令“进位加”;如果您可以编写内联汇编（或者可以访问内部函数），则可以利用这些优势。对于乘法，大多数计算机具有可以计算一个机器字 - >两个机器字产品的机器指令;有时候，获得两半的指令称为“乘法hi”和“乘法低”。您需要编写程序集来获取它们，尽管许多编译器提供了更大的整数类型，这些整数类型的使用可以让您访问这些指令：在gcc可以实现多重喜为

uint64_t mulhi(uint64_t x, uint64_t y) 
{ 
    return ((__uint128_t) x * y) >> 64; 
}

当人们无法利用这一点，他们在做2^32而是乘法，使他们能够使用相同的方法来实现便携式mulhi指令，使用uint64_t作为双数字类型。

如果你想编写高效的代码，你真的需要利用这些更大的乘法指令。基数2^32中的数字乘以比基数10中的数字乘以功能强九十倍以上。基数2^64中的数字乘以4倍。而且你的计算机可能比你在10次乘法中实现的更快。

来源

2015-07-10 10:28:18 Hurkyl

但正如我说我使用基于整数的向量长算术represend庞大的数字作为拥有超过20位甚至普通'uint64_t'类型不适合整。 – vpetrigo

@vpetrigo：但是'2^64'中的一个* 2 *位数字可以存储一个20位十进制数的数字。 – Hurkyl

Karatsuba乘法改进

回答

相关问题