a space saving modification would be to have the bitmap only represent numbers that end in 1, 3, 7, and 9 (so one byte could cover a range of 20) as all primes other than 2 and 5 end in one of those numbers (and of course all evens other than 2 are excluded). In order to clear these bits quickly perhaps a tiny bit of assembly could be leveraged. Not sure about doing it in Java but in many other languages that would be fairly trivial (and of course, in something like C it might just optimize high level code adequately without assembly). Why would one want to do this? Well, perhaps to build a huge table of primes to act as potential factor candidates when searching for extremely large primes (as the table only needs to go up to the square root of the prime one's searching for). A further optimization might be to start run length encoding the number of zeros between the ones of this table as the distance between primes gets huge pretty quickly.
I think a rudimentary sieve in Clojure is challenge enough. And there can be optimizations but they make the code look significantly less elegant -- it requires "java interop" which makes the calls look like very.long.java.names/method.
Thanks for inviting me to take part in one of your videos, Daniel! I had so much fun recording this!
Also had an awesome time! Thanks so much for the collab!
Wow, what a treat! Thank you Pez & Daniel!
Glad you enjoyed it!
I've been using Calva to learn Clojure and it really helped a lot! Thanks Peter!
Thank you for taking the time to do this video!
a space saving modification would be to have the bitmap only represent numbers that end in 1, 3, 7, and 9 (so one byte could cover a range of 20) as all primes other than 2 and 5 end in one of those numbers (and of course all evens other than 2 are excluded). In order to clear these bits quickly perhaps a tiny bit of assembly could be leveraged. Not sure about doing it in Java but in many other languages that would be fairly trivial (and of course, in something like C it might just optimize high level code adequately without assembly).
Why would one want to do this? Well, perhaps to build a huge table of primes to act as potential factor candidates when searching for extremely large primes (as the table only needs to go up to the square root of the prime one's searching for).
A further optimization might be to start run length encoding the number of zeros between the ones of this table as the distance between primes gets huge pretty quickly.
I think a rudimentary sieve in Clojure is challenge enough. And there can be optimizations but they make the code look significantly less elegant -- it requires "java interop" which makes the calls look like very.long.java.names/method.
I mean, finding prime numbers has never been more lucrative.
👉🔢👉💰