java - 最小公倍数算法的速度(java)

Question

我正在尝试解决欧拉问题:目前我的速度定义步骤是计算两个数的最小公倍数。那么，这些方法中哪一种更快？为什么？

    public static int lcm(int a, int b){
        for(int test = a; true; test += a){
            if(test % b == 0)
                return test;
        }
    }

或

    public static int lcm(int a, int b){
        for(int i = 1; true; i++){
            if(i*a % b == 0)
                return i*a;
        }
    }

我认为这里的基本问题是哪个过程更快，乘法还是加法。

谢谢。

(在要求我展示我的其余代码/说我不应该专注于程序的这一部分之前:我的问题不是如何获得问题的答案而是如何使这部分更快。)

Answer 1

粗略地说，要创建快速代码，请避免一切会导致汇编代码变慢的事情。这包括:

• 临时变量(此处:循环变量)

• 常量(此处:true)

• 条件检查(此处:true)

• 乘法(此处:i * a)

• 模(此处:test % b)

• 不要依赖编译器优化

临时、取模和一比较是算法固有的，因此是可以避免的。所以它会导致这样的结果:

public int euler(int a, int b) {
    int test = a;
    while (test % b != 0) {
        test += a;
    }
    return test;
}

如果您稍微(在数值上)将算法修改为等价方程，则可以完全消除乘法:

public int own(int a, int b) {
    int x = a;
    for (int y = 0;; x += a) {
        while (y < x) {
            y += b;
        }
        if (x == y)
            break;
    }
    return x;
}

顺便说一句:如果您要查找大数的 LCM，也许您最好使用 Euclid 的 GCD 算法。因此 LCM(a, b) = a * b/GCD(a, b)。 Java 类 BigInteger.gcd() 中已有一个有效的实现。