Haar sampling by Gaussian QR decomposition ($Q(G)\sim \mathrm{Haar}(O(n))$)

Generate a real $n$-by-$n$ matrix $G$ with independent entries having the standard normal distribution. Take its QR decomposition with positive diagonal in the upper triangular matrix factor, $G=QR$. The orthogonal matrix $Q$ has normalized Haar measure on the full orthogonal group $O(n)$. If a numerical factorization returns $Q_0{R}_0$, set $S=\mathrm{diag}(\mathrm{sgn}{R}_{0,ii})$ and return $Q_{0}S$. The signs are nonzero almost surely: successively drawn Gaussian columns have probability zero of lying in the proper linear subspace spanned by earlier columns.

For correctness, every fixed orthogonal matrix $U$ preserves the standard Gaussian column density and column independence, so $UG$ and $G$ have the same probability distribution. The positive-diagonal QR decomposition is unique: two decompositions would give an orthogonal matrix that is also an upper triangular matrix with positive diagonal, hence the identity. Therefore $Q(UG)=UQ(G)$ and $Q(G)$ has a left-invariant probability law. Uniqueness of normalized Haar measure on the compact group $O(n)$ identifies that law. Each determinant sign has probability $1/2$ by reflection invariance.