Skip to main content

Basic Sieve

I've implemented a basic sieve to see if it does any better than trial division.
While trial division found the first million primes in 8.28 seconds the sieve does the same task in 0.84 seconds.  That's a little better!


Running the sieve on the range [2..1,000,000,002) yields 50,847,534 primes in 78.14 seconds.  I'm currently storing a byte for each number so that means I'm using 1GB ram.  We can't just keep increasing the range because we will eventually run out of memory.  Even storing a single bit for each number (we only need to know if it has been crossed our or not) would only divide this by a factor of 8.

Perhaps we can work on a section of the number line at a time?
Labels:

Comments

Post a Comment

Popular posts from this blog

Duck typing considered harmful.

I've had a chance to work on a fairly large chunk of Python at this point and have decided that Python (like Perl) is completely untenable at scale.  <rant><rave><drool>  but wait!  I have reasons! Programmers spend most of their time reading code.  We read massive amounts of code.  After we read massive amounts of code we write one... or change one... To make a change to a piece of code you first have to understand what it does and how it interacts with the system around it.  Then we start reading massive amounts of code again.  Anything you can do to minimize the amount of code a programmer has to understand to make a change becomes a huge gain in productivity. Duck typing causes the amount of code you need to read to make a change to grow very large. For example lets look at two functions, one in C++ and one in Python. First in C++ int function(type1 arg1, type2 arg2) {   return arg1->method(arg2); } In this fun...
1 comment
Read more

How big are primes?

So, If we were to calculate the first billion primes how much ram would we need? At the end the primes won't fit in a 32bit integer.  If we store them all in 64bit integers we'd need 8GB. Even if they all fit in 32bit integers we'd still need 4GB of storage just to store the list. Seeing at my little machine has 4GB ram that isn't going to work either. How about just storing the intervals between primes? For the first primes (2, 3, 5, 7, 11, 13, 17) we would store (2, 1, 2, 2, 4, 2, 4) Using a byte for every interval less than 128 and a short for the rest lets us store the first billion primes in just about 1GB.  Now that we can do! Maybe we can do even better though...
Post a Comment
Read more
C Craft  is a great article about C including discussion on the good, the bad, and why you can't eat just one. Quote from the preface: Let me open with a disclaimer. What follows is an unabashedly opinionated diatribe certain to offend many programmers. Craftsmen inevitably grow defensive of their favourite tools and practices. Rather than respect this natural sensitivity, I will exploit it, shamelessly intensifying the vitriol for attention. I care little whether one applauds or deplores my views; I mainly want my audience to feel compelled to read on. However, I try to be informative as well as incendiary. Whether one finds my statements profound or unsound, whether one abhors or adores my examples, and whether one is amused or bemused by my observations, I hope one leaves wiser.
Post a Comment
Read more