Thread: CRT offsets View Single Post 2021-04-01, 16:03 #2 henryzz Just call me Henry   "David" Sep 2007 Cambridge (GMT/BST) 134378 Posts I thought it might be useful for me to share my algorithms for optimizing the offsets for one or two primes. Any improvements or questions would be appreciated. Algorithm for optimizing one prime at once: 1. Calculate current score 2. Choose a prime p to investigate 3. Generate the sieve array ignoring the prime p 4. Loop through sieve array. If the element is set then increment the value for x % p to count how many times that modulus occurs. As we are iterating subtraction can be used rather than division to maintain speed. 5. Choose the modulus with the maximum number of occurrences. 6. Return to step 2 and choose the next prime Algorithm for optimizing two primes at once: 1. Calculate current score 2. Choose a prime p to investigate 3. Choose a candidate offset for the prime p 4. Calculate a score with the offset chosen in step 3. Record the difference between this and the best score. This difference is the improvement needed by the second prime. 5. Choose a prime q > p to investigate 6. Generate the sieve array ignoring the prime q 7. Loop through sieve array. If the element is set then increment the value for x % q to count how many times that modulus occurs. As we are iterating subtraction can be used rather than division to maintain speed. 8. Check if the modulus with the maximum number of occurrences improves the score enough to correct for the offset chosen in step 3(that was probably worse than the best). If so keep it. 9. Return to step 5 and choose the next prime unless all have been tried 9. Return to step 3 and choose the next offset unless all offsets have been tried 10. Return to step 2 and choose the next prime Last fiddled with by henryzz on 2021-04-01 at 16:18  