As part of a more complex algorithm, I need a fast method to find random points of the n-sphere, $S^n$, starting with a RNG (random number generator). A simple way to do this (in low dimensions at least) is to select a random point of the (n+1)-ball and normalize it. And to get a random point of the (n+1)-ball select a random point of the (n+1)-cube $[-1,1]^{n+1}$ (by selecting (n+1) points of $[0,1)$ with the RNG and scaling using $x \mapsto 2x-1$) and then use "rejection", i.e., just ignore a point if it is not in the (n+1)-ball. This works fine if n is reasonably small, however for large n the volume of the ball is such a tiny fraction of the volume of the cube that rejection is enormously inefficient. So what is a good alternative approach. 



What is a good method to find random points on the n-sphere when n is large?
The usual approach is to generate $n+1$ i.i.d. mean zero Gaussian random variables $X\_1, \dotsc, X\_{n+1}$ to get a random point $X$ in $(n+1)$-space with rotationally invariant distribution and normalize.


Incidentally, if you ever actually need to generate a random point in an $n$-ball, the best way is probably to generate a random point in the $(n+1)$-sphere as above and drop the last two coordinates.


