What algorithm should get the number closest to a constant that can be evenly (within the field) divisible by two other constants?
So let's say I have numbers A = 1483 and B = 635. My X = 100.0
Let's say my authorized MARGIN is 10.0
What's the best way to get the closest number to X (maybe a floating point) that can divide by A and B with a remainder less than MARGIN?
For K.'s answer A% K <= MARGIN, B% K <= MARGIN, where K is as close to X as possible, for example | K - X | <100
source to share
Let's try to write a problem with mathematical notation.
You have Euclidean divisions:
A = Q1*X + R1
B = Q2*X + R2
You want to find the minimum | x | such that
A = Q1'*(X+x) + R1' , |R1'| <= M
B = Q2'*(X+x) + R2' , |R2'| <= M
To help you find such x, you have relationships like:
A = Q1*(X+x) + R1-Q1*x
B = Q2*(X+x) + R2-Q2*x
Here, you should first focus on how to solve the example you gave and then try to generalize.
1483 = 14*100 + 83 = 15*100 - 17
635 = 6*100 + 35 = 7*100 - 65
If you can take x> 0 to decrease R2 (35) to 10, or x <0 to increase R1 (-17) to -10?
In the first case, x must be in the interval [25/6, 45/6] to bring | R2 '| <= M, but at the same time it must be in the interval [73/14, 93/14] to bring | R1 '| <= M.
Do these spacing overlap?
- if yes you have a solution.
- if not, then you need to try some more (reduce the numbers Q1 and / or Q2)
Just consult any decent translator (Squeak / Pharo Smalltalk here)
{25/6 . 45/6. 73/14 . 93/14} sorted = {(25/6) . (73/14) . (93/14) . (15/2)}
Thus, they overlap starting at x = 73/14.
But maybe you get closer x in the other direction?
I didn't give an algorithm, just hints for you to continue. But you can see that the increment doesn't have to be random (like 0.001).
source to share
Currently, the best way I have found is the brute force method, finding GCDs A and B and decreasing by a small interval (0.001) and finding the smallest c (K) where K> = X and c (x) = A% x + B% x
If I could find a way to correctly distinguish c (x), I would like to find its gradient and use gradient descent to find the most optimal value without brute force.
source to share