问题标签 [euclidean-algorithm]

我试图找到一种uint64_t在不支持 128 位整数的系统上使用 C 实现 EEA 的方法。问题在于，似乎总是存在某个变量或另一个变量会溢出的情况，从而产生不正确的结果。

我知道它可以用 /signed/ 机器字来完成，这里和其他地方有很多答案可以为此提供伪代码。可以用无符号且没有溢出来完成吗？还是您需要更大的整数大小？

我想知道是否可以在恒定时间内计算上述目标。我需要它来解决 codechef 上的问题。

这个算法的时间复杂度是多少？有人可以提供详细的解释吗？

不应使用 BigInteger 类的 modInverse 方法。我尝试并使用了这种方法，但它没有产生正确的结果。任何帮助，将不胜感激。

假设我有一个名为my_func(a,b,s,t). 假设，我想a和b被值传递，但我想s和t被引用传递。如在，我想一些如何通过让我们说(4,5,s',t')。该函数通过调用 来执行计算my_func(a/2,b/2,s/2,t/2)。问题是，在递归的“底部”有一个基本案例，它为sand提供了具体的值t。

让我举一个小例子：

因此，我将此函数称为 ，e_euclid(a,b, something, something)但随后我必须为s和提供具体值t。你们能看到我在这里想做什么吗？

在我返回 (s,t) 的地方进行递归会导致我不希望执行的艰难计算，所以我想这样做。

我最初是通过以下方式实现欧几里得算法的。

该算法是尾递归的，我希望它可以用recursion-schemes直观地编写。然后，下面的euc是递归部分的摘录。这个euclid函数使用euc，而psi专门用于一步处理。

euc函数看起来像apo态射，但我不知道如何将apo专门化为euc。在我看来，它们是完全不同的东西。是否可以将euc写成递归方案中的某种态射？

问候。

我正在尝试使用 BigInteger 制作扩展的欧几里得算法。但我不断收到错误消息

线程“主”java.lang.ArithmeticException 中的异常：BigInteger 除以零

我在谷歌上搜索，它说我可能会因为非整数除法而出错

我应该如何解决这个问题？

所以关于扩展欧几里得算法，找到 , , 和 在方程 中的算法a，b其中d和am+bn=d是m两个n正整数，d是它们的 GCD，并且a和b是两个整数（不一定是正数）

所以我正在关注的书有以下实现这个算法的说明：

我的问题是我不是特别了解这个算法的所有数学，我对普通的欧几里得算法了解得足够好，所以我也了解了一半的扩展算法。我不明白a'andb'的需要t（我知道这t是一个临时变量，但我不明白a = t - qaandb = t - qb部分）。以及变量a、a'、b和的初始化，b'以及每次迭代时它们之间的值交换。任何人都可以帮助我弥合我对这个算法的理解中的这些差距吗？

经过一些实验和搜索，我想出了以下定义：

我会评估emcd' 56 15到最内层，例如：

• 我的评估是否朝着正确的方向发展？

编辑：

根据 Will Ness 的评论，我正在更新评估。

经过一些实验和搜索，我想出了以下定义：

• 这个表达背后的含义是什么t - (q * s)？

我试图手动评估它；即使我得到了正确的结果(1, -4, 15)，我也看不出为什么该表达式返回t.

有一种著名的计算方法s和tin as + bt = gcd(a, b)。在寻找 gcd 的过程中，我得到了几个方程。

通过反转欧几里得算法中的步骤，可以找到这些整数a和b。那些得到的方程看起来像表达式t - (q * s)；但是，我无法弄清楚确切的过程。