OpenEuphoria

[rant][benchmark] Sieve of Eratosthenes

• Posted by _tom (admin) Jan 08, 2019
• 1304 views

The Sieve of Eratosthenes is "a classic algorithm for finding prime numbers."

I found a Python algorithm that uses "list comprehension" which results in a compact program. [ Python without Fear Brian Overland, 2018 Pearson Education ]

The program outputs the largest primes in the first 20_000 numbers.

# Python code 
 
n = 20000 
comp_list = [j for i in range(2,n) 
               for j in range(i*i, n, i )] 
prime_list = [i for i in range(2,n) 
                      if i not in comp_list] 
print( prime_list[-10:] ) 

The Euphoria version looks like this:

-- Euphoria Code 
 
integer n = 20000 
 
sequence b_lst = repeat( 1, n ) 
sequence prime_lst = {} 
 
for prime = 2 to n do 
	if b_lst[prime] then 
		prime_lst = append(prime_lst, prime ) 
		for i = prime * 2  to n by prime do 
			b_lst[i] = 0 
		end for 
	end if 
end for 
 
? prime_lst[$-9..$] 

My benchmark testing program is:

atom t 
 
puts(1, "phix\n" ) 
t = time() 
? system_exec( "p sieve.ex" ) 
printf(1, "%g time\n\n", time() - t ) 
 
 
puts(1, "oE\n" ) 
t = time() 
? system_exec( "eui sieve.ex" ) 
printf(1, "%g time\n\n", time() - t ) 
 
 
puts(1, "python\n" )  
t = time() 
? system_exec( "python sieve.py" ) 
printf(1, "%g time\n\n", time() - t ) 
 
 
puts(1, "phix compiled\n" )  
t = time() 
? system_exec( "./Sieve" ) 
printf(1, "%g time\n\n", time() - t ) 
 
 
puts(1, "oE compiled\n" )  
t = time() 
? system_exec( "./sieve" ) 
printf(1, "%g time\n\n", time() - t ) 

The results (netbook) are:

phix 
{19927,19937,19949,19961,19963,19973,19979,19991,19993,19997} 
0 
0.126013 time 
 
oE 
{19927,19937,19949,19961,19963,19973,19979,19991,19993,19997} 
0 
0.0479414 time 
 
python 
[19927, 19937, 19949, 19961, 19963, 19973, 19979, 19991, 19993, 19997] 
0 
33.448 time 
 
phix compiled 
{19927,19937,19949,19961,19963,19973,19979,19991,19993,19997} 
0 
0.00570715 time 
 
oE compiled 
{19927,19937,19949,19961,19963,19973,19979,19991,19993,19997} 
0 
0.0102074 time 

In conclusion:

• I found a benchmark that is extremely unfair to Python
• I still do not understand the advantage of "list comprehension"
• as long as I use oE|Phix my netbook is fast enough

_tom