java - 为什么乘法比开平方快很多倍？

Question

我有几个关于以下算法的问题来判断一个数是否为质数，我也知道 sieve of Eratosthenes可以更快的响应。

1. 为什么计算i i * sqrt (n) 的速度更快。比 sqrt (n) 一次？
2. 为什么 Math.sqrt() 比我的 sqrt() 方法快？

3. 这些算法的复杂度分别是O(n), O(sqrt(n)), O(n log(n))？

   public class Main {
   
   public static void main(String[] args) {
   
   // Case 1 comparing Algorithms
   long startTime = System.currentTimeMillis(); // Start Time
   for (int i = 2; i <= 100000; ++i) {
       if (isPrime1(i))
           continue;
   }
   long stopTime = System.currentTimeMillis(); // End Time
   System.out.printf("Duracion: %4d ms. while (i*i <= N) Algorithm\n",
           stopTime - startTime);
   
   // Case 2 comparing Algorithms
   startTime = System.currentTimeMillis();
   for (int i = 2; i <= 100000; ++i) {
       if (isPrime2(i))
           continue;
   }
   stopTime = System.currentTimeMillis();
   System.out.printf("Duracion: %4d ms. while (i <= sqrt(N)) Algorithm\n",
           stopTime - startTime);
   
   // Case 3 comparing Algorithms
   startTime = System.currentTimeMillis();
   for (int i = 2; i <= 100000; ++i) {
       if (isPrime3(i))
           continue;
   }
   stopTime = System.currentTimeMillis();
   System.out.printf(
             "Duracion: %4d ms. s = sqrt(N) while (i <= s) Algorithm\n",
             stopTime - startTime);
   
   // Case 4 comparing Algorithms
   startTime = System.currentTimeMillis();
   for (int i = 2; i <= 100000; ++i) {
       if (isPrime4(i))
           continue;
   }
   stopTime = System.currentTimeMillis();
   System.out.printf(
             "Duracion: %4d ms. s = Math.sqrt(N) while (i <= s) Algorithm\n",
             stopTime - startTime);
   }
   
   public static boolean isPrime1(int n) {
       for (long i = 2; i * i <= n; i++) {
           if (n % i == 0)
               return false;
       }
       return true;
   }
   
   public static boolean isPrime2(int n) {
       for (long i = 2; i <= sqrt(n); i++) {
           if (n % i == 0)
               return false;
       }
       return true;
   }
   
   public static boolean isPrime3(int n) {
       double s = sqrt(n);
       for (long i = 2; i <= s; i++) {
           if (n % i == 0)
               return false;
       }
       return true;
   }
   
   public static boolean isPrime4(int n) {
       // Proving wich if faster between my sqrt method or Java's sqrt
       double s = Math.sqrt(n);
       for (long i = 2; i <= s; i++) {
           if (n % i == 0)
               return false;
       }
       return true;
   }
   
   public static double abs(double n) {
       return n < 0 ? -n : n;
   }
   
   public static double sqrt(double n) {
       // Newton's method, from book Algorithms 4th edition by Robert Sedgwick
       // and Kevin Wayne
       if (n < 0)
           return Double.NaN;
   
       double err = 1e-15;
       double p = n;
   
       while (abs(p - n / p) > err * n)
           p = (p + n / p) / 2.0;
   
       return p;
   }
   }
   

这也是我的代码的链接:http://ideone.com/Fapj1P

Answer 1

1. Why is faster to compute i*i, sqrt (n) times. than sqrt (n) just one time ?看看下面的复杂性。计算平方根的额外成本。

2. Why Math.sqrt() is faster than my sqrt() method ?
Math.sqrt() 委托(delegate)调用 StrictMath.sqrt，这是在硬件或 native 代码中完成的。

3. What is the complexity of these algorithms?
您描述的每个功能的复杂性

i=2 .. i*i<n O(sqrt(n))

i=2 .. sqrt(n) O(sqrt(n)*log(n))

i=2 .. sqrt (by Newton's method) O(sqrt(n)) + O(log(n))

i=2 .. sqrt (by Math.sqrt) O(sqrt(n))

牛顿法的复杂度来自
http://en.citizendium.org/wiki/Newton%27s_method#Computational_complexity