What's the best way to find a perpendicular vector?
You don't need the cross-product, as long as you have a scalar product. Remember, most vector spaces do not have a cross-product, but a lot of them do have a scalar product.
Take any arbitrary vector $\vec{r}$ that is not parallel to the given vector $\vec{v}$.
Then $\vec{q} = \vec{r} - \left(\frac{\vec{r}\cdot\vec{v}}{\vec{v}\cdot\vec{v}}\right) \vec{v}$ will be orthogonal to $\vec{v}$.
To prove this, just show that $\vec{q} \cdot \vec{v} = 0$, which just takes a little bit of algebra.
This process is the basis of the Gram-Schmidt process, an important process in linear algebra.
To answer a question you didn't ask, one might wonder "Is there a nice formula that consumes a unit vector $v = (a,b,c)$ and produces a unit vector perpendicular to $v$?" (Of course, if you have a way to produce a vector perpendicular to $v$, you can always divide by its length to get a UNIT vector.)
If by "nice formula", you mean "a triple of expressions involving $a,b,c$, each of which is a continuous function", then the answer is (somewhat surprisingly) "no".
Such a formula would provide, for each point of the unit sphere (the endpoint of your vector $v$) a vector $w$ which, translated to the tip of $v$, is tangent to the sphere, i.e., you'd get an everywhere nonzero continuous vector field on the unit sphere.
And such a thing cannot exist by the Morse Index Theorem.
This is one of my favorite examples of a nice simple-sounding question being tied to a deep theorem of topology.
Given any vector $(a,b,c)$, with $a,b,c\neq 0$, a fast way to find a perpendicular vector is to consider
$$(-b,a,0) \implies (a,b,c)\cdot (-b,a,0) =-ab+ba+0=0$$
or other similar combination of the components as for example $(-c,0,a)$ or $(0,c,-b)$.
When one or two components are equal to zero, find a perpendicular vector is trivial, e.g. $(a,b,0)\perp (0,0,c)$.
If we are interested to find a triple of orthogonal vectors, starting from one given vector, assuming $a,b,c \neq 0$, we can proceed as follows:
- The starting vector contains two zero components, the orthogonal triple is
$$v_1=(a,0,0) \quad v_2=0,b,0) \quad v_3=(0,0,c)$$
- The starting vector contains one zero components, one orthogonal triple is
$$v_1=(a,b,0) \quad v_2=(-b,a,0) \quad v_3=(0,0,c)$$
- The starting vector doesn't contain zero components, one orthogonal triple is
$$v_1=(a,b,c) \quad v_2=(-b,a,0) \quad v_3=v_1 \times v_2 = (-ac,-bc,a^2+b^2)$$