Last active
August 29, 2015 13:56
-
-
Save pavanky/9053387 to your computer and use it in GitHub Desktop.
Comparing primality tests
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/python3 | |
def format(f): | |
return int(f * 100) / 100 | |
def isprime_6k(p): | |
# Basic Test | |
if (p % 2 == 0): | |
return 0,1 | |
if (p % 3 == 0): | |
return 0,2 | |
comps = 2 | |
# http://en.wikipedia.org/wiki/Primality_test | |
# The algorithm can be improved further by observing that all primes are of the form | |
# 6k +/- 1, with the exception of 2 and 3. | |
# This is because all integers can be expressed as (6k + i) for some integer k | |
# and for i = -1, 0, 1, 2, 3, or 4; | |
# 2 divides (6k + 0), (6k + 2), (6k + 4); | |
# and 3 divides (6k + 3). | |
# So for every prime p > 3, p is of one the following forms: | |
# m = 6n - 1 | |
# k = 6n + 1 | |
m = 5 | |
k = 7 | |
while (1): | |
if (m * m > p): | |
return 1, comps + 1 | |
if (p % m == 0): | |
return 0, comps + 2 | |
if (p % k == 0): | |
return 0, comps + 3 | |
comps += 3 | |
m += 6 | |
k += 6 | |
def isprime_sv(p): | |
# Basic Test | |
if (p % 2 == 0): | |
return 0,1 | |
if (p % 3 == 0): | |
return 0,2 | |
comps = 2 | |
# Implemented logic from here | |
# https://github.com/videlalvaro/erlang-prime-sv | |
n = int((p - 1) / 2) | |
k = 3 | |
res = int((k - 1) / 2) | |
while (1): | |
if (n < k): | |
return 1, comps + 1 | |
if (k * k > p): | |
return 1, comps + 2 | |
if ((n % k) == res): | |
return 0, comps + 3 | |
comps += 3 | |
k += 2 | |
res += 1 | |
if __name__ == "__main__": | |
comps_6k_false = 0 | |
comps_6k_true = 0 | |
primes_6k = 0 | |
comps_sv_false = 0 | |
comps_sv_true = 0 | |
primes_sv = 0 | |
for num in range(5, 100001): | |
check, comps = isprime_6k(num) | |
if (check): | |
comps_6k_true += comps | |
primes_6k += 1 | |
else: | |
comps_6k_false += comps | |
check, comps = isprime_sv(num) | |
if (check): | |
comps_sv_true += comps | |
primes_sv += 1 | |
else: | |
comps_sv_false += comps | |
if (primes_6k != primes_sv): | |
print("Something went wrong at", num) | |
if (num == 100 or | |
num == 1000 or | |
num == 10000): | |
print("isprime_6k @ ", num, | |
format(comps_6k_true / primes_6k), | |
format(comps_6k_false / (num - primes_6k))) | |
print("isprime_sv @ ", num, | |
format(comps_sv_true / primes_sv), | |
format(comps_sv_false / (num - primes_sv))) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
$ python isprime.py | |
isprime_6k @ 100 5.08 1.54 | |
isprime_sv @ 100 10.47 2.09 | |
isprime_6k @ 1000 11.94 2.23 | |
isprime_sv @ 1000 30.83 3.91 | |
isprime_6k @ 10000 33.78 3.3 | |
isprime_sv @ 10000 96.45 7.06 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment