Python: поиск более быстрой и менее точной функции sqrt () - PullRequest
Новая
       11

Python: поиск более быстрой и менее точной функции sqrt ()

0 голосов
/ 10 декабря 2018

Я ищу более дешевую, менее точную функцию квадратного корня для большого объема вычислений пифагора, которые не требуют высокоточных результатов.Входные данные являются положительными целыми числами, и я могу ограничить входные данные при необходимости.Вывод в 1dp с точностью + - 0.1, если хорошо, но я мог бы даже сойти с выводом до ближайшего целого числа + - 1. Есть ли что-то встроенное в python, которое может помочь с этим?Что-то вроде math.sqrt (), которое делает меньше приближений, возможно?

Ответы [ 2 ]

0 голосов
/ 10 декабря 2018

@ ModeSitt был быстрее, чем я:)

Метод Ньютона это путь, мой вклад является реализация метода Ньютона, который немного быстрее, чем один предложенный ModeSitt (возьмем, например, sqrt (65), следующий метод вернется после 4 итераций против fast_sqrt, который вернется после 6 итераций). 

def sqrt(x):
    delta = 0.1
    runner = x / 2
    while abs(runner - (x / runner)) > delta:
        runner = ((x / runner) + runner) / 2
    return runner

При этом math.sqrt наверняка будет быстрее любогореализация, с которой вы придете.Давайте сравним два: 

import time
import math

def timeit1():
    s = time.time()
    for i in range(1, 1000000):
        x = sqrt(i)
    print("sqrt took %f seconds" % (time.time() - s))

def timeit2():
    s = time.time()
    for i in range(1, 1000000):
        x = math.sqrt(i)
    print("math.sqrt took %f seconds" % (time.time() - s))

timeit1()
timeit2()

Вывод, который я получил на своем компьютере (Macbook pro): 

sqrt took 3.229701 seconds
math.sqrt took 0.074377 seconds
0 голосов
/ 10 декабря 2018

Как я уже сказал в своем комментарии, я не думаю, что у вас будет намного лучше скорость по сравнению с math.sqrt в нативном питоне, учитывая его связь с C функцией sqrt.Тем не менее, ваш вопрос указывает на то, что вам нужно выполнить много «вычислений Пифагора».Я предполагаю, что вы имеете в виду, что у вас много треугольников со сторонами a и b, и вы хотите найти значение c для всех из них.Если это так, следующее будет достаточно быстро для вас.Это использует vectorization с numpy: 

import numpy as np

all_as = ... # python list of all of your a values 
all_bs = ... # python list of all of your b values 

cs = np.sqrt(np.array(all_as)**2 + np.array(all_bs)**2).tolist()

, если ваш вариант использования отличается, то, пожалуйста, обновите ваш вопрос с типом данных, которые вы имеете, и какую операцию вы хотите,

Однако, если вам действительно нужна реализация быстрого квадратного корня на python, вы можете использовать метод Ньютона` , чтобы сделать это: 

def fast_sqrt(y, tolerance=0.05) 
    prev = -1.0
    x = 1.0
    while abs(x - prev) > tolerance:  # within range
        prev = x
        x = x - (x * x - y) / (2 * x)
    return x

Однако дажес очень высокой терпимостью (0.5 абсурд), вы, скорее всего, не победите math.sqrt.Хотя у меня нет эталонных тестов, подтверждающих это :) - но я могу сделать их для вас (или вы тоже можете!)

...