Thread: CRT offsets
View Single Post
Old 2021-04-06, 12:39   #17
Just call me Henry
henryzz's Avatar
Sep 2007
Cambridge (GMT/BST)

25·5·37 Posts

Originally Posted by R. Gerbicz View Post
For that record used only your 1st method with the following modification:
collect in array/vector those res values that occur maximal times as x%p and choose randomly(!) one res value from these. It gives some breath for the algorithm, but notice that you can stuck in a local min, so without several restarts you could be far from global min. I'd say the above result is not very far from optimal, but this is just my guess.
I think there are a few approaches to this.
I think you are suggesting randomly pick one that matches the res in question, randomize the others and then optimize everything using the previously defined methods.

Depending on how many primes hit the chosen res value it may be possible to do an exhaustive search for all of them(not certain but I think 10-15 would be possible). This would have the greatest chance of success I think.

I think an obvious optimization for this would be to recognize that there will be some very small primes that don't stand a chance of being changed. The sieve array could also be pre-populated with the sieve for all the other primes.

Local minima have the potential to be an issue. I need to try again with random starting points rather than just zeros. Selecting subsets that have more potential to improve to randomize seems like a decent way forward. Some form of simulated annealing might be sensible although I am not sure how to apply it in this case.
henryzz is offline   Reply With Quote