注意到这里的所有答案都没有提到欧几里得算法的迭代实现。
public static long gcdLongIterative(long a, long b) {
long tmp;
while (0 != b) {
tmp = b;
b = a % b;
a = tmp;
}
return a;
}
我像@Bohemian 一样实现了验证测试，递归和迭代实现的工作方式相同，但是迭代方法更快。基准测试显示了小的改进，但它是改进的，总体而言，不太多使用堆栈并完全依赖 Java VM 来优化其实现依赖感觉更好。即使基准测试相同，我仍然会觉得迭代更好，因为迭代更便携，而递归仅由我的主机 Java 优化，但在其他 VM 上可能没有得到很好的优化。
基准测试结果（代码在答案的底部）：
(100 000 000 iterations)
gcd recursive: 3113ms
gcd iterative: 3079ms
gcd BigInteger: 13672ms
迹象：
我注意到的一个区别（除了性能之外）是符号的处理方式不同，手工实现的欧几里得算法gcdLong和我的gcdLongIterative行为相同，但两者都不同于BigInteger倾向于“保持”原样的符号。似乎本质上gcdandgcdLongIterative 可以返回负数，而 BigInteger 只会返回正数。
gcdLong and gcdLongIterative implementations:
-4/-2 => 2/1
-10/200 => 1/-20
10/-200 => 1/-20
BigInteger implementation tends to 'keep' the signs:
-4/-2 => -2/-1
-10/200 => -1/20
10/-200 => 1/-20
用于分数的所有结果都是有效的，但如果您期望数字具有特定的“风格”，则值得考虑后处理标准化。
例如，如果首选 BigInteger 行为，则只返回绝对值就足够了，如下所示：
public static long gcdLongIterative(long a, long b) {
long tmp;
while (0 != b) {
tmp = b;
b = a % b;
a = tmp;
}
return Math.abs(a);
}
表现：
受@Xabster benchmark 的启发（来自Java：Get Greatest Common Divisor，哪种方法更好？）我将其扩展为测试所有 3 种实现，在某些情况下递归和迭代执行相同，但迭代在大多数情况下稍快案件。
基准代码：
import java.math.BigInteger;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
public class Test {
private static final int BENCHMARK_ITERATIONS = 100000000;
public static long gcdLong(long a, long b) {
return b == 0 ? a : gcdLong(b, a % b);
}
public static long gcdLongIterative(long a, long b) {
long tmp;
while (0 != b) {
tmp = b;
b = a % b;
a = tmp;
}
return a;
}
public static long gcdLongBigInteger(long a, long b) {
return BigInteger.valueOf(a).gcd(BigInteger.valueOf((b))).longValue();
}
public static String asFractionGcdLong(long a, long b) {
long gcd = gcdLong(a, b);
return (a / gcd) + "/" + (b / gcd);
}
public static String asFractionGcdLongIterative(long a, long b) {
long gcd = gcdLongIterative(a, b);
return (a / gcd) + "/" + (b / gcd);
}
public static String asFractionGcdLongBI(long a, long b) {
long gcd = gcdLongBigInteger(a, b);
return (a / gcd) + "/" + (b / gcd);
}
public static void test(String actual, String expected) {
boolean match = expected.equals(actual);
if (match) {
System.out.println("Actual and expected match=" + expected);
} else {
System.out.println("NO match expected=" + expected + " actual=" + actual);
}
}
public static class Values {
public long a;
public long b;
public String expected;
public Values(long a, long b, String expected) {
this.a = a;
this.b = b;
this.expected = expected;
}
}
public static void validityTest() {
List<Values> vals = new LinkedList<Values>(Arrays.asList(
new Values(500, 1000, "1/2"),
new Values(17, 3, "17/3"),
new Values(462, 1071, "22/51"),
new Values(-4, -2, "2/1"),
new Values(-10, 200, "1/-20"),
new Values(10, -200, "1/-20")
));
System.out.println("------ Recursive implementation -------");
vals.forEach(v -> test(asFractionGcdLong(v.a, v.b), v.expected));
System.out.println();
System.out.println("------ Iterative implementation -------");
vals.forEach(v -> test(asFractionGcdLongIterative(v.a, v.b), v.expected));
System.out.println();
System.out.println("------ BigInteger implementation -------");
vals.forEach(v -> test(asFractionGcdLongBI(v.a, v.b), v.expected));
System.out.println();
}
public static void benchMark() {
Random r = new Random();
long[] nums = new long[BENCHMARK_ITERATIONS];
for (int i = 0 ; i < nums.length ; i++) nums[i] = r.nextLong();
System.out.println("Waming up for benchmark...");
for (int i = 0 ; i < nums.length-1; i++) gcdLong(i, i + 1);
for (int i = 0 ; i < nums.length-1; i++) gcdLongIterative(i, i + 1);
for (int i = 0 ; i < nums.length-1; i++) gcdLongBigInteger(i, i + 1);
System.out.println("Started benchmark...");
long s = System.currentTimeMillis();
for (int i = 0 ; i < nums.length-1; i++) gcdLong(i, i + 1);
System.out.println("recursive: " + (System.currentTimeMillis() - s) + "ms");
s = System.currentTimeMillis();
for (int i = 0 ; i < nums.length-1; i++) gcdLongIterative(i, i + 1);
System.out.println("iterative: " + (System.currentTimeMillis() - s) + "ms");
s = System.currentTimeMillis();
for (int i = 0 ; i < nums.length-1; i++) gcdLongBigInteger(i, i + 1);
System.out.println("BigInteger: " + (System.currentTimeMillis() - s) + "ms");
}
public static void main(String[] args) {
validityTest();
benchMark();
}
}