如何在不使用数学模块的情况下执行平方根？

Question

我想在不使用数学模块的情况下找到数字的平方根，因为我需要调用函数约20k次，并且不希望每次调用函数时都通过链接到数学模块来减慢执行的速度

找到平方根有没有更快更简单的方法？

Answer 1

导入数学模块只发生一次，你可能不会比数学模块快得多。还有一个关于Which is faster in Python: x**.5 or math.sqrt(x)?的较旧的Stackoverflow问题。目前还不清楚哪种方法更快。

也许看看NumPy和SciPy，不一定是sqrt，但如果你正在做一些繁重的计算，他们可能会得心应手。

Answer 2

你可以实现牛顿的方法，但是，虽然速度非常快，但它不可能比我假设在数学模块中实现的C版本更快。见http://en.wikipedia.org/wiki/Methods_of_computing_square_roots。

Answer 3

使用电源操作，并提高数字的1/2功率：

>>> 2**0.5 
1.4142135623730951 

至于是否会更快：

>>> timeit.timeit(stmt='sqrt(x)', setup='from math import sqrt; x = 2') 
0.7182440785071833 
>>> timeit.timeit(stmt='x**0.5', setup='from math import sqrt; x = 2') 
0.87514279049432275 

Answer 4

至于法比安说，这是很难比快math.sqrt。原因是它使用CPython从C库中调用相应的函数。

from math import sqrt 

到开方以后每次通话将不一定要看它的数学模块，从而节省了执行时间：

但是，您可以通过删除属性查找的开销，加快东西：

print sqrt(2) 

这里是定时号码，从最快到最慢的（Python的2.6.5，Mac OS X的10.6.3）：sqrt比**0.5更快：

lebigot@weinberg ~ % python -m timeit -s 'from math import sqrt; x = 2' 'sqrt(x)' 
1000000 loops, best of 3: 0.207 usec per loop 
lebigot@weinberg ~ % python -m timeit -s 'x = 2' 'x**0.5' 
1000000 loops, best of 3: 0.226 usec per loop 
lebigot@weinberg ~ % python -m timeit -s 'import math; x = 2' 'math.sqrt(x)' 
1000000 loops, best of 3: 0.268 usec per loop 

请注意，计时测试计算变量的平方根。他们不计算恒定像2**0.5，因为2**0.5是预 -calculated，在CPython的：

import dis 

def f(): 
    return 2**0.5 

print dis.dis(f) 

打印

2   0 LOAD_CONST    3 (1.4142135623730951) 
      3 RETURN_VALUE   

在那里你看到不断浮动的sqrt（2）= 1.414 ...

如另一个答案中提到的，如果您操纵数组数组，NumPy的sqrt就是要走的路。

Answer 5

我想数学图书馆可能会和你自己写的任何东西一样快。但是如果你想自己写，这里有一个算法。我不知道Python，所以我只会写一些伪代码。

function sqrt(x) 
    lastGuess=x/2 
    loop 
    guess=(lastGuess+x/lastGuess)/2 
    if abs(guess-lastGuess)<.000001 // or whatever threshold you want 
     exit loop 
    lastGuess=guess 
    return guess 

和伪翻译到Python：

def sqrt(x): 
    last_guess= x/2.0 
    while True: 
     guess= (last_guess + x/last_guess)/2 
     if abs(guess - last_guess) < .000001: # example threshold 
      return guess 
     last_guess= guess 

Answer 6

在某些特殊情况下，你可以交易程序大小起泡速度。创建一个大型数组并存储每个平方根操作的预计算结果（使用输入值作为索引）。这是相当有限的，但你不会得到更快。

（这是怎么做到的）

Answer 7

用于计算正方形的Python代码片段。它首先做出初步猜测，如果猜测不够好，它会迭代，直到我们有一个好的猜测。

def gen_square_root_v1(number, epsilon): 

    #boundary condition check 

    if number == '1': 
     return 1 

    elif number <= 0: 
     print('this computes square root for positive numbers only') 

    else: 
     pass 


    prev_estimate = number/2 

    while True: 

     #each itearation, calculate a new estimate 
     new_estimate = (prev_estimate + number/prev_estimate)/2 

     #Alternatively can use if abs(new_estimate - prev_estimate) < epsilon: 

     #check the difference between square of new_estimate and number 
     if abs(new_estimate * new_estimate - number) < epsilon: 
     return prev_estimate 

    #if guess is not good enough, use it to make the next guess   
    prev_estimate = new_estimate 


#call the function  
print(gen_square_root_v1(16,1e-5))