速度的最小公倍数算法（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

评论或预测哪一个更快是言之过早。

您的两个程序将采用如下所述的相同次数的迭代。

在情况1中，您正在增加每个步骤a。

在情况2中，则是由1，其是与由一个增加而增加倍数。

让我们看看情况1

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

你必须避免乘法操作if发言，并在return。

在案例2中，您使用的是increment operator，并在if和return中乘以。 它是在每个条件下相乘。

增量操作可以使用组件的增量操作进行优化，因此它可以比通过添加更快。

情况1中的额外时间由a添加。

在第二种情况下，如果2个额外的时间是增量的，并在每个繁殖，如果成功的条件，如果条件和回报。

如果乘法慢于加法，则情况2比情况1稍慢。您可能仅在大量的测试运行时才会注意到轻微的差异。

请注意，还有其他的因素也可以影响性能。

所以，来最终结论之前，两个密码，必须异形看到所花费的时间方面的差异。

Answer 2

粗略地说，创建快速代码避免了导致汇编代码变慢的所有问题。这包括：

• 临时对象（这里：循环变量）

• 常量（这里真）

• 状况检查（在这里：真）

• 乘法（这里：我* a）

• Modulo（here：test％b）

• 不要依赖于编译器优化

临时，模和一个对比是算法固有的，因此anavoidable。因此，它会导致这样的事情：

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（）中已经有了一个高效的实现。