For an embarrassing number of months now, I’ve been promising an article about a Python 3 solution to Project Euler Problem 2.  I’ve actually got it written and typed up into a file, but it is way too long.   So I’ve convinced myself I need to re-edit it into a short coherent series of articles, but somehow I’ve never gotten around to finishing that editing drudgery.   I will get to it Real Soon Now.   Honest.

Meanwhile, I don’t want this blog to look like I’ve abandoned it, so today I’m republishing here the most popular article yet from https://rdrewd.blogspot.com.   This article was originally published on 09/27/2014, and has, according to blogspot.com’s stats, had 2959 pageviews there, and received 46 +1 votes from readers (Yay!) and drawn 140 comments, far more than has been typical for my posts.

I’m not at all sure how to bring the blogspot.com comments over here to the wordpress incarnation of my blog, but the comment threads were quite interesting.   See http://rdrewd.blogspot.com/2014/09/actual-code-c-vs-python-for-small.html if you’d like to rummage in the comments.  Many other programming languages were dragged into solving the same problem, and the runtime performance was compared, and the problem was ratcheted up for find millions of prime numbers instead of just 20.  All in all, it was a great deal of fun for me to follow the comments.  Heck the comment thread even found a runtime performance surprise in the implementation of Go, and may have caused some improvement in x86 runtime performance of later Go implementations.

The picture at the top of this article is a Ulam spiral, borrowed from Wikipedia:  https://en.wikipedia.org/wiki/Ulam_spiral.  I wanted something pretty to lighten the page, something that had to do with prime numbers.  Full-disclosure:  the programs I’m about to describe have nothing to do with the Ulam spiral, except that the programs find prime numbers and the Ulam spiral shows surprising patterns in prime numbers when you lay them out on a number line that you’ve spiraled that way.

And so without further adieu, here’s a re-run of my most popular blog post so far…


If you aren’t much interested in writing software, this post is probably not for you. If you read the post without following the links to the example implementations, then I’m not sure what you are doing here, though you are certainly welcome to ask questions.

Recently on Quora.com someone asked to see C code to find the first 20 prime numbers. Seemed like an easy enough question,
but the first guy who answered it, gave a C++-based pseudocode and some tips on how to convert that to C. That answer didn’t make me happy. Heck, I figure if you’re going to write in some other language, why not Python as a sort of testable pseudocode, but the question really needs that answer to then be re-stated in C.

So I sat down and banged out a Python 2 program to find and print the first 20 prime numbers. That code is here: find20primes.py

I used a list to hold the list of primes. When the list grows to 20 items, I’m done. I start the list by telling it 2 is a prime number. I then only consider odd numbers as additional candidates. If the candidate is divisible by any of the prime numbers we’ve found so far, it is not a prime number. If the candidate isn’t divisible by any of the prime numbers we’ve found so far, then the candidate is a prime number so we append it to our list of primes and, in either case, add 2 to the candidate number to get the next candidate number to be tested. In C, we’ll need a little more book keeping for the list, but since the max size of the list is bounded (20 items), things should translate from Python to C pretty easily. One trick that isn’t entirely obvious is the use I made of Python’s for…else control structure to catch the case of the for loop not exiting via break. We can paper that over with a goto in C, or you can add some flags

I was thinking that C has labeled break statements to let me do sort of the same thing as that for…else. But much to my chagrin, that’s a feature of Java, not C. Oops. So, goto it is in my C translation of the program.

So I sat down with that Python listing open in one window and typed up find20primes.c.  That code is here: find20primes.c

I believe it is a straight-forward translation of the Python program into C. Of course, the C program is bigger in the sense of it has more lines of code. There are lines added to delimit the blocks and loops in the program, and lines added for variable declarations and lines added for the annoying book-keeping that C needs me to do where Python just handles those chores. I did run into some trouble where I didn’t get the book keeping entirely correct the first time through. The program outputted 20 primes, but it started with 2, followed by 73, followed by 3, and it left out 71 at the end of the list. Huh? Turned out I was mistakenly incrementing primecnt before I’d used it to fill in the next slot in the primes array, so I skipped the primes[1] slot and just got 73 there by bad luck. Python would have told me about an uninitialized variable if there’d been a spot in the Python program for me to have committed that same kind of error.

Having finally gotten both programs working, conventional wisdom is that the C code should be much faster than the Python code.
So I used the “time” command to see how the timings compare.

Using cygwin Python 2.7.8 on Windows 7 on a PC with an i5 processor and 8GB of RAM,

$ time python find20primes.py

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

real 0m0.136s
user 0m0.000s
sys 0m0.062s

Using cygwin cc 4.8.3 on that same Windows 7 PC:

$ time cc find20primes.c

real 0m0.238s
user 0m0.045s
sys 0m0.185s

$ time ./a.exe
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71

real 0m0.064s
user 0m0.015s
sys 0m0.015s

The execution time for the compiled C program was way less than the total time for the Python run, but if you add in the compile time for the C program, Python comes out ahead. Your mileage may vary.

By the way, if I throw in a -O option (“optimize the generated code”) on the cc command, it further slows the compile down, while the run time is about the same.

$ time cc -O find20primes.c

real 0m0.336s
user 0m0.031s
sys 0m0.185s

$ time ./a.exe
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71

real 0m0.086s
user 0m0.000s
sys 0m0.015s

(the “real” elapsed time varies a lot from run to run. These run times are so short the variability makes it hard to make fair comparisons in races between the programs). I suspect that the real time is dominated by the console I/O to print the results, so optimizing the details of the loops isn’t going to do much improving of things.

Now to make things more interesting, suppose I wanted to pass in as a command line argument the number of primes to be found. So long as the primes are still in the range of ints that only needs a malloc of the array in C but if the program is ever asked to get up into really big primes, the Python code will keep on chugging while the C code will need substantial rework to pull in an arbitrary precision integer library module. This blog article is already long enough, so I’ll leave that generalization to “findNprimes” up to you. How big does N have to be to break the C code’s use of ints? I suppose that with relatively minor surgery, you could convert over to use of long ints (or if your compiler supports them, to long long ints) in the C program.
Looking into it lightly, it appears that the cc included with Cygwin supports long long ints. The format strings will need adjusting. Use %lld instead of %d.

If you’ve feeling anxious to try further experiments, see how pypy does in handling the find20primes.py program. That’ll probably be more interesting with findNprimes.py with a really big value for N.

The moral to the story is that C may not be the best choice of programming language for this kind of problem.

Did you enjoy this article or was it too technical? Please add a comment down below so I know what you think about this sort of writing.

Advertisements

4 thoughts on “Actual Code – C vs. Python for a Small Problem

  1. In my opinion, one of the great strengths of Python, is that it is a language that makes it easy for me to think through a program and cleanly, concisely, express and refine my solution. In looking over the other language implementations, I can certainly see there are other contemporary programming languages that let you cleanly express an solution of a problem, and some of them even bring the advantage of the code running faster than the Python implementation. I’ve been surprised that no one has presented a “functional programming” solution here for comparison, even a performance comparison of a more functional programming slanted Python implementation of the initial Python solution might be interesting to see.

    There are of course umpteen-gillion other programming languages that aren’t represented here yet with an argument in favor of whatever is your favorite. Most glaringly missing, in my opinion, is a good clean example of how this little problem should be done in C++, or at least an explanation as to why C++ isn’t a great match to this little problem. As it stands, I am left suspicious that at least on small scale problems, perhaps C++ isn’t a good choice. But then, I keep hoping that someone with mastery of the latest revisions of C++ can show me such amazingly clean and easy to read code for the problem at hand that I’ll finally see the light.

    I’ve also been surprised that the goto in my C rendition of the code didn’t draw more attention than it seems to have gotten. My judgment call was that I didn’t want to clutter my C version of the code by introducing a flag or a redundant test to remove the need for the goto statement, but no one has countered by showing a revised version that gets rid of the goto and still is uncluttered and clean. Java’s support for breaking from labeled blocks of code, perhaps should entice a Java fan into showing how a Java implementation compares in readability (and performance?) to a C implementation. For n=20, performance isn’t very interesting, but we’ve had examples in the comments that have run n up to way higher numbers than 20. As commercially popular as Java is, we haven’t drawn out a Java proponent to show the strengths of that particular programming language?

    Writing, testing and making timing measurements is a lot more work than just hurling a remark and maybe clicking “like” somewhere, but if you feel strongly about a programming language, I believe there’s still plenty of room to explore things here in the comment section and show us the results.

    Like

    1. Interesting blog post, I appreciate your maturity with regards to some of the factors that go into actually getting code implemented. Different languages have their strong and weak points and should be considered on their merits for solving the specific problem at hand. One other option is to use more than one language at once to leverage the better parts of various languages. So I made a c++ implementation and then went a step further and made a tutorial for how you would make Python bindings for it:

      http://www.jaggedverge.com/2016/09/generating-python-bindings-from-c11-with-pybind11/

      That way you can use the C++ code directly in the Python project. Sometimes people artificially limit themselves to the use of one language, hopefully this helps people broaden their view.

      Liked by 2 people

      1. Thanks. I wasn’t familiar with pybind11, but will have to give it a try.

        Thanks for a clean looking C++ implementation of the findprimes routine. I’ll have to play with gcc and your implementation to do some timing comparisons.

        Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s