how to perform square root without using math module??

Question

i want to find the square root of a number without using the math module,as i need to call the function some 20k times and dont want to slow down the execution by linking to the math module each time the function is called

is there any faster and easier way for finding square root??

Answer 1

Importing the math module only happens once, and you probably won't get much faster than the math module. There is also an older Stackoverflow question regarding Which is faster in Python: x**.5 or math.sqrt(x)?. It is not clear which method is faster.

Maybe take a look at NumPy and SciPy, not necessarily for the sqrt but if you're doing some heavy calculations they could be handy.

Answer 2

You could implement Newton's method but, though it's really fast, it's unlikely to be faster than the C version which I assume is implemented in the math module. See http://en.wikipedia.org/wiki/Methods_of_computing_square_roots .

Answer 3

Use the power operator, and raise your numbers to the 1/2 power:

>>> 2**0.5
1.4142135623730951

As to whether it's faster:

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

As Fabian said, it's hard to be faster than math.sqrt. The reason is that it calls the correspond function from the C library, with CPython.

However, you can speed things up by removing the overhead of attribute lookup:

from math import sqrt

Each subsequent call to sqrt will not have to look it up in the math module, which saves execution time:

print sqrt(2)

Here are timing numbers, from the fastest to the slowest (Python 2.6.5, Mac OS X 10.6.3): sqrt is faster than **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

Note that the timing tests calculate the square root of a variable. They do not calculate a constant like "2*0.5", because "2*0.5" is pre-calculated, in CPython:

import dis

def f():
    return 2**0.5

print dis.dis(f)

prints

2           0 LOAD_CONST               3 (1.4142135623730951)
            3 RETURN_VALUE        

where you see the constant float sqrt(2) = 1.414…

If you manipulate arrays of numbers, NumPy's sqrt is the way to go, as mentioned in another answer.

Answer 5

I'd think the math library would likely be as fast as anything you could write yourself. But if you want to write your own, here's one algorithm. I don't know Python, so I'll just write some 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

and the pseudocode translated to 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

In some special cases you can trade program size for blistering speed. Create a large array and store the pre-calculated result for every square root operation (using the input value as the index). It's pretty limited but you won't get anything faster.

(That's how quake did it)