计算 e^x 的最快方法？

Question

假设 x 可以是浮点值，计算 e^x 的最快方法是什么。

现在我已经使用python的数学库来计算这个，下面是完整的代码，其中result = -0.490631 + 0.774275 * math.exp(0.474907 * sum)是主要逻辑，其余是问题所需的文件处理代码.

import math
import sys

def sum_digits(n):
   r = 0
   while n:
       r, n = r + n % 10, n // 10
   return r

def _print(string):
    fo = open("output.txt", "w+")
    fo.write(string)
    fo.close()

try:
    f = open('input.txt')
except IOError:
    _print("error")
    sys.exit()
data = f.read()
num = data.split('\n', 1)[0]
try:
   val = int(num)
except ValueError:
    _print("error")
    sys.exit()

sum = sum_digits(int(num))
f.close()

if (sum == 2):
    _print("1")
else:
    result = -0.490631 + 0.774275 * math.exp(0.474907 * sum)
    _print(str(math.ceil(result)))

result的右值是我用自己的数据集从wolfarm-mathematica导出的曲线方程（这是一个编程问题的解）。

但这似乎没有通过评估的标准！

我也尝试过 newton-raphson 方法，但是较大 x 的收敛导致了问题，除此之外，计算自然对数 ln(x) 又是一个挑战！

我没有任何语言限制，所以任何解决方案都是可以接受的。另外，如果 python 的数学库是最快的，正如某些评论所说，那么任何人都可以深入了解该程序的时间复杂度和执行时间，简而言之，该程序的效率？

Answer 1

我不知道这段代码中的指数曲线数学是否准确，但肯定不是慢点。

首先，您在一次 read 调用中读取输入数据。确实必须读取它，但这会加载整个文件。下一步只取第一行，所以使用 readline 似乎更合适。该拆分本身是 O(n)，其中 n 至少是文件大小，其中可能包括您忽略的数据，因为您只处理一行。

其次，将该行转换为 int。这可能需要 Python 的长整数支持，但操作可能是 O(n) 或 O(n^2)。单次通过算法会将每个数字的累积数字乘以 10，每次分配一个或两个新的（更长的）长整数。

第三，sum_digits 再次将 long int 分解为数字。它使用昂贵的除法和两个操作来做到这一点，而不是使用 divmod。那是 O(n^2)，因为每个部门都必须处理每个数字的每个较高数字。而且只是因为您刚刚进行的转换才需要它。

使用 sum(int(c) for c in l if c.isdigit()) 之类的方法可能更容易对字符串中找到的数字求和，其中 l 是输入行。它不是特别快，因为在数字转换中有相当多的开销并且总和可能会变大，但它确实通过相当紧密的循环进行了单次传递；它介于 O(n) 和 O(n log n) 之间，具体取决于数据的长度，因为总和本身可能会变大。

至于未知的指数曲线，存在小数异常的问题。如果答案无论如何都是整数，则可能还有其他一些更快、更准确的选项。

最后，您至少有四种不同的输出数据格式：error、2、3.0、3e+20。您知道其中哪些是预期的吗？也许您应该使用格式化输出而不是 str 来转换您的数字。

一个额外的注意事项：如果数据真的很大，分块处理肯定会加快速度（而不是运行内存不足，需要交换等）。当您正在寻找数字总和时，您的大小复杂度可以从 O(n) 降低到 O(log n)。

计算 e^x 的最快方法？

Fastest way to compute e^x?

python

optimization

mathematical-optimization