使用泰勒级数来加速计算

Question

在数学中，Taylor series对于使用小函数多项式来近似函数是很重要的。

我想知道这样的近似如何有用，例如为了加速计算。让我们用著名的泰勒级数：

log(1+x) = x + 0.5 * x^2 + (error term) 

道义上，计算等级2的多项式的值应比计算log快得多。

因此，一个码来测试此：

import numpy, time 

def f(t): 
    return t + 0.5 * t ** 2 
f = numpy.vectorize(f) 

s = time.time() 
for i in range(100): 
    x = numpy.random.rand(100000) 
    numpy.log(1 + x) 
print time.time() - s   # 0.556999921799 seconds 

s = time.time() 
for i in range(100): 
    x = numpy.random.rand(100000) 
    f(x) 
print time.time() - s   # arghh! 4.81500005722 seconds 

为什么是多项式方法比实际慢日志10次？我预计相反。

PS：这个问题可能是在SO和数学中间。

Answer 1

随着Python + Numpy，它可能在这里和那里优化，所以它是不可能真正基准log(1+x)与x + 0.5 * x^2。 所以我转向了C++。

结果：每操作

时间与日志：19.57纳秒每个操作
时间与日志的顺序-2泰勒展开：3。73纳秒

所以大致x5因素！

---

#include <iostream> 
#include <math.h> 
#include <time.h> 
#define N (1000*1000*100) 
#define NANO (1000*1000*1000) 

int main() 
{ 
    float *x = (float*) malloc(N * sizeof(float)); 
    float y; 
    float elapsed1, elapsed2; 
    clock_t begin, end; 
    int i; 

    for (i = 0; i < N; i++) 
    x[i] = (float) (rand() + 1)/(float)(RAND_MAX); 

    begin = clock(); 
    for (i = 0; i < N; i++) 
    y = logf(x[i]); 
    end = clock(); 
    elapsed1 = float(end - begin)/CLOCKS_PER_SEC/N * NANO; 

    begin = clock(); 
    for (i = 0; i < N; i++) 
    y = x[i] + 0.5 * x[i] * x[i]; 
    end = clock(); 
    elapsed2 = float(end - begin)/CLOCKS_PER_SEC/N * NANO; 

    std::cout << "Time per operation with log: " << elapsed1 << " ns\n"; 
    std::cout << "Time per operation with order-2 Taylor epansion: " << elapsed2 << " ns"; 

    free(x); 

} 

Answer 2

使用numpy的矢量化操作几乎总是比你自己的代码中任何尝试的优化都快。正如@Divakar提到的那样，vectorize实际上只是一个编写for循环的简便方法，所以你的代码将比numpy的本地代码慢。

用标准Python代码替换numpy的优化例程，表明您的方法速度大致相同。

import math, numpy, time 


def f(t): 
    return t + 0.5 * t ** 2 

x = numpy.random.rand(1000000) 

s = time.time() 
for num in x: 
    math.log(1 + num) 
print (time.time() - s ) 

s = time.time() 
for num in x: 
    f(num) 
print (time.time() - s)  

结果：

1.1951053142547607 
1.3485901355743408 

逼近只是稍微慢一些，但幂是非常昂贵的。与t*t更换t ** 2给出了一个很好的改善，并允许近似略强于大盘python的log

1.1818947792053223 
0.8402454853057861 

编辑：另外，由于大课在这里进行了优化科学图书馆几乎任何一天胜过一周的手工编写的解决方案，这里是泰勒系列近似与numpy的矢量化操作，这是迄今为止最快的。请注意，唯一的重大变化是vectorize未在近似函数上调用，因此默认情况下使用numpy的矢量化操作。

import numpy, time 

def f(t): 
    return t + 0.5 * t ** 2 

x = numpy.random.rand(1000000) 
s = time.time() 
numpy.log(1 + x) 
print (time.time() - s) 

s = time.time() 
x = numpy.random.rand(100000) 
f(x) 
print (time.time() - s ) 

结果：

0.07202601432800293 
0.0019881725311279297 

有你有它，矢量化近似是在一个数量级的速度比numpy的真实矢量log。