4 ms·

> 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

> 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.

pvg 6y ago
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. https://www-01.ibm.com/common/ssi/cgi-bin/ssialias?htmlfid=897/ENUS9394-001&infotype=DD&subtype=SM&appname=skmwww https://www-01.ibm.com/common/ssi/cgi-bin/ssialias?htmlfid=8...
- dvirsky 6y ago
  Of course, but you'd still need an array of a few dozens of those.
  - pvg 6y ago
    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.
    - dvirsky 6y ago
      Astronomical referred to memory, for disks I called it "massive".
      - pvg 6y ago
        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.
        dvirsky 6y ago
        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".
stabbles 6y ago
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. I have an implementation of it in Julia here: https://github.com/haampie/FastPrimeSieve.jl https://github.com/haampie/FastPrimeSieve.jl which was influenced by https://github.com/kimwalisch/primesieve https://github.com/kimwalisch/primesieve.
- ctchocula 6y ago
  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.
- dvirsky 6y ago
  Very cool idea! Still would require unrealistic amounts of memory for a 1994 desktop but super cool :)

pvg 6y ago

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. https://www-01.ibm.com/common/ssi/cgi-bin/ssialias?htmlfid=897/ENUS9394-001&infotype=DD&subtype=SM&appname=skmwww https://www-01.ibm.com/common/ssi/cgi-bin/ssialias?htmlfid=8...

dvirsky 6y ago
Of course, but you'd still need an array of a few dozens of those.
- pvg 6y ago
  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.
  - dvirsky 6y ago
    Astronomical referred to memory, for disks I called it "massive".
    - pvg 6y ago
      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.
      - dvirsky 6y ago
        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".

stabbles 6y ago

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. I have an implementation of it in Julia here: https://github.com/haampie/FastPrimeSieve.jl https://github.com/haampie/FastPrimeSieve.jl which was influenced by https://github.com/kimwalisch/primesieve https://github.com/kimwalisch/primesieve.

ctchocula 6y ago
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.
dvirsky 6y ago
Very cool idea! Still would require unrealistic amounts of memory for a 1994 desktop but super cool :)