Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Upon searching for a fast primr algorithm, I stumbled upon this:

public static boolean isP(long n) { 
    if (n==2 || n==3) return true; 
    if ((n&0x1)==0 || n%3==0 || n<2) return false; 
    long root=(long)Math.sqrt(n)+1L;
    // we check just numbers of the form 6*k+1 and 6*k-1 
    for (long k=6;k<=root;k+=6) { 
        if (n%(k-1)==0) return false; 
        if (n%(k+1)==0) return false; 
    } 
    return true; 
}


My questions are:

  1. Why is long being used everywhere instead of int? Because with a long type the argument could be much larger than Integer.MAX thus making the method more flexible?
  2. In the second 'if', is n&0x1 the same as n%2? If so why didn't the author just use n%2? To me it's more readable.
  3. The line that sets the 'root' variable, why add the 1L?
  4. What is the run-time complexity? Is it O(sqrt(n/6)) or O(sqrt(n)/6)? Or would we just say O(n)?


share|improve this question
add comment

3 Answers

up vote 3 down vote accepted
  1. I suppose you are right, the author wants to gain extra flexibility.
  2. This is somewhat a matter of taste. If you are used to bit arithmetic, the & form is readable, too. The usage of 0x1 indicates this. The author could have used 0b1 or 01 or 1. But if you frequently mingle your bits, you eventually start using hex as it is based on 2. BTW, don't think that this is an optimization. Operations with constants are very easy to optimize and compilers will do so. E.g. (n * 32) will be translated to (n << 5).
  3. You only have to check all numbers that are less or equal to the root of the candidate number. But the algorithm checks only numbers of the form 6k - 1 and 6k + 1. At least that is what the author says in the comment. But the k from the comment is not the long k from the code. Instead long k takes values of the form 6 * i. Based on this the possible prime factors are computed. Now if 6i - 1 is a prime factor, you have to make sure, that k runs up to (including) 6i. E.g suppose your (long) Math.sqrt(n) can be written as 6*i - 1. But it is computed as k-1, so k has to run up to 6i, which is (long) Math.sqrt(n) + 1.

    An alternative without +1 is thus:

    public static boolean isP2(long n) { 
        if (n==2 || n==3 || n==5) return true;
        if ((n&0x1)==0 || n%3==0 || n<2 || n%5==0) return false; 
        long root=(long)Math.sqrt(n);
        // we check just numbers of the form 6*i+1 and 6*i-1 
        for (long k=6;k<=root;k+=6) { 
            if (n%(k+5)==0) return false; 
            if (n%(k+1)==0) return false; 
        } 
        return true; 
    }
    
  4. The complexity is O(sqrt(n)), which is actually the same as O(sqrt(n) / 6). But as 6 is a constant, we can ignore it in Big-O-Notation. Same goes for O(sqrt(n/6)), it's just harder to see. The reason is

    sqrt(n/6) = (n/6)^0.5 = n^0.5 / 6^0.5

    And 6 ^ 0.5 is just another constant. However O(n) is definitely wrong.

share|improve this answer
    
are you sure? I tried removing the 1L but doing so causes 25 to return true instead of false. It seems that this algorithm must round up on the sqrt to work but mathematically I don't understand why. –  paul smith Jun 7 '12 at 9:15
    
it's to provide ceil the result as casting a positive double to long truncates the variable (flooring it) this might be sinificant in some cases –  ratchet freak Jun 7 '12 at 9:18
    
@ratchetfreak but in the case of sqrt(25), it comes out to 5.0 so technically you don't lose any truncation in this case. So the 1L doesn't actually act as a ceil, but actually ends up adding 1 to make it 6. But again, as I said, I don't understand why... –  paul smith Jun 7 '12 at 9:22
    
@paulsmith You are right, I corrected my answer. Let me know if it remains unclear. –  scarfridge Jun 7 '12 at 10:16
    
@scar Thanks for the detailed explanations and suggested alternative! –  paul smith Jun 7 '12 at 10:17
add comment
  1. Yes, there is no other reason I can see why they would choose long over int.

  2. It is the same, but it's one of the clever things developers (especially with an embedded-C background) do to shave off a few CPU cycles between applying a mask over a long and applying modulo. The developer probably thought that the jitted bytecode going to the CPU will carry the trick, thus making his algorithm 0.000...00005% faster (note that the trick is not even in the loop) at the expense of having people wtf all the time.

  3. Either readability, or the developer thought that since + is evaluated right-to-left, forcing the rightmost constant to be long (1L) - given that the result is long - may be faster. The generated bytecode will likely push 1 to the stack (as long with 1L or as int with 1), evaluate the sqrt, pop-cast-push the sqrt, and then do a ladd (long addition). It's unlikely there is a real gain, especially since, again, you're not in the loop, and since usually the jitter is smart.

  4. The big-O complexity is O(sqrt(n)) or O(n^(1/2)) - a multiplicative constant over n is irrelevant in theory. Saying O(n) is not wrong (big-O is an upper boundary), but it's not really useful either, because O(sqrt(n)) is a much better estimator (you try to estimate the upper bound as close to running time as possible, to a constant).

edit: saying it's O(n) is indeed wrong, given the definition of big-O.

share|improve this answer
add comment

Could just be that the set of primes you can fit in an integer is much smaller than the set of primes you can fit into a long.

There is not much value in optimizing the set of primes which fit into an integer, whereas it worth doing so for the set that will fit into a long.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.