Attempt for new software for prime k-tuples
 

So I am trying to create a new piece of software that searches for prime k-tuples similar to [URL="https://github.com/Pttn/rieMiner"]rieMiner[/URL]. Mostly for fun and learning. Initially, I started by understanding some of the concepts and creating a toy [URL="https://pastebin.com/4THLj7EB"]Python implementation[/URL] which seems to be working as expected (at least at first glance). I went on to write it in Rust but it was slow (compared to rieMiner), so as a sanity check I also wrote a C++ version and it seems to be as slow as the Rust code. When I say slow I mean rieMiner's eta is 24h and my eta is 1y :smile: (even with all the AVX stuff removed) for a 150 digit octuplet! Both of these versions implement the exact same logic as the Python code. The way I compared the speed was to implement the [URL="https://github.com/Pttn/rieMiner/blob/master/Stats.hpp#L19"]metrics[/URL] rieMiner has in my code and compare the eta. After profiling and trying to figure out where the inefficiency was I thought I might check if the problem was in the algorithm itself, specifically the sieving part. So I tried debugging rieMiner and used the same primorial, offset, pattern, difficulty (T) and prime_table_limit on my code to compare the implementations in more detail. It turns out that when I print the candidates that rieMiner actually tests for primality, they are a lot less than mine. I am in the process of trying to understand the [URL="https://github.com/Pttn/rieMiner/blob/master/Miner.cpp#L640"]sieving[/URL] in the author's code but I don't seem to be getting anywhere. The comments inside the _processSieve function claim that we "// Eliminate primorial factors of the form p*m + fp for every m*p in the current table.", which is exactly what I am doing but for some reason a lot more candidates are tested on my implementation. I also see that rieMiner does things a bit differently. While I am sieving once and then testing everything that is left, rieMiner is interleaving between sieving and testing so I am not sure if my comparison is fair. Can anyone help me figure this out?