Why is multiplied many times faster than taking the square root?

Question

I have several questions with the following algorithms to tell if a number is prime, I also know that with the sieve of Eratosthenes can be faster response.

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 ?

3. What is the complexity of these algorithms 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;
   }
   }
   

This is the link of my code also: http://ideone.com/Fapj1P

Answer 1

1. Why is faster to compute i*i, sqrt (n) times. than sqrt (n) just one time ? Look at the complexities below. The additional cost of computing square root.

2. Why Math.sqrt() is faster than my sqrt() method ?
Math.sqrt() delegates call to StrictMath.sqrt which is done in hardware or native code.

3. What is the complexity of these algorithms?
The complexity of each function you described

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))

Newton's method's complexity from
http://en.citizendium.org/wiki/Newton%27s_method#Computational_complexity