While working on my current microcontroller project I’ve become a little obsessed with the prospect of rapidly generating lists of prime numbers. I’ve been testing various strategies for speeding up the process using logic modifications to a base concept. I’ve been doing my conceptual work in Python because it’s so fast and easy to rapidly develop applications with. Now that I have a good understanding of my strategy (code scheme) of choice, I’m starting to wonder how much better the same code would run in C. It’s no secret that Python’s strength is its versatility and ease of development of scritps, not its speed. C on the other hand can be very cumbersome and awkward to develop with, but its compiled code is very efficient so it’s better suited for mathematical applications which require billions of repetitive tasks.

To visualize the speed difference between C and Python, I wrote the same prime-number-testing code in both languages and timed their output. Basically I wrote identical code in each language (variable names and functions are the same, almost a line-by-line translation) and timed how long it took to find all prime numbers up to 10,000,000. (It reported the length of runtime at every 100,000 integers, totalling 100 time points).

The results:

The black line is code written in C and the blue line is Python. According to this output, Pythin is about 4 times slower than C at identifying primes utilizing the identical method. I’m not a coding expert, and there may be better ways to code/compile things in each language, so I’ll asy this is an indication of speed rather than a detailed, scientific study comparing the two languages. For fairness, I’ll provide my code.

Python code to generate prime numbers up to 10^7:

import time
def isPrime(testPrime):
	for div in xrange(2,int(testPrime**.5)+1):
		if testPrime%div==0: return False
	return True

def testSpeed(startAt, stopAt):
	primesFound=0
	startTime = time.clock()
	for testPrime in xrange(startAt,stopAt):
		if isPrime(testPrime):
			primesFound+=1
	s="%d,%d,%d,%fn"%(primesFound,startAt,stopAt,time.clock()-startTime)
	print s
	f=open("log_py.txt",'a')
	f.write(s)
	f.close()
	return 

for i in range(100):
	testSpeed(100000*i,100000*(i+1))
raw_input()

C code to generate prime numbers up to 10^7:

#include <stdio.h>
#include <math.h>
#include <time.h>

char isPrime(int testPrime){
     int div;
     for (div=2;div<(int)sqrt(testPrime)+1;div++){
         if (testPrime%div==0) return 0;
         }
     return 1;
     }

void testSpeed(unsigned int startAt, unsigned int stopAt){
    int primesFound=0;
	char buf[256],len;
	unsigned int testPrime;
    clock_t startTime = clock();
    for(testPrime=startAt;testPrime<stopAt;testPrime++){
        if (isPrime(testPrime)) primesFound++;
        }
	len=sprintf(buf,"n%i,%u,%u,%f",primesFound,startAt,stopAt,
		(float)(clock()-startTime)/CLOCKS_PER_SEC);
	printf("%s",buf);
	FILE *fptr = fopen("log_c.txt","a");
	fputs(buf,fptr);
	fclose(fptr);
    return;
}

int main(){
	char i;
	for (i=0;i<100;i++){
		testSpeed(100000*i,100000*(i+1));
	}
    return 0;
}

Python code to graph the difference utilizing MatPlotLib:

import pylab

def graphIt(fname,col):
	f=open(fname,'r')
	data=f.readlines()
	f.close()
	val,time=[],[]
	for line in data:
		if line.count(',')<3: continue
		line=line.strip('n').split(',')
		val.append(int(line[1]))
		time.append(float(line[3]))
	pylab.plot(val,time,color=col)
	return [val,time]

pylab.figure()
pylab.subplot(311)
v,tc=graphIt('log_c.txt','k');
v,tp=graphIt('log_py.txt','b');
pylab.title("C vs Python: test 10,000 numbers for primeness")
pylab.ylabel("time (seconds)")
pylab.xlabel("starting value")
pylab.grid(alpha=.3)
pylab.subplot(312)
pylab.grid(alpha=.3)
graphIt('log_c.txt','k');
graphIt('log_py.txt','b');
pylab.ylabel("time (seconds)")
pylab.xlabel("starting value")
pylab.semilogy()
pylab.subplot(313)
ratios=[]
for x in range(len(v)):
	ratios.append(float(tp[x])/tc[x])
pylab.plot(v,ratios,'k')
pylab.ylabel("speed ratio")
pylab.xlabel("starting value")
pylab.axis([None,None,None,5])
pylab.grid(alpha=.3)
pylab.show()