Как выполнить квадратный корень без использования математического модуля?

Ответ 1

Импорт математического модуля происходит только один раз, и вы, вероятно, не получите гораздо быстрее, чем математический модуль. Существует также более старый вопрос о Stackoverflow относительно который быстрее в Python: x **. 5 или math.sqrt(x)?. Неясно, какой метод выполняется быстрее.

Возможно, посмотрите NumPy и SciPy, не обязательно для sqrt, но если вы делаете тяжелые вычисления, они могут быть удобными.

Ответ 2

Как сказал Фабиан, трудно быть быстрее, чем math.sqrt. Причина в том, что он вызывает функцию соответствия из библиотеки C, с CPython.

Однако вы можете ускорить процесс, удалив служебные данные поиска атрибутов:

from math import sqrt

Каждый последующий вызов sqrt не должен искать его в математическом модуле, что экономит время выполнения:

print sqrt(2)

Здесь приведены временные номера: от самого быстрого до самого медленного (Python 2.6.5, Mac OS X 10.6.3): sqrt быстрее, чем **0.5:

[email protected] ~ % python -m timeit -s 'from math import sqrt; x = 2' 'sqrt(x)'
1000000 loops, best of 3: 0.207 usec per loop
[email protected] ~ % python -m timeit -s 'x = 2' 'x**0.5'
1000000 loops, best of 3: 0.226 usec per loop
[email protected] ~ % 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 предварительно вычисляется в CPython:

import dis

def f():
    return 2**0.5

print dis.dis(f)

печатает

2           0 LOAD_CONST               3 (1.4142135623730951)
            3 RETURN_VALUE        

где вы видите константу float sqrt (2) = 1.414...

Если вы манипулируете массивами чисел, NumPy sqrt - это путь, как указано в другом ответе.

Ответ 3

Я думаю, что математическая библиотека, вероятно, будет так же быстро, как и все, что вы могли бы написать сами. Но если вы хотите написать свой собственный, вот один алгоритм. Я не знаю 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

Ответ 4

В некоторых особых случаях вы можете торговать размером программы для скорости вздутия. Создайте большой массив и сохраните предварительно рассчитанный результат для каждой операции с квадратным корнем (используя входное значение в качестве индекса). Это довольно ограничено, но вы не получите ничего быстрее.

(Это как землетрясение)

Ответ 5

Вы можете реализовать метод Newton, но, хотя он очень быстро, он вряд ли будет быстрее, чем версия C, которую я предполагаю, реализована в математическом модуле. См. http://en.wikipedia.org/wiki/Methods_of_computing_square_roots.

Ответ 6

Используйте оператор питания и поднимите свои цифры на 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

Ответ 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))