I’m currently reading Algorithms Unplugged, lent to me by my friend and professor, Dr. Marr.
The text provided 4 versions of an algorithm and claimed that each new version had a noticeable increase in runtime efficiency.
These algorithms take some number n and return a list of all prime numbers up to and including n. For example, if n = 13, this algorithm returns [2,3,5,7,11,13].
I was skeptical of their claims $\Rightarrow$ I took the psuedocode and converted it into functional Python, then wrote a timing function: this tests each algorithm by letting n = 2^6 to 2^20 and repeating each calculation 1000 times (in order to find the average runtime).
I had to wrestle with Python in order to stop it from rounding off the calculated runtimes (treating runtime as a float), which lead to an interesting adventure into the time module man page.
tl;dr
- take psuedocode from a book (p.121-127 of Algorithms Unplugged by various German computer scientists*)
- translate said psuedocode into functional code, and
- test the run-times of each algorithm
''' Catherine Ray prime_runtime0.py 'Algorithms Unplugged' Demonstration Program uses algorithms listed in psuedocode from pg.119-127. Each algorithm returns a list of all primes up to some number n. There are 4 versions of this algorithm; this program computes the average runtimes of each version and prints to stdout. ''' import math import time as t class Runtime(): def execute(self): repeat = 1000 #number of times to repeat runtime calculation n = [2**x for x in xrange(6, 21, 7)] #produce list of large numbers to test algorithms #n = [2**6, 2**20] for v in xrange(1,5): method = 'self.prime_number'+str(v) #test each version of the algorithm, version = 1, 2, 3, 4 print 'ntVersion ' + str(v), 'nHighest Prime Number Computed : Average Runtimen' #find runtime [self.runtime(method, number, repeat) for number in n] def runtime(self, method, n, repeat): #function = function to test #n = highest prime to compute #repeat = number of trials to run method = eval(method) total = 0 #reset total for r in xrange(0, repeat+1): start = t.time() #get start time methodrun=method(n) end = t.time() #get end time total = total + end-start #add to previously calculated time average_time = total/repeat #find average runtime print '2^%d :' %(int(math.log(n)/math.log(2))), average_time def prime_number1(self, n): #version 1, pg. 121 list = [i for i in xrange(2,n+1)] #write down all numbers between 2 and n in a list for i in xrange(2, n+1): for k in xrange(2, n+1): if i*k in list: list.remove(i*k) #if i*k is in list, remove else: pass #if i*k isn't in list, do nothing return list def prime_number2(self, n): #version 2, pg. 123 list = [i for i in xrange(2,n+1)] #write down all numbers between 2 and n in a list for i in xrange(2, int(math.floor(math.sqrt(n)))+1): for k in xrange(2, int(math.floor(n/i))+1): if i*k in list: list.remove(i*k) #if i*k is in list, remove else: pass #if i*k isn't in list, do nothing return list def prime_number3(self, n): #version 3, pg. 125 list = [i for i in xrange(2,n+1)] #write down all numbers between 2 and n in a list for i in xrange(2, int(math.floor(math.sqrt(n)))+1): if i in list: for k in xrange(2, int(math.floor(n/i))+1): if i*k in list: list.remove(i*k) #if i*k is in list, remove else: pass #if i*k isn't in list, do nothing return list def prime_number4(self, n): #final version, pg.127 list = [i for i in xrange(2,n+1)] #write down all numbers between 2 and n in a list for i in xrange(2, int(math.floor(math.sqrt(n)))+1): if i in list: for k in xrange(int(math.floor(n/i)), i-1, -1): if k in list: if i*k in list: list.remove(i*k) #if i*k is in list, remove else: pass #if i*k isn't in list, do nothing return list if __name__ == '__main__': runtime = Runtime() runtime.execute()
I left the code to run overnight.
Taking a brief glance at the output, I found confirmation of the authors’ claims. The runtime each version is less than the previous version (version4 should take less time to run than version1).
*Berthold Vöcking, Helmut Alt, Martin Dietzfelbinger, Rüdiger Reischuk, Christian Scheideler, Heribert Vollmer, Dorothea Wagner