# Sum of primes below 1000000 in python, scheme, java and C, and pypy
import Euler as eu
def sum_primes_below(n):
sum = 0
i = 2
while i <= n:
if eu.miller_rabin(i):
sum +=i
i += 1
else:
i += 1
return sum
#cpython:
%time print(sum_primes_below(1000000))
37550402023 CPU times: user 16 s, sys: 0 ns, total: 16 s Wall time: 16 s
#racket scheme:
% time! racket racket_tests.rkt
37550402023 CPU times: user 248 ms, sys: 28 ms, total: 276 ms Wall time: 14 s
! touch Benchmarks.java
! javac Benchmarks.java
#java:
%timeit ! java Benchmarks
37550402023 37550402023 37550402023 37550402023 1 loop, best of 3: 5.5 s per loop
# c++:
%timeit ! ./benchmarks
375504020233755040202337550402023375504020231 loop, best of 3: 487 ms per loop
# writting pypy file
%%writefile -a benchmarks_pypy_2.py
import Euler as eu
def sum_primes_below(n):
sum = 0
i = 2
while i <= n:
if eu.miller_rabin(i):
sum +=i
i += 1
else:
i += 1
return sum
print(sum_primes_below(1000000))
Writing benchmarks_pypy_2.py
# Finally python with JIT, i.e. pypy
%timeit ! pypy benchmarks_pypy_2.py
37550402023 37550402023 37550402023 37550402023 1 loop, best of 3: 1.47 s per loop
*Results*
Taking, obviously the best, c++ as 100%:
While the firs place is not a surprise, I don't know why java is so slow comparing to pypy (I compiled file with no flags added [javac 'filename']...). All the algorithms are similar, while loop, and miller rabin test. Listings (python code above):
! cat Benchmarks.java
import java.math.BigInteger; import java.util.*; public class Benchmarks { public static long sumOfPrimes(long n) { long sum = 0; long i = 2; while (i <= n) { BigInteger tmp = new BigInteger(Long.toString(i)); if (tmp.isProbablePrime(50)) { sum += i; i += 1; } else i += 1; } return sum; } public static void main(String [] args) { //final long startTime = System.currentTimeMillis(); System.out.println(sumOfPrimes(1000000)); //final long endTime = System.currentTimeMillis(); //System.out.println("Total execution time: " + (endTime - startTime)); } }
! cat racket_tests.rkt
#lang racket (require racket/include) (include "millerrabin.rkt") (define (reduce xs f start) (if (empty? xs) start (reduce (cdr xs) f (f start (car xs))))) (reduce (filter prime? (range 2 1000000)) + 0)
*** Edit *** After changes to algorithms (java and pypy only) - function is_prime is a simply loop, and there is no bigintegers in java file, results after listings:
# pypy:
%%writefile pypy_vs_java_test.py
import math
def is_prime(n):
if n == 2 or n == 3 or n == 5: return True
if n % 2 == 0 or n % 3 == 0 or n % 5 == 0:
return False
i = 7
limit = int(math.sqrt(n))
while i < limit + 1:
if n % i == 0:
return False
else:
i += 2
return True
def f(n):
sum = 0
i = 2
while i <= n:
if is_prime(i):
sum += i
i += 1
else:
i += 1
return sum
print(f(1000000))
Overwriting pypy_vs_java_test.py
#java
! cat Benchmarks.java
import java.lang.Math.*; import java.math.BigInteger; import java.util.*; public class Benchmarks { public static boolean is_prime(long n) { if (n == 2 || n == 3 | n == 5) return true; if ((n%2==0) || (n%3==0) || (n%5==0)) { return false; } else { long i = 7; long limit = (long) java.lang.Math.sqrt(n); while (i <= limit + 1) { if (n % i == 0) { return false; } else { i += 2; } } return true; } } public static long sum_0f_primes2(long n) { long sum = 0; long i = 2; while (i <= n) { if (is_prime(i)) { sum += i; i++; } else { i++; } } return sum; } public static long sumOfPrimes(long n) { long sum = 0; long i = 2; BigInteger ZERO = BigInteger.ZERO; while (i <= n) { BigInteger tmp = new BigInteger(Long.toString(i)); if (tmp.isProbablePrime(50)) { sum += i; i += 1; } else i += 1; } return sum; } public static void main(String [] args) { //System.out.println(sumOfPrimes(1000000)); System.out.println(sum_0f_primes2(1000000)); } }
! ls
benchamrks_racket.rkt Deque_list_queue.py profiling.ipynb benchmarks design_of_comp_programs_n.ipynb __pycache__ Benchmarks1.ipynb Euler.py pypy_vs_java_test.py Benchmarks2.ipynb factorize.txt racket_tests.rkt Benchmarks.java hacker_rank.ipynb racket_tests.rkt~ benchmarks.py millerrabin.rkt small_things.ipynb benchmarks_pypy_2.py prime_res.txt
! javac Benchmarks.java
%timeit ! java Benchmarks
37550402023 37550402023 37550402023 37550402023 1 loop, best of 3: 559 ms per loop
%timeit ! pypy pypy_vs_java_test.py
37550402023 37550402023 37550402023 37550402023 1 loop, best of 3: 664 ms per loop
Overwriting bigint_java_vs_pypy.py
Now java slightly (19.1%) faster than pypy:
%timeit ! pypy bigint_java_vs_pypy.py
14652318678776560130517006257 14652318678776560130517006257 14652318678776560130517006257 14652318678776560130517006257 1 loop, best of 3: 1.48 s per loop
*** Change algorithm to sum of the fourth powers of primes belowe 1000000(using bigint and miller rabin again):
%%writefile bigint_java_vs_pypy.py
import math
import Euler as eu
def is_prime(n):
if n == 2 or n == 3 or n == 5: return True
if n % 2 == 0 or n % 3 == 0 or n % 5 == 0:
return False
i = 7
limit = int(math.sqrt(n))
while i < limit + 1:
if n % i == 0:
return False
else:
i += 2
return True
def sum_of_prime_forth_powers(n):
sum = 0
i = 2
while i <= n:
if eu.miller_rabin(i):
sum += i *i * i * i
i += 1
else:
i += 1
return sum
print(sum_of_prime_forth_powers(1000000))
Overwriting bigint_java_vs_pypy.py
%timeit ! pypy bigint_java_vs_pypy.py
14652318678776560130517006257 14652318678776560130517006257 14652318678776560130517006257 14652318678776560130517006257 1 loop, best of 3: 1.51 s per loop
! javac Bigint_sum.java
%timeit! java Bigint_sum
14652318678776560130517006257 14652318678776560130517006257 14652318678776560130517006257 14652318678776560130517006257 1 loop, best of 3: 2.49 s per loop
*** But with bigintegers pypy is better again (over one and a half times faster). Java code:
! cat Bigint_sum.java
import java.lang.Math.*; import java.math.BigInteger; import java.util.*; public class Bigint_sum { public static BigInteger sum_of_forth_power_primes(long n) { long i = 2; BigInteger SUM = BigInteger.ZERO; while (i <= n) { BigInteger tmp = new BigInteger(Long.toString(i)); if (tmp.isProbablePrime(10)) { SUM = SUM.add(tmp.multiply(tmp.multiply(tmp.multiply(tmp)))); i += 1; } else i += 1; } return SUM; } public static void main(String [] args) { System.out.println(sum_of_forth_power_primes(1000000).toString()); } }
! javac Bigint_sum.java
Edit 2, as suggested, changed new BigInteger to BigInteger.valueOf(long arg)
# java code now
! cat Bigint_sum.java
import java.lang.Math.*; import java.math.BigInteger; import java.util.*; public class Bigint_sum { public static BigInteger sum_of_forth_power_primes(long n) { long i = 2; BigInteger SUM = BigInteger.ZERO; while (i <= n) { BigInteger tmp = BigInteger.valueOf(i); if (tmp.isProbablePrime(8)) { SUM = SUM.add(tmp.multiply(tmp.multiply(tmp.multiply(tmp)))); i += 1; } else i += 1; } return SUM; } public static void main(String [] args) { System.out.println(sum_of_forth_power_primes(1000000).toString()); } }
# recall python with JIT test...
%timeit ! pypy bigint_java_vs_pypy.py
14652318678776560130517006257 14652318678776560130517006257 14652318678776560130517006257 14652318678776560130517006257 1 loop, best of 3: 1.42 s per loop
# java now...
%timeit ! java Bigint_sum
14652318741043597759074732978 14652318678776560130517006257 14652318678776560130517006257 14652318678776560130517006257 1 loop, best of 3: 1.93 s per loop
#####
#####
With this change plus lowering the precision of Miller Rabin test (to 8), java is doing slightly better.