# Faster Distance formulae for higher n dimension

I need to calculate the distance two points, but these two points contain more than 100 dimensions. With the regular two or three dimension distance formula, we can extend this further to n dimension distance formula, however, this takes some computation time quite a bit. So if possible, I would like to find a way to cut down some computation, as I have quite a number of huge data sets.

My constrains are:

• In one data set, all points contain exactly n dimension, but n is quite huge, always more than 100.
• the numerical data in each dimension lies between 0 to 255 only.

With these constrains above, is there a faster way to compute the n dimension distance between each point in this case?

-
What is taking all that time for you? You're not doing a square root for each new dimension, are you? Or it is the squarings that cost you time? –  Henning Makholm Nov 21 '12 at 15:46
To be frank, I am not sure, but I am using en.wikipedia.org/wiki/Euclidean_distance#N_dimensions –  Karl Nov 21 '12 at 15:49
Frankly, in 100 dimensions, it might be the case that Euclidean distance is not the best measure anyway; high-dimensional space is just asn awful lot of void. The 1-norm $d(a,b)=\sum |a_i-b_i|$ or the $\infty$-norm $d(a,b)=\max |a_i-b_i|$ might be just as useful, but that depends on your intended application. –  Hagen von Eitzen Nov 21 '12 at 16:24
@Hagen: could you elaborate what is ∞-norm ? –  Karl Nov 22 '12 at 14:07

Squaring is generally quite fast, there are faster ways to optimize square roots http://en.wikipedia.org/wiki/Fast_inverse_square_root

You could always offload the computation onto the GPU if you have the freedom to do that. I'm not entirely sure of the situation here

You could also try building a lookup table of square numbers (between 0-255) if they are whole numbers only and keep in memory.

-