Comment faire une racine carrée sans utiliser de module mathématique?

Question

Je veux trouver la racine carrée d'un nombre sans utiliser le module math, car je dois appeler la fonction 20k fois et ne pas vouloir ralentir l'exécution en liant le module mathématique à chaque fois que la fonction est appelée

Existe-t-il un moyen plus rapide et plus facile de trouver une racine carrée?

Answer 1

L'importation du module mathématique ne se fait qu'une seule fois, et vous n'obtiendrez probablement pas beaucoup plus vite que le module mathématique. Il y a aussi une ancienne question Stackoverflow concernant Which is faster in Python: x**.5 or math.sqrt(x)?. Il n'est pas clair quelle méthode est la plus rapide.

Peut-être jeter un oeil à NumPy et SciPy, pas nécessairement pour le sqrt mais si vous faites des calculs lourds, ils pourraient être utiles.

Answer 2

Vous pouvez implémenter la méthode de Newton mais, bien que ce soit très rapide, il est peu probable qu'il soit plus rapide que la version C qui, je suppose, est implémentée dans le module mathématique. Voir http://en.wikipedia.org/wiki/Methods_of_computing_square_roots.

Answer 3

L'opérateur de puissance, et augmenter vos chiffres à la 1/2 puissance:

>>> 2**0.5 
1.4142135623730951 

Quant à savoir s'il est plus rapide:

>>> 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

Comme l'a dit Fabian, il est difficile d'être plus rapide que math.sqrt. La raison en est qu'il appelle la fonction correspondante de la bibliothèque C, avec CPython.

Cependant, vous pouvez accélérer les choses en supprimant les frais généraux de recherche d'attribut:

from math import sqrt 

Chaque appel ultérieur à sqrt sera pas doivent le chercher dans le module de calcul, ce qui fait gagner du temps d'exécution:

print sqrt(2) 

Voici chronométrons nombre, du plus rapide au plus lent (Python 2.6.5, Mac OS X 10.6.3): sqrt est plus rapide que **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 

Notez que les tests de synchronisation calculer la racine carrée d'une variable . Ils ne calculent pas une constante comme 2**0.5, parce que 2**0.5 est pré -calculated, en CPython:

import dis 

def f(): 
    return 2**0.5 

print dis.dis(f) 

impressions

2   0 LOAD_CONST    3 (1.4142135623730951) 
      3 RETURN_VALUE   

où vous voyez le sqrt flottant constant (2) = 1,414 ...

Si vous manipulez des tableaux de nombres, le sqrt de NumPy est le chemin à suivre, comme mentionné dans une autre réponse.

Answer 5

Je pense que la bibliothèque de mathématiques serait probablement aussi rapide que tout ce que vous pourriez écrire vous-même. Mais si vous voulez écrire le vôtre, voici un algorithme. Je ne connais pas Python, donc je vais juste écrire du pseudo-code.

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 

et le pseudo-code traduit en 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

Dans certains cas particuliers, vous pouvez échanger la taille du programme pour la vitesse boursouflures. Créez un grand tableau et stockez le résultat pré-calculé pour chaque opération racine carrée (en utilisant la valeur d'entrée comme index). C'est assez limité mais vous n'obtiendrez rien plus rapidement.

(Voilà comment le séisme a fait)

Answer 7

extrait de code Python pour calculer carré. Il fait d'abord une supposition initiale, et si la supposition n'est pas assez bon, il itère jusqu'à ce que nous ayons une bonne estimation.

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))