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

[Pete Shinners <pete@shinners.org>]

forwarded post from unsubscribed
----------------------------------------------------------------------

From: Beni Cherniavsky
Subject: Re: [pygame] Re: [Tutor] Fastest (x,y) distance calculation
In-Reply-To: <3BFF1930-E55F-11D7-B303-000A95686CD8@threeoh.com>

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