Find a perpendicular vector in 3D to another 3D vector with same length?

Question

Is there a fast way to find such a 3d vector that is perpendicular to another 3d vector given $x,y,z$ and is same length that is efficient (no sqrt or $\cos$/$\sin$)? Like how in 2d such a vector is $(-y, x)$.

Answer 1

If I understand correctly, you want to find an efficiently computable function $f$ mapping any vector $x$ to another vector $f(x)$ such that $\|x\| = \|f(x)\|$ and $x \cdot f(x) = 0$. Let's call $F$ the set of all such functions.

First off, I'd argue against square roots being inefficient, since modern processors can take square roots almost as fast as they can divide. Your best bet, if you're asking because you want to code something, is just to go for the necessary square root operation. Don't fall for premature optimization.

But to preserve the spirit of your question, I'll use an intuitive definition of "efficiency" by counting the number of operations performed except the four elementary operations addition, subtraction, multiplication and division. A computation is more efficient than another if it uses fewer nonelementary operations. I'll leave unspecified what nonelementary operations are allowed, in your case you'd probably allow operations such as square roots, sines and cosines.

For this definition, the answer to your question is No.

What I'll prove is that any appropriate function $f \in F$ is exactly as efficient to compute as the function $g$ that takes a vector and computes its length, by implementing $g$ in terms of $f$ and some $f_0 \in F$ in terms of $g$ by using only elementary operations (scalar products and cross products are composed from those):

$$g(x) = \frac{x \cdot (x \times f(x))}{x \cdot x}$$

$$f_0(x) = \frac{x \cdot x}{g(x \times (x \times v))} \cdot (x \times v)$$

Here $v$ is any nonzero constant vector of your choice. ($f_0$ is not defined if $x$ is parallel to $v$, but you can special-case that. This special-casing or discontinuity is unavoidable: due to the hairy ball theorem there cannot be any $f \in F$ defined continuously everywhere).

As you can see, for every implementation of every choice of $f \in F$ there is an equally efficient implementation of $g$ by computing $f$ first, then using the formula for $g$ in terms of $f$. The same holds vice versa: for every implementation of $g$ there is an equally efficient implementation of $f_0$ by computing $g$ first, then using the provided formula. Since $f_0 \in F$, the best implementation of $g$ is therefore just as efficient to compute as the best implementation of the best choice for $f$.

Now since dividing by length is not very efficient, computing length is therefore also not very efficient, so computing $g$ is not very efficient, therefore computing $f$ is also not very efficient, no matter how you do it and how you choose $f \in F$.

---

Edit: Made a mistake defining $g$ in terms of $f$. I don't know how to resolve that, so I'm not sure that my claim (that $g$ and $f$ have the same efficiency) is even correct anymore.