Normalizing A Vector

[Lawrence D'Oliveiro]

Say a vector V is a tuple of 3 numbers, not all zero. You want to normalize
it (scale all components by the same factor) so its magnitude is 1.

The usual way is something like this:

L = math.sqrt(V[0] * V[0] + V[1] * V[1] + V[2] * V[2])
V = (V[0] / L, V[1] / L, V[2] / L)

What I don’t like is having that intermediate variable L leftover after the
computation. Here’s how to do it in one step:

V = tuple \
(
x
/
math.sqrt
(
reduce(lambda a, b : a + b, (y * y for y in V), 0)
)
for x in V
)

which, incidentally, also works for vectors with dimensions other than 3.

 

[Alain Ketterlin]

Say a vector V is a tuple of 3 numbers, not all zero. You want to normalize
it (scale all components by the same factor) so its magnitude is 1.

The usual way is something like this:

L = math.sqrt(V[0] * V[0] + V[1] * V[1] + V[2] * V[2])
V = (V[0] / L, V[1] / L, V[2] / L)

What I don’t like is having that intermediate variable L leftover after the
computation.

Well, it also guarantees that the square root is computed once.

Here’s how to do it in one step:

V = tuple \
( x / math.sqrt
(
reduce(lambda a, b : a + b, (y * y for y in V), 0)
)
for x in V
)

which, incidentally, also works for vectors with dimensions other than 3.

And how many times does it call math.sqrt?

(That's actually not easy to test. Does any insider know the answer?
Does the compiler hoist the math.sqrt(...) out of the implicit loop? I
guess not, because it can't assert that reduce has no side effect.)

Your best bet is to define a function that does the normalization. Your
(local) name will disappear at the end of the call. If you want it to
work for any vector size:

def norm(V):
L = math.sqrt( sum( [x**2 for x in V] ) )
return [ x/L for x in V ]

If you do a lot of such computations, have a look at numpy.

-- Alain.

 

[Chris Rebert]

Say a vector V is a tuple of 3 numbers, not all zero. You want to normalize
it (scale all components by the same factor) so its magnitude is 1.

The usual way is something like this:

   L = math.sqrt(V[0] * V[0] + V[1] * V[1] + V[2] * V[2])
   V = (V[0] / L, V[1] / L, V[2] / L)

What I don’t like is having that intermediate variable L leftover after the
computation. Here’s how to do it in one step:

I suppose you'd be a fan of the proposed "given"/"where" statement
then (but its prognosis isn't great):
http://www.python.org/dev/peps/pep-3150/

Cheers,
Chris

 

[John Nagle]

Does the compiler hoist the math.sqrt(...) out of the implicit loop?

Global optimization in Python? Not in CPython.

The program might redefine math.sqrt from another
thread while the program is running, which would invalidate the
hoisting of the function. That has to be supported.

Shed Skin might do it, but it restricts the language and
doesn't allow the full dynamism of Python.

John Nagle

 

[Lawrence D'Oliveiro]

Well, it also guarantees that the square root is computed once.

OK, this version should solve that problem, without requiring any new
language features:

V = tuple \
(
x
/
l
for x in V
for l in
(math.sqrt(reduce(lambda a, b : a + b, (y * y for y in V), 0)),)
)

 

[Thomas Jollans]

reduce(lambda a, b : a + b, (y * y for y in V), 0))

This is a lot more verbose than it has to be, and probably slower too.

firstly:

(lambda a,b: a+b) is equivalent to operator.add.

==>
reduce(operator.add, (y*y for y in V), 0)

However - reduce with operator.add ? we have a special name for this:

==>
sum(y*y for y in V)

 

[Alain Ketterlin]

OK, this version should solve that problem, without requiring any new
language features:

V = tuple \
(
x
/
l
for x in V
for l in
(math.sqrt(reduce(lambda a, b : a + b, (y * y for y in V), 0)),)
)

You got the order wrong (it has to be for l ... for x ...)

You're kind of lucky here, because the arglist to tuple() provides a
scope that hides x and l. Be careful if you ever change tuple(...) to
[...], because x and l would leak to the outer scope (with python 2.*).
In the general case

for L in [...some-expr...]:
... whatever

doesn't hide L. Python doesn't provide a "let" construct (à la Lisp or
*ML).

-- Alain.

 

[Lawrence D'Oliveiro]

You got the order wrong (it has to be for l ... for x ...)

No, I deliberately put it in that order to ensure that the value for l can
only ever be evaulated once.

You're kind of lucky here, because the arglist to tuple() provides a
scope that hides x and l. Be careful if you ever change tuple(...) to
[...], because x and l would leak to the outer scope (with python 2.*).

Interesting. However, using “list( ... )†instead of “[ ... ]†also prevents
the leakage.

 

[Thomas Jollans]

You got the order wrong (it has to be for l ... for x ...)

No, I deliberately put it in that order to ensure that the value for l can
only ever be evaulated once.

You're kind of lucky here, because the arglist to tuple() provides a
scope that hides x and l. Be careful if you ever change tuple(...) to
[...], because x and l would leak to the outer scope (with python 2.*).

Interesting. However, using “list( ... )†instead of “[ ... ]†also prevents
the leakage.

Yes. That's because the variable leakage of list comprehensions was
never a good idea, and is kept in Python 2.x only for backwards
compatibility. When generator expressions where introduced, it was done
in such a way that the scope didn't leak (which probably wouldn't make
any sense anyway since there's no guarantee a generator expression is
executed at all before the next line)

In Python 3, list comprehensions don't leak names any more - they act
(nearly?) the same as like( ... expr ... ) now.

 

[Alain Ketterlin]

No, I deliberately put it in that order to ensure that the value for l can
only ever be evaulated once.

Try this (essentially equivalent to your code):

def f():
print "hello"
return 1

V = tuple( 1 for x in [1,2,3] for l in (f(),) )

How many "hello"s do you see?

Comprehension are not loops spelled backwards. The values in:

whatever for i ... for j ...

are the values produced by the equivalent code:

for i ...
for j ...
whatever

-- Alain.

 

[Terry Reedy]

Say a vector V is a tuple of 3 numbers, not all zero. You want to normalize
it (scale all components by the same factor) so its magnitude is 1.

The usual way is something like this:

L = math.sqrt(V[0] * V[0] + V[1] * V[1] + V[2] * V[2])
V = (V[0] / L, V[1] / L, V[2] / L)

What I don’t like is having that intermediate variable L leftover after the
computation.

So, instead of fooling around with error-prone, hard-to-type
constructions, just delete the damn thing!

def L

Compare those foolproof 5 chars to what at first did not work right and
even what did. And, as other said, in most real applications, you will
normalize in more than one place. In fact, you may well want a vlen
function.

def vlen(seq): return math.sqrt(sum(x*x for x in seq))

 

[Matteo Landi]

Say a vector V is a tuple of 3 numbers, not all zero. You want to
normalize
it (scale all components by the same factor) so its magnitude is 1.

The usual way is something like this:

    L = math.sqrt(V[0] * V[0] + V[1] * V[1] + V[2] * V[2])
    V = (V[0] / L, V[1] / L, V[2] / L)

What I don’t like is having that intermediate variable L leftover after
the
computation.

So, instead of fooling around with error-prone, hard-to-type constructions,
just delete the damn thing!

def L

del L

 

[Lawrence D'Oliveiro]

No, I deliberately put it in that order to ensure that the value for l
can only ever be evaulated once.

Try this (essentially equivalent to your code):

def f():
print "hello"
return 1

V = tuple( 1 for x in [1,2,3] for l in (f(),) )

How many "hello"s do you see?

Comprehension are not loops spelled backwards. The values in:

whatever for i ... for j ...

are the values produced by the equivalent code:

for i ...
for j ...
whatever

Damn. I thought that

e for i ... for j ...

was equivalent to

(e for i ...) for j ...

Looks like I was wrong.

 

[Bartc]

Say a vector V is a tuple of 3 numbers, not all zero. You want to
normalize
it (scale all components by the same factor) so its magnitude is 1.

The usual way is something like this:

L = math.sqrt(V[0] * V[0] + V[1] * V[1] + V[2] * V[2])
V = (V[0] / L, V[1] / L, V[2] / L)

Your best bet is to define a function that does the normalization. Your
(local) name will disappear at the end of the call. If you want it to
work for any vector size:

def norm(V):
L = math.sqrt( sum( [x**2 for x in V] ) )
return [ x/L for x in V ]

There's a cost involved in using those fancy constructions. I found the
following to be about twice as fast, when vectors are known to have 3
elements:

def norm3d(v):
L = math.sqrt((v[0]*v[0]+v[1]*v[1]+v[2]*v[2]))
return (v[0]/L,v[1]/L,v[2]/L)

(Strangely, changing those divides to multiplies made it slower.)

 

[Alain Ketterlin]

def norm(V):
L = math.sqrt( sum( [x**2 for x in V] ) )
return [ x/L for x in V ]

There's a cost involved in using those fancy constructions.

Sure. The above has three loops that take some time.

I found the following to be about twice as fast, when vectors are
known to have 3 elements:

def norm3d(v):
L = math.sqrt((v[0]*v[0]+v[1]*v[1]+v[2]*v[2]))
return (v[0]/L,v[1]/L,v[2]/L)

(Strangely, changing those divides to multiplies made it slower.)

You mean by setting L to 1.0 / math.sqrt(...) and using v[0]*L etc.?
I think * and / have the same cost on floats, and the added / adds
some cost. But what you observe is probably caused by the overloading of
"*", that needs more type checks. You may try with operator.mul to see
if the call compensates the cost of type checking, but I doubt it.

-- Alain.

 

[Bartc]

def norm3d(v):
L = math.sqrt((v[0]*v[0]+v[1]*v[1]+v[2]*v[2]))
return (v[0]/L,v[1]/L,v[2]/L)

(Strangely, changing those divides to multiplies made it slower.)

You mean by setting L to 1.0 / math.sqrt(...) and using v[0]*L etc.?
Yes.

I think * and / have the same cost on floats, and the added / adds
some cost.

I expected no measurable difference, not running Python anyway (I tried it
in gcc and using divides increased runtimes by 50%, corresponding to some 1%
for Python).

I would naturally have written it using multiplies, and was just surprised
at a 3-4% slowdown.

But what you observe is probably caused by the overloading of
"*", that needs more type checks.

That sounds reasonable.

 

[Lawrence D'Oliveiro]

There's a cost involved in using those fancy constructions.

Sure. But at the point that starts to matter, you have to ask yourself why
you’re not rewriting the CPU-intensive part in C.

 

[sturlamolden]

Say a vector V is a tuple of 3 numbers, not all zero. You want to normalize
it (scale all components by the same factor) so its magnitude is 1.

The usual way is something like this:

    L = math.sqrt(V[0] * V[0] + V[1] * V[1] + V[2] * V[2])
    V = (V[0] / L, V[1] / L, V[2] / L)

What I don’t like is having that intermediate variable L leftover after the
computation.

L = math.sqrt(V[0] * V[0] + V[1] * V[1] + V[2] * V[2])
V = (V[0] / L, V[1] / L, V[2] / L)
del L

But this is the kind of programming tasks where NumPy is nice:

V[:] = V / np.sqrt((V**2).sum())


Sturla