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

Question

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?

What's the upper bound? Is it small enough to precompute all square roots once? — pault, Dec 10 '18 at 02:15
im leaving this as a comment because it is not a good answer, but math.sqrt is most likely faster than anything you can reasonably implement in python as math.sqrt links to C's sqrt. This of course depends on what you mean by 'less accurate', but im going to venture to say math.sqrt is going to be better. However, if you need to do many sqrt functions, you can vectorize this operation by putting these calculations into a numpy array and "sqrting" these entries. Can you be more specific on the type of calculation you are doing? — modesitt, Dec 10 '18 at 02:17
@ChuckIvan it actually is not https://stackoverflow.com/questions/327002/which-is-faster-in-python-x-5-or-math-sqrtx — modesitt, Dec 10 '18 at 02:21

modesitt · Answer 1 · 2018-12-10T02:48:40.457

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

Note NumPy has a [`tolist`](https://docs.scipy.org/doc/numpy/reference/generated/numpy.ndarray.tolist.html) method, so you can use this instead of `list(...)`. But, often, list conversion is not a necessity. — jpp, Dec 10 '18 at 02:30

Nir Alfasi · Answer 2 · 2018-12-10T02:42:16.737

@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

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

2 Answers2