问题标签 [greatest-common-divisor]

I want to write a program where you enter two numbers and get the Greatest common divisor with the following pseudo code:

THis is my current version which gives me an error:52:invalid combination of opcode and operands.

I am totally new to assembly and nasm and i hope you can help me to find the error or false syntax.

我正在使用二进制方法来计算两个分数的 GCD，该方法工作得非常好，除非我将某些数字相减。

我假设这是因为，例如，当我从 1/6 中减去 2/15 时，GCD 有一个重复的数字或类似的东西，尽管我可能是错的。

那是我用来完成此操作的代码，调试消息将永远打印出来。

有没有办法在它卡住时作弊，或者设置一个例外？

在进行自己的 BigInteger 实现时，我遇到了扩展 GCD 算法，这是查找模乘逆的基础。由于众所周知的欧几里得方法执行速度太慢，混合和二进制算法仅快 5-10 倍，因此选择了 Lehmer 对经典算法的修改。但困难在于，在描述 Lehmer's 时，我发现的所有书籍（Knuth、Handbook of Applied Cryptography、Internets 等）都有相同的缺点：

1. 解释基于几个技巧：
   • 输入数字始终具有相同的长度；
   • 抽象 CPU 有带符号的寄存器，可以同时保存数字和符号；
   • 抽象 CPU 具有半无限的寄存器，即它永远不会溢出。
2. 只提供了基本的 GCD 算法，没有关注逆辅因子。

至于第一个问题，我最初对找不到任何真实世界的实现感到惊讶（不要将我指向 GNU MP 库——它不是学习的来源），但最终通过反编译微软的实现获得了灵感来自.Net 4.0，这显然是基于论文“<a href="http://www.csie.nuk.edu.tw/~cychen/gcd/A%20double-digit%20Lehmer-Euclid% 20algorithm%20for%20finding%20the%20GCD%20of%20long%20integers.pdf" rel="nofollow">一种用于查找长整数 GCD 的两位数 Lehmer-Euclid 算法，作者 Jebelean。生成的函数很大，看起来很吓人，但效果很好。

但是微软的库只提供基本功能，没有计算辅因子。好吧，准确地说，在速记步骤中计算了一些辅因子，在第一步中，这些辅因子只是初始的，但是在执行了速记步骤之后，它们就不再匹配了。我目前的解决方案是与“替代”辅因子并行更新“真实”辅因子（第一步除外），但这会使性能下降到零以下：该函数现在完成的速度仅比二进制快 25-50%基本模式中的方法。所以，问题在于，虽然输入数字仅在速记步骤中完全更新，但辅因子也在每个速记步骤的迭代中更新，从而几乎破坏了 Lehmer 方法的任何好处。

为了加快速度，我实现了一个“融合乘加”功能，因为“融合乘乘减”确实有助于更新输入数字，但这次影响可以忽略不计。另一项改进是基于这样一个事实，即通常只需要一个辅因子，因此可以根本不计算另一个辅因子。这应该将开销减半（甚至更多，因为第二个数字通常明显小于第一个），但实际上开销仅减少了预期的 25% 到 50% 。

因此，我的问题归结为：

1. 是否有任何关于 Lehmer 算法的全面解释，与实际硬件上的实际实现相关（使用大小有限的无符号字）？
2. 与上面相同，但关于扩展的GCD 计算。

因此，尽管我对基本算法的性能感到满意，但扩展操作模式正好相反，这在我的案例中是主要的。

我试图在 x86 程序集中迭代地找到 GCD。不知何故，循环在第一次迭代后继续终止，因为余数 = 0。任何想法为什么？

我正在 MIT 6.00 学习 Python 并堆叠制作递归代码。我唯一想做的就是从x中迭代减去1，但不知道该怎么做..

这是我的代码

请帮忙 ！！！

我今天才开始学习Scheme。

我写了一个函数gcd()，但它总是返回0。

为什么我错了？

我想使用 JavaScript 找到最大公约数。

有没有人做过并愿意分享？

它在 amazon.interviewstreet.com 中给了我一些输入的错误答案（我不知道是哪个，因为他们没有透露他们用于测试用例的输入）

还有为什么这个实现一直给我stackoverflow（再次不知道哪些输入）

请让我知道我错过了什么。我是编程新手，仍然是初学者。

如何用 Java 编写这段代码？

while (b) {由于Type mismatch错误，我似乎无法在 Java 中执行此操作。看来我也不能a, b = b, a%b完全用Java做这条线。

我只能找到关于如何递归和迭代地实现 gcd 函数的帖子，但是我找不到这个。我确定它在 Stackoverflow 上，但是我找不到它，所以如果它是重复的帖子，我深表歉意。

我查看了维基百科（此处）的分析，无法理解它们的重复关系。

考虑以下在 C 中递归实现的 GCD 函数的实现。它的前提条件是两个数字都必须是正数，但与运行时间无关。

对运行时间进行分析，我发现每个操作都是 O(1)，因此我们知道到目前为止的递归关系是：T(n) = O(1) + ???。现在要分析递归调用，我不确定如何将 a (mod b) 解释为我的递归调用以正确说明我的递归关系。