  We develop an efficient algorithm for sampling the eigenvalues of random
matrices distributed according to the Haar measure over the orthogonal or
unitary group. Our technique samples directly a factorization of the Hessenberg
form of such matrices, and then computes their eigenvalues with a tailored
core-chasing algorithm. This approach requires a number of floating-point
operations that is quadratic in the order of the matrix being sampled, and can
be adapted to other matrix groups. In particular, we explain how it can be used
to sample the Haar measure over the special orthogonal and unitary groups and
the conditional probability distribution obtained by requiring the determinant
of the sampled matrix be a given complex number on the complex unit circle.
