Thread: CRT offsets
View Single Post
Old 2021-04-01, 16:03   #2
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

134378 Posts
Default

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
henryzz is offline   Reply With Quote