问题标签 [greatest-common-divisor]

我想在我的应用程序中简化一部分。分数就像 x/y，其中 x 和 y 是整数。我想将分数简化为最简单的形式。谁能给我提示如何做到这一点。提前致谢。

http://en.wikipedia.org/wiki/Binary_GCD_algorithm

根据 Wikipedia 的说法，它应该比 Euclid 的算法快一点（不多，但我至少期望获得相同的性能）。对我来说，它慢了一个数量级。大家能帮我弄清楚为什么吗？

我尝试在 Ruby 中实现它。首先，我采用了递归解决方案

效果不太好，所以我想检查一下如果它是一个循环它会有多快

这些是基准测试结果

std 是原生 ruby​​ 1.9.3 C 实现。

rbn 基本上是相同的东西（欧几里得算法），但用 Ruby 编写。

bin 是您在上面看到的循环代码。

rec 是递归版本。

编辑：我在 matz 的 ruby​​ 1.9.3 上运行了基准测试。我尝试在 Rubinius 上运行相同的测试，这就是我得到的。这也令人费解……

我是 ios 编程新手。我对 GCD 计划有疑问。

我不明白这部分：

这是什么意思，用英语？

感谢大家的帮助，我做了一些非常好的改变，但现在它给了我一个 +4198498 的答案，而不是 5，我知道第一组值是错误的。我推错了什么或没有正确弹出注册表？我使用 ret 8 清理了堆栈，它应该为下一次调用清理堆栈，对吗？

这是我到目前为止所拥有的：

这可能是一个非常简单的问题。假设我有一个计算 gcd 的类，称为 Gcdcomp。该类中的代码全部有效。当我在我的主要代码块中提到它时，我说..

a 和 hii 是我的两个变量。默认情况下，Getgcd 类使用 int a 和 int b 并在执行 euclids 算法后返回 a。如何在我的主代码中使用该返回值作为变量？

我目前使用此代码查找 gcd 和 lcm

但是，如果我想为数字列表执行此操作，例如 [4,5,7,1,5,7,10,1,16,24] 等，该怎么办？我是否受限于循环？

我正在尝试使用 y-combinator 在 scala 中定义 gcd：

但我收到一个错误：

如果我将所有论点都归结起来，那么就没有问题：

我在非咖喱版本中做错了什么？

基本上，标题说明了一切。这些数字并不太大（N 的最大值为 ~2/3 * max(long)，max M 为 max(long)），所以我认为即使是我目前拥有的简单解决方案也足够了。M 总是大于 N。

我目前拥有的：

• 最简单，从 N + 1 开始，执行简单的欧几里得 GCD，如果它返回 1，我们就完成了，如果不增加，再试一次。

我想知道这个解决方案最坏的情况是什么。性能不是一个大问题，但我仍然觉得必须有更好的方法。

谢谢。

关于最坏的情况，我做了一个小测试：

它运行了约 30 分钟，到目前为止最坏的情况是 29 次迭代。所以我相信有一个比 O(N) 更精确的答案。

这是一个简单的任务，但我似乎无法弄清楚如何去做

这是一个示例函数结构

测试数据

注意：最大小数位数为 1。编程语言并不重要。我只需要算法

请帮忙..谢谢！

好吧，我知道这确实是一个愚蠢的问题，但我无法理解。有一项任务我应该找到 欧几里得（gcd）的递归算法。我已经完成了一个案例，在这里：

我需要做另一种情况，其中递归从 х0 开始，当 Xi 调用函数计数 Xi+1 时。应该是这样的：

但它不起作用。请帮帮我。