C++ Stein 算法求 GCD

在本文中，您将了解 Stein 算法，它用于在 C++ 中查找 GCD，包括其算法和示例。

什么是 Stein 算法？

Stein 算法 是一种查找 两个非负整数 的 最大公约数 的算法，也称为 二进制 GCD 算法。Stein 算法使用减法、比较和算术移位而不是除法。它是确定两个数字的最大公约数 (GCD) 的有效方法。

尽管以色列程序员兼科学家 Josef Stein 于 1967 年 首次以其当前形式发布了该方法，但中国古人可能早在公元前二世纪就知道了它。

示例

输入

a = 24 b = 30

输出

6

输入

a = 36, b = 60

输出

12

算法

该算法通过重复应用这些恒等式来查找两个非负数 x 和 y 的 GCD

1. gcd(x,0) = x: 任何数都能整除零，y 是能整除的最大数
2. gcd(2x,2y) = 2 . gcd(x,y): 这里，2 是一个公约数。
3. gcd(x,2y)=gcd(x,y): 如果 x 是奇数，则 2 不是公约数。
4. gcd(x,y) = gcd(x, y-x): 如果 x、y 均为奇数且 x<=y。

• 由于 GCD 具有交换性 ((gcd(x,y) = gcd(y,x))，因此如果操作数交换，这些恒等式仍然适用：gcd(0,y) = y，如果 y 是奇数，则 gcd(2x,y) = gcd(x,y) 等。

Stein 算法查找两个数字 gcd(a, b) 的方法：-

• 如果 a 和 b 都为 0，则 GCD 为 0。gcd(0, 0) = 0。
• 由于任何数都能整除零，gcd(a, 0) = a 且 gcd(0, b) = b。
• 鉴于 2 是一个公约数，如果 a 和 b 都是偶数，则 gcd(a, b) = 2*gcd(a/2, b/2)。
• 位移运算符可用于执行乘以二的操作。
• 如果 a 是偶数且 b 是奇数，则有 gcd(a, b) = gcd(a/2, b)。类似地，如果 a 是奇数且 b 是偶数，则 gcd(a, b) = gcd(a, b/2)。这是因为 2 永远不能被二整除。
• 当 a 和 b 均为奇数时，gcd(a, b) 的公式为 gcd(|a-b|/2, b)。当两个奇数不同时，差为偶数。继续执行步骤 3-5，直到 a = b 或 a = 0。在这两种情况下，GCD 等于 power(2, k) * b，其中 k 是在步骤 3 中确定的 2 的公因数个数，power(2, k) 是 2 的 k 次幂。

示例 1

让我们举一个例子，在 C++ 中使用 Stein 算法 查找 GCD。

输出

复杂度分析

时间复杂度

• O(N * N)

辅助空间

• O(1)

示例 2

让我们再举一个例子，使用 Stein 算法 查找 GCD：

输出

复杂度分析

时间复杂度

• O(N * N)，其中 N 是较大数字的位数。

辅助空间

• O(N * N)，其中 N 是较大数字的位数。

Stein 算法优于欧几里得算法查找两个数字的 GCD 的优点

• Stein 算法是欧几里得算法的优化版本。
• 它更有效，因为它使用位移运算符。