什么算法可以让一个数字最接近一个可以均匀(在一定范围内)分成两个其他常数的常数?

What's an algorithm to get a number closest to a constant that can evenly (within a margin) divide into two other constants?

所以假设我有数字 A=1483 和 B = 635。我的 X=100.0

假设我允许的保证金是 10.0

获得最接近 X(可以是浮点数)且余数小于 MARGIN 的 A 和 B 的最佳方法是什么?

对于答案K。A % K <= MARGIN,B % K <= MARGIN,K尽可能接近X,例如|K - X| < 100

目前我找到的最好方法是通过找到 A 和 B 的 GCD 并减少一个小间隔 (0.001) 并找到最小的 c(K),其中 K >= X 和 c (x) = A % x + B % x

如果我找到了一种正确区分 c(x) 的方法,我会很想找到它的梯度并使用梯度下降来找到最优值而不需要蛮力。

让我们尝试用数学符号来写问题。

你得到的是欧氏除法:

A = Q1*X + R1
B = Q2*X + R2

您想找到最小的|x|这样

A = Q1'*(X+x) + R1' , |R1'| <= M
B = Q2'*(X+x) + R2' , |R2'| <= M

为了帮助您找到这样的 x,您有如下关系:

A = Q1*(X+x) + R1-Q1*x
B = Q2*(X+x) + R2-Q2*x

从这里开始,您应该首先专注于如何解决您给出的示例,然后尝试概括。

1483 = 14*100 + 83 = 15*100 - 17
 635 =  6*100 + 35 =  7*100 - 65

你应该取 x > 0 以将 R2 (35) 降低到 10,还是取 x < 0 以将 R1 (-17) 增加到 -10?

第一种情况,x应该在区间[25/6 , 45/6] 内才能带来|R2'| <= M,但同时必须在区间 [73/14 , 93/14] 才能带上 |R1'| <= M.

这些间隔是否重叠?

  • 如果是,您有解决方案。
  • 如果没有,那么你必须进一步尝试(减商Q1' and/or Q2')

只需咨询任何体面的解释器(Squeak/Pharo 这里是 Smalltalk)

 {25/6 . 45/6. 73/14 . 93/14} sorted
 = {(25/6) . (73/14) . (93/14) . (15/2)}

所以它们重叠,从 x=73/14 开始。
但也许你会在另一个方向得到更近的 x?

我没有给出算法,只是一个线索,看你继续。但是你看到增量不一定是随机的(比如 0.001)。