Fat*_*tso 9 algorithm math number-theory
我有两个号码,x1而且x2.对于一个数字y,我想计算公约数x1和x2尽可能接近的公约数y.
有一个有效的算法吗？
我认为现在是时候重新解决我的问题并且更清楚了.这不是关于整数...所以,我们有两个数字x1和x2.比如说,用户输入一个数字y.我想要找到的是一个y'接近的数字y,x1 % y'并且x2 % y'非常小(0.02例如,小于,但我们可以调用这个数字LIMIT).换句话说,我不需要最优算法,但需要很好的近似.
我感谢你们所有的时间和精力,非常友好!
我认为对于这个问题没有已知的有效(多项式时间)算法,因为从整数因子分解到这个问题存在多项式时间减少.由于没有用于整数分解的已知多项式时间算法,因此对于您的问题也不可能有已知的算法,因为否则我们确实会有一个用于整数分解的多项式时间算法.
要了解其工作原理,假设您有一个您想要考虑的数字n.现在,使用您想要的任何算法,找到最接近√n的n和n的公因子.由于n的非平凡除数不能大于√n,因此找到(1)除以n的最大整数,或者(2)如果n为素数则为1.然后,您可以将n除以此数字并重复以生成n的所有因子.由于n最多只能有O(log n)个因子,因此对于你的问题,这最多需要求解器的多次迭代,因此我们有一个从整数因子分解到这个问题的多项式时间减少.如上所述,这意味着,至少在公开文献中,没有已知的有效经典算法来解决该问题.可能存在一个,但这将是一个非常重要的结果.
对不起,否定的答案,希望这有帮助!
| 归档时间： |
|
| 查看次数： |
3631 次 |
| 最近记录： |