我正在寻找有关快速 GCD 计算算法的信息。特别是，我想看看它的实现。

对我来说最有趣的是： - Lehmer GCD 算法， - 加速 GCD 算法， - k-ary 算法， - 带有 FFT 的 Knuth-Schonhage。我完全没有关于加速 GCD 算法的信息，我只看过几篇文章，其中提到它是在中等输入（~1000 位）上最有效和最快速的 gcd 计算方法

从理论的角度来看，它们看起来对我来说很难理解。任何人都可以分享代码（最好在 c++ 上）实现列表中的任何算法\部分或分享任何这样做的经验。我也将不胜感激任何信息、评论、建议和地方调查。我有一个处理大整数的类，但我没有处理它的方法。当然，除了 Euclid 和 Binary gcd 算法，我现在看起来很清楚；没有问题。最后我想得到的主要内容：实现 lehmer gcd 的代码。（从列表中更容易）

我正在编写一个混合数字类，需要一个快速简单的“最大公约数”函数。谁能给我代码或代码链接？

我想在 Objective-C 中编写一个方法，它会产生一个文本字符串'a:b:c:d'。我有四个 UISteppers（它们的值分别显示在一个标签中）。我希望这四个数字的比率以它们的最低整数形式显示，包括如果有些是 0。

例如。a=6, b=4, c=0, d=0 文本字符串 = 3:2:0:0

我找到了各种查找最大公约数的方法，包括http://macscripter.net/viewtopic.php?id=35759。然而，我对iOS真的很陌生，这是我在Hello World之后的第一个应用程序，数学函数甚至声明一个方法，定义它和调用它仍然是一个谜。

你能帮忙吗？

我正在尝试解决SPOJ 问题 PGCD，它询问最大公约数表中出现了多少素数。

我想到的第一个想法是首先通过筛选生成素数。

然后，对于每个素数p，看看有多少对 ( a , b )，其中a和b小于给定的界限，满足GCD(a,b)=p。

例如，有多少对小于 (20, 20) 满足 GCD(a,b)=7？

当然，如前所述，a和b是有界的。

那么有可能逆转GCD吗？还是这个解决方案完全无效？

我决定实现一个程序，可以在 TI-Basic 中找到任意两个数字（包括非整数）的 GCD。我已经在 J​​ava 中很好地使用了它，所以我知道它可以工作。它在 TI-Basic 中运行良好，但与内置gcd(功能相比，它非常缓慢；该gcd(函数似乎在毫秒内得到结果，而我的可能需要几秒钟。为什么 TI-Basic 比预定义的计算器功能慢这么多？

编码

以下是 TI-Basic 中的程序代码，供您查看：

免责声明：这是我查看我的 TI-84 并在此处输入的结果。可能有一些错别字，尽管我尽力保持不变

对于那些可能不知道这意味着什么的人，下面提供了伪代码：

首先是一个小的澄清。我确实在这个问题上得到了 AC，但我更好的方法（这在数学上是等效的，我假设我的 AC 解决方案）是得到一个 WA 判决在 interviewstreet 中存在一个问题，如下所示：

有1个友好号码和N个不友好号码。我们想找出有多少数字正好整除友好数字，但不整除任何不友好数字。

输入格式：

输入的第一行包含两个由空格分隔的数字 N 和 K。N是不友好号码的数量，K是友好号码。输入的第二行包含 N 个空格分隔的不友好数字。

输出格式：

在一行中输出答案。

样本输入：

8 16
2 5 7 4 3 8 3 18

样本输出：

1

解释：

给定友好数字 16 的除数是 { 1, 2, 4, 8, 16 }，不友好数字是 { 2, 5, 7, 4, 3, 8, 3, 18 }。现在1整除所有不友好的数字，2整除2，4整除4，8整除8，但16不整除任何一个。因此，只有一个数字可以整除友好数字，但不整除任何不友好数字。所以答案是1。

我的算法（得到了 AC）如下：

1. 让可能的不友好数字输入[i] where 0<=i

2. 对于每个 input[i] 找到 gcd(input[i],k)。

3. 将范围 (0,n) 中所有 i 的 gcd(input[i],k) 的所有因子存储在一个集合中。让我们将此集合称为可能因子。

4. 对于 k 的每个因子，检查它是否除掉了可能因子中的任何元素。如果否，则增加答案计数

我修改了算法，假设如下：

不是将 gcd(input[i],k) 的所有因子存储在一个集合中，而是找出范围 (0,n) 中所有 i 的 gcd(input[i],k) 的 lcm。这可以通过以下 LOC 轻松完成

现在对于 k 的所有因素，检查它们是否划分 lcm。如果没有，则增加计数。

然而，这个假设给了我 WA。是因为我的逻辑有任何缺陷吗？如果是，请指出（如果可能，用数学证明）这两种方法有何不同？

这是我的代码，第二种方法供参考（以及可能的错误）

考虑 Euclid 算法的这种实现：

维基百科上的一个很好的证明表明，该算法“总是需要少于 O(h) 的除法，其中 h 是较小数字 b 中的位数”。

然而，在图灵机上，计算 mod b 的过程的时间复杂度为 O(a+b)。我的直觉和一些大型测试告诉我，欧几里德算法的复杂度在图灵机上仍然是 O(a+b)。

关于如何证明这一点的任何想法？

我是haskell的新手。我正在尝试编写一个 gcd 可执行文件。

当我编译此代码时，我收到以下错误。

我不明白我的问题出在哪里......这是我的代码。

我所知道的是，这read可以帮助我将字符串转换为 int。

通过这个程序，我打算找到两个数字的 GCD。但我得到的结果是“浮点异常（核心转储）”。问题是什么？我试图生成的代码是

我生成的汇编文件是：

另一方面，此汇编代码有效

在标签 .L0 中，当我检查 %eax 寄存器的值时，我得到了正确的值。但是当我检查 ecx 寄存器的值时，它给了我零。我不知道为什么。也许这就是我得到浮点分段错误的原因。有人可以帮我找出原因。

我试图生成的逻辑是

给出浮点错误的汇编文件是：