[pygame] Re: [Tutor] Fastest (x,y) distance calculation

[Beni Cherniavsky]

Bob Ippolito wrote on 2003-09-12:

> You can think of complex numbers as a 2D plane in a lot of respects.
> The imaginary component is the Y axis, and the real component is the X
> axis.  abs(c) is defined as the distance from the origin complex(0, 0j)
> or math.sqrt(c.real**2 + c.imag**2).
>
> In any case, you're doing more computational work with abs or hypot
> because they are the actual distance, not the distance**2.
>
There is a way to find abs**2 of complex numbers without sqrt:

>>> a = 3 + 4j
>>> b = 6 + 8j
>>> d = a - b
>>> d * d.conjugate()
(25+0j)
>>> (d * d.conjugate()).real
25.0

The "conjugate" operation simply negates the imaginary part of a
complex number, so:

(X + Yj) * (X - Yj) == X**2 + XYj - XYj - (Yj)**2 == X**2 + Y**2

Alas, this turns out even less effecient than abs() , probably because
we do 4 float mutiplications (of which 2 we throw away) and because we
of two extra attribute accesses:

$ timeit.py -s 'd = 3 + 4j' '(d * d.conjugate()).real'
1000000 loops, best of 3: 1.45 usec per loop
$ timeit.py -s 'd = 3 + 4j' 'abs(d)'
1000000 loops, best of 3: 0.623 usec per loop

But `abs` on complex numbers *is* faster than multiplying integers by
themselves and adding:

$ timeit.py -s 'x = 3; y = 4' 'x * x + y * y'
1000000 loops, best of 3: 0.732 usec per loop

So `abs` wins so far (python2.3, x86).  If you use psyco, there is
little doubt that the simplest integer method will win by far.

-- 
Beni Cherniavsky <cben at users.sf.net>