> Even a Boolean vector taking just 1 bit per element would have to be more than 3e10 bytes long, so it was clear that the problem had to be partitioned.
That's 28GB. That's just astronomical in those days' terms, even stored on hard drives it would have taken a massive array of commodity HDDs. I love these little reminders of how far we've come.
There is a very beautiful way to do it using much less memory.
You need O(sqrt(n)/log(n)) memory, not O(n), if you keep track of the list of primes found so far, and a fixed-size interval over which you sieve: [1, k], [k+1, 2k], [2k+1, 3k], ...
Now, for the beautiful part, if you skip multiples of 2, 3 and 5, and work in blocks of 2 * 3 * 5 = 30 numbers, you only need to sieve {1, 7, 11, 13, 17, 19, 23, 29} + i*30. 8 booleans, that happen to fit in 1 byte. So 1 byte = 1 interval of 30 numbers.
Next, you can unroll the sieving loop, but no compiler will do this for you, you have to do it by hand. This allows you to sieve up to 8 multiples per iteration.
This solution is beautiful. Thank you for sharing. No longer will I need to dynamically allocate huge arrays when solving prime number-related problems on Project Euler.
There were 0.5 to 2gb drives around then as were commercial offerings for arrays that could easily store 28. The growth has been huge, of course, but the mid 90s weren't entirely the stone age either.
Right but it's hardly astronomical and something that easily fit on a single array. My 1996 (work) workstation had about 9gb in regular drives hooked up to it. A lot, but nothing astronomical. DVDs were just around the corner, for another point of context.
Hah, I have pendaticornered myself with the astronomical. I guess a better way of putting it is - 1 gig drives came out in 91, the 2 gig barracuda in 92. By 94, typical personal device storage would be a bigger fraction of 30 gigs than, say, current typical personal device storage as a fraction of a current backblaze 4u pod. A backblaze pod is pretty mundane.
I think an average consumer HDD around that time was probably 100-200MB, no? I don't remember what the cheap desktop I bought in '94 had, but it was definitely not over a gig. I remember I bought a 6GB HDD that was already pretty cheap in '99, thinking "wow, disks are just massive now".
That's 28GB. That's just astronomical in those days' terms, even stored on hard drives it would have taken a massive array of commodity HDDs. I love these little reminders of how far we've come.