我的问题可以用Python解决吗？是吗，怎么了？

Question

我需要能够输入两个部分已知的因子，每个因子精确到15位，产品答案精确到29位。在程序运行期间，两个因数的起始值（0.199848…和4.97438…）必须保持不变。每个因子中的零都是Python必须处理的和“数字变化”。当系数相乘时，这种“数值变化”必须产生乘积‭0.9941229342154732337566954206到29位小数，以匹配我的产品输入。我想知道Python运行完成后，匹配产品的最终因素是什么

例如：

我的意见 系数1 0.19984800000000‭ 系数2 4.9743800000000 产品‭0.99412293421547337566954206

输出： 输出值应该是0.199848442087413 X 4.974384208042620=‭0.99412293421547337566954206

因此，总之，Python将找出与我对已知产品的输入相匹配的因素‭我给它的0.99412293421547337566954206。我认为Python可能会在零上使用组合/置换，直到它找到一个生成我输入的产品的组合

Answer 1

一些指针

• 不能使用浮点数。它们只有大约17位十进制数字的精度，从十进制到二进制浮点的转换本质上是不精确的
• 一个好的起点是decimal模块

例如：

In [1]: import decimal as dm

In [2]: dm.getcontext().prec = 29

In [3]: factor1 = dm.Decimal('0.199848')
Out[3]: Decimal('0.199848')

In [4]: factor2 = dm.Decimal('4.97438')
Out[4]: Decimal('4.97438')

In [5]: desired = dm.Decimal('0.99412293432154732337566954206')
Out[5]: Decimal('0.99412293432154732337566954206')

In [6]: factor1*factor2 > desired
Out[6]: False

• 正如Błotosmętek在评论中指出的那样，组合的数量太多，无法进行暴力搜索。所以你必须换一种方式

请记住，一个产品可以：

• 小于要求的结果
• 等于要求的结果或结果
• 大于要求的结果

在第一种情况下，其中一个因素必须变得更大。在最后一种情况下，其中一个因素必须变小

由于第二个因素是最大的，我将从factor1开始。 在小数点后加9（最大可能增加），检查产品是否大于目标值

In [7]: new1 = dm.Decimal('0.1998489')
Out[7]: Decimal('0.1998489')

In [8]: new1*factor2 > desired
Out[8]: True

所以这个数字太大了。小于9/2的最大整数是4，所以试试看

In [9]: new1 = dm.Decimal('0.1998484')
Out[9]: Decimal('0.1998484')

In [10]: new1*factor2 > desired
Out[10]: False

现在将0.1998489和0.1998484之间的距离减半。再检查一下。你会发现 0.1998487太大，但0.1998486不太大

现在转到factor1的下一个数字，依此类推，直到找到factor1的正确位数

然后对factor2执行相同的操作，但现在还要测试相等性

编辑：关于暴力所需的时间

在我的机器上，将两个Decimal相乘并将其与第三个相乘大约需要119纳秒。有人可能会认为这并不太糟糕

In [2]: from decimal import Decimal

In [3]: f1 = Decimal('0.199848')
Out[3]: Decimal('0.199848')

In [4]: f2 = Decimal('4.97438')
Out[4]: Decimal('4.97438')

In [6]: result = Decimal('0.99412293432154732337566954206')
Out[6]: Decimal('0.99412293432154732337566954206')

In [7]: %timeit f1*f2 == result
119 ns ± 0.0114 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

但是考虑最坏的情况，我们必须做10 ^ 19的计算。让我们看看需要多长时间：

In [9]: round(119e-9*1e19/3600/24/365.25, 0)
Out[9]: 37709

因此，检查整个问题域至少需要38000年

当然，经过几次尝试，你会幸运地找到正确的结果。但不要指望这一点。如果事先不知道在哪里寻找，您可以合理地预期需要检查一半的问题域大约是19000年。因此，Błotosmętek说暴力搜索是不可行的