performance - 快速乘法

Question

当我要计算以下系列1+x+x^2+x^3+...时，我更愿意这样做：（(1+x)(1+x^2)(1+x^4)...这就像某种重复平方）这样可以显着减少乘法的次数。

现在我想计算系列1+x/1!+(x^2)/2!+(x^3)/3!+...，我怎样才能使用类似的技术来提高乘法的数量？

任何建议都热烈欢迎！

Answer 1

你提到的优化方法，大概是Horner的方法：

a + bx +cx^2 +dx^3 = ((c+dx)x + b)x + a

交替级数 A*(1-x)(1+x^2)(1-x^4)(1+x^8) ... OTOH 可用于计算 A/(1+x) 的除法的近似值，其中 x 很小。

exp(x)的泰勒级数sigma x^n/n!收敛性很差；其他近似值更适合获得准确的值；如果有一个技巧可以减少乘法，那就是使用临时值进行迭代：

  sum=1; temp=x; k=1; 
  // The sum after first iteration is (1+x) or 1+x^1/1!
  for (i=1;i<=N;i++) { sum=sum+temp; k=k*(i+1); temp = temp * x / k; }
  // or
  prod=1.0; for (i=N;i>0;i--) prod = prod * x/(double)i + 1.0;

乘以阶乘应该会提高一点准确性——在现实生活temp=temp*x/(i+1)中，为了能够进一步迭代，或者使用查找表来获取常数 a_n / n!，可能是明智的，因为通常只需要几个术语。（sin/cos 的 4 或 5 个术语）。

事实证明，霍纳规则在几何级数到产品形式的转换中并没有太大的作用。Sigma x^n要计算指数，必须应用其他强大的技术——通常是范围缩减和有理数 (Pade)、多项式 (chebyshev) 近似等。

Answer 2

将评论转换为答案：

请注意，对于第一个系列，存在完全等价的：

1+x+x^2+x^3+...+x^n = (1-x^(n+1))/(1-x)

使用它，您可以更快地计算它。

第二个是收敛系列e^x，您可能想使用标准数学库函数pow(e, x)或exp(x)代替。

Answer 3

在第一个系列的方法中，您不认为使用 1 + x(1+ x( 1+ x( 1+x)....)) 会是更好的方法。类似的方法可以应用于第二个系列。所以 1 + x/1 ( 1+ x/2 (1 + x/3 * (1 + x/4(.....))))