Prime counting function

Haven’t updated my GSoC status in a while… I just added the prime counting function ( π(x) for all the nerds) which is just a simple for loop that uses is_prime().  Of course there is a better way to do that, but I’m going to save making algorithimic improvements for the optimizes phase.  There is both a test and an extended test and π(x) has been spot-checked up to around 10^6.

I also rewrote the XT for is_prime to pull a datafile from a different source… still works, but is kinda slow.  Again, I’ll be benchmarking these tests and seeing what kind of improvements I can make.  Right now the is_prime skips even numbers but that can be improved to check numbers modulo 8 or maybe someo ther base.  I can also include a list of small primes and do some trial division before hitting the more computationally intensive tests.  That should speed up the tests significantly.

Another posibility is to just replace the guts of is_prime with AKS – a deterministic polynomial-running time algorithim.  The benefits of would be pretty fantastic, but implementing it might be a little hairy.  All I’m saying is that it’s on the radar.

Posted in Google Summer of Code | Comments Off on Prime counting function

Comments are closed.