CODEWITHSUNDEEP
pythonperformancesqrt
Michael Hoy
Michael Hoy

Reputation: 21

Python: looking for a faster, less accurate sqrt() function

I'm looking for a cheaper, less accurate square root function for a high volume of pythagorus calculations that do not need highly accurate results. Inputs are positive integers, and I can upper-bound the input if necessary. Output to 1dp with accuracy +- 0.1 if good, but I could even get away with output to nearest integer +- 1. Is there anything built into python that can help with this? Something like math.sqrt() that does less approximations perhaps?

Upvotes: 1

Views: 2748

Answers (2)

modesitt
modesitt

Reputation: 7210

As I said in my comment, I do not think you will do much better in speed over math.sqrt in native python given it's linkage to C's sqrt function. However, your question indicates that you need to perform a lot of "Pythagoras calculations". I am assuming you mean you have a lot of triangles with sides a and b and you want to find the c value for all of them. If so, the following will be quick enough for you. This leverages vectorization with 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()

if your use-case is different, then please update your question with the kind of data you have and what operation you want.

However, if you really want a python implementation of fast square rooting, you can use Newton'ss method` to do this:

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

However, even with a very high tolerance (0.5 is absurd), you will most likely not beat math.sqrt. Although, I have no benchmarks to back this up :) - but I can make them for you (or you can do it too!)

Upvotes: 4

Nir Alfasi
Nir Alfasi

Reputation: 53535

@modesitt was faster than me :)

Newton's method is the way to go, my contribution is an implementation of Newton's method that is a bit faster than the one modesitt suggested (take sqrt(65) for example, the following method will return after 4 iterations vs fast_sqrt which will return after 6 iterations).

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

That said, math.sqrt will most certainly be faster then any implementation that you'll come with. Let's benchmark the two:

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

The output that I got on my machine (Macbook pro):

sqrt took 3.229701 seconds
math.sqrt took 0.074377 seconds

Upvotes: 1

Related Questions