计算科学 - 具有复杂性的gcd最优算法 - 吾爱随笔录

计算科学优化算法参考请求复杂

2021-12-17 05:06:57

如果您有任何有用的资源，我想知道 gcd 的最佳优化算法及其复杂性，我很乐意看看它。

1个回答

当前最先进的技术使用欧几里得算法的变体。然而，它被证明是非最优的：

尽管它的变体具有显着的速度改进，但我还没有听说过顺序最优的变体。我想最好的修改之一是 Lehmer 算法。扩展欧几里得算法也值得一提。

此外，我猜想在并行机器上获得最优性，或者至少有保证的界限。其中一项深刻的工作证明了 O(n^2/log(n)) 的顺序复杂度，同时实现了并行复杂度，值得一看：

其它你可能感兴趣的问题