# Fast Square Root For Distance Calculations?

This topic is 711 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I am facing a problem that calculating length of many vectors leads to huge performance drops and I am pretty much sure that the main reason is the square root algorithm that the programming language uses. What I thought - is there any faster, yet accurate approximation that I could use for the vector length calculation? Either faster square root equation or whole different vector length calculation.

Thanks!

##### Share on other sites

Depends on what you need, exact length (slowest) or just some length (use squared length) or just a comparison of what's closer.
There's this classic: https://en.wikipedia.org/wiki/Fast_inverse_square_root
Also Manhattan and Chebyshev's distances might be of interest.

##### Share on other sites

I am pretty much sure that the main reason is the square root algorithm that the programming language uses.

Which language? Most square roots will go direct to the processor these days, rather than be implemented via a software algorithm. This means it's unlikely you're going to get a faster implementation that is accurate.

If you have space, you might consider calculating and caching vector length whenever the vector value changes, making accessing it a O(1) operation - useful if you change the vector infrequently but measure them often.

##### Share on other sites

Hello!

Thanks for answers. Well, I don't need to compare 2 distances so the squared distance won't work. It turns out that square root wasn't my problem. I have the vector length calculated in a for loop together with few more(but actually lighter) equations. I was surprised how 1500 calculations in loop like this and a target game frequency of 500 Hz(100 Hz game frequency and 5 sub-steps) ended up in 20 FPS. That's incredibly bad result(especially knowing that I have decent laptop CPU(2.3 GHz, 4 cores). I am using Python and after a few analysis I found the problem - it turns out that Python is incredibly bad at for loops, like 50 times slower that C++ or Java. Hm... I didn't expect this. I am wondering - can I somehow optimize Python for loops and/or class access?

This isn't that important anyways as I'm using Python only for test stage(as it's incredibly easy to code in Python), I'll switch to C++ after.

##### Share on other sites

Well, it's working. I got a Python script that does mathematical calculations with use of vectors(but no matrices or any other similars). It does it all in loops. I write it in OOP. Somehow it seems that I got performance issues, but after checking my code several times I find it being clean and well-optimized. I read at some resources that loops in Python are incredibly slow. I just wanna get confirmation for this and, if possible, some ways to speed it up.

##### Share on other sites
One way to speed these things up in Python is to use numpy:

import numpy as np

vectors = np.random.rand(1500, 3)
lengths = np.linalg.norm(vectors, axis=1)


Voila, no (Python) loops. Edited by kloffy

##### Share on other sites

Python is not the optimal language for CPU-intensive operations because it intrinsically has layers of indirection between the language and the processor - the bytecode interpreter, the C objects representing your variables, the system calls implementing those objects, etc.

Therefore optimising Python is often a case of reducing the number of Python operations and replacing them with C operations. This can be done a few ways:

1) Replacing algorithms implemented in Python with standard library or built-in functions. For example, sometimes an explicit loop can be replaced with a call to the map() function - this moves the looping part into C code, and therefore is sometimes faster.
2) 3rd party C libraries like numpy (see above). For heavy mathematical lifting this is the number 1 choice.
3) Replacing the standard Python interpreter with one that compiles down to machine code. PyPy is the main choice here. Note that some extensions won't work with it.

4) Creating extensions in C that your Python program can use. You can make a module in C that Python can import and it'll usually run a lot faster than the equivalent Python code. Cython can help you a lot here.

5) Ditching Python entirely in favour of a faster language. Python is great but sometimes it's the wrong tool for the job. This might be a good time to consider whether you're using the right language. Consider also the target platforms and deployment method - Python is not great for mobile, won't run on the web, and deployment is a mess.

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 14
• 30
• 13
• 11
• 11
• ### Forum Statistics

• Total Topics
631781
• Total Posts
3002316
×