![]() |
|
|
#1 |
|
"Makis Christou"
Jun 2020
Cyprus
11 Posts |
So I am trying to create a new piece of software that searches for prime k-tuples similar to rieMiner. Mostly for fun and learning. Initially, I started by understanding some of the concepts and creating a toy Python implementation 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
(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 metrics 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 sieving 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?
|
|
|
|
![]() |
| Thread Tools | |
Similar Threads
|
||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| How to efficiently sieve for prime k-tuples | makis | Software | 9 | 2023-03-01 07:48 |
| On the Infinity of Twin Prime and other K-tuples | jzakiya | jzakiya | 111 | 2022-09-25 04:10 |
| prime k-tuples | MattcAnderson | Math | 0 | 2020-06-16 17:45 |
| How do you efficiently sieve for prime 3/4-tuples? | Puzzle-Peter | Software | 156 | 2019-06-03 20:19 |
| Prime 95 and Software OC'ing | Matt_G | Hardware | 13 | 2004-02-01 04:16 |