(2) hash access slows disproportionately whereas this lookup could just be an array. That array could be packed down to one bit per element for the most efficient storage, given that it has only boolean values. Lookup (and registration) can be achieved without unpacking from that using bit operators such as '<<' and '&', thereby winning on processing as well as storage.

What you describe is a primes sieve. One common prime generation technique is the Sieve of Eratosthenes. Another (sometimes slightly faster, but always more complicated) is the Sieve of Atkin.

I believe danaj has a blazing fast segmented sieve in Math::Prime::Util, and I have a pretty basic non-segmented Sieve of Eratosthenes implementation in Math::Prime::FastSieve.

Yes that's right, Dave. Coincidentally the sieve technique came up here only three weeks ago when a poster was trying to check a conjecture about Recaman's sequence. In thinking about primes, I did consider XS and C++ funnily enough, until I realised that prime or not is conceptually boolean and can be packed down to bits, so XS and C++ might be less urgent. Nevertheless I totally applaud the work you've done and XS and C++ is a very good choice.

One world, one people

In this case, the example is simply trying to show that results can be cached. As you say, we could reduce storage cost a lot and speed a little by using an array, string, or vector. Though one has to be careful with that as a single input of (for example) 1e18 will work fine with the hash but blow up with the other methods.

It turns out using a module (e.g. ntheory) for is_prime() is easier and faster overall anyway. No need to spend time on sieving, caching, memoize, etc. for these small sizes. But looking at the full context for this code, this is completely backwards -- he's using primality as a simple test vehicle to show caching.

That's why Davido's module uses XS and C++. An optimised Perl implementation would have a challenge to re-invent the processor in some ways, whereas in C++, structs can be used to map one datatype over another without any conversion, bit-shifting or reassignment making it easier to simulate a 2^N bit machine, where N is arbitrary.

One world, one people

That's why Davido's module uses XS and C++. An optimised Perl implementation would have a challenge to re-invent the processor in some ways, whereas in C++, structs can be used to map one datatype over another without any conversion, bit-shifting or reassignment making it easier to simulate a 2^N bit machine, where N is arbitrary.

I think you've missed the point. You said it would be more space efficient to use a bit array vs. a hash. That's right if your inputs are small, as a bit array (in Perl or C) takes only only N bits (N being the max entry), vs. a hash which in Perl is quite large per entry. Storing the result of every prime below 10M takes about 67MB as a hash, while only 1.5MB as a bit array (could be even less with some optimizations). But if I store the result of 10k random 32-bit numbers, then the hash wins by a huge amount.

My example was 1e18. This one entry now takes 1e18 bits to store just the single result. You can't do that, whether it is C or C++ or Perl. You need a different way to think about it. Your first solution is also a non-starter, as you certainly don't want to generate or store the 2.47e16 primes under that value. Unfortunately Math::Prime::FastSieve doesn't work at these large sizes, while Math::Prime::XS and Math::Prime::Util (ntheory) do.

Primality is not the same problem as prime generation.