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

Refill

1. Is clearly not true, since you claim to calculate sqrt(n) in both cases. – Aeon

This is an example of microbenchmarking; I see no warm up period, how are you accounting for JIT? – Aeon

2) Because Math.sqrt generally delegates to a hardware operation that's going to be faster than essentially any code you could possibly write. – Gaullist

Note that sqrt is a built-in function of most implementations of IEEE floating-point hardware. – Buoy

And sqrt, at best, has a complexity equivalent to divide, which is inherently 2-4 times the complexity of multiply. – Buoy

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

Coward

Answer 2

Squaring a number is effectively an integer operation while sqrt is floating point. Recognizing the run-time allocations for casting and computation the results you have observed are not surprising.

The Wikipedia page on sqrt http://en.wikipedia.org/wiki/Square_root has a nice section on computation.

As for the faster method I trust you can investigate (sub)linear run-time operation n^2.

On the note of run-times you might like this little piece of code I wrote up to demonstrate the number of system calls made to functions during iteration, you may find it, or something similar to it in java useful as you think about this sort of stuff. gist.github.com/Krewn/1ea0c788ac7210efc475

edit: Here is a nice explanation of integer sqrt. run-times http://www.codecodex.com/wiki/Calculate_an_integer_square_root

edit: on a 64 nm core2 to--- How slow (how many cycles) is calculating a square root?

Please include output in your post when possible Related to your question although approaching primes in a different way,

def getPrimes(n):
    primes = [2] 
                        # instantiates our list to a list of one element, 2
    k = 3
    while(len(primes) < n):
                        # python uses the prefix function len(var) for lists dictionaries and strings  
        k2 = 0
        isprime=True    
                        #Vacuously true assumption that every number is prime unless 
        while(primes[k2]**2<=k): #   <>   this is where you are substituting sqrt with sq  <>  #
            if(k%primes[k2]==0):
                isprime=False
                break
            k2+=1        
        if(isprime):primes.append(k)
        k+=2
    return(primes)

print (getPrimes(30))

Marchioness