How to generate a random quaternion quickly?

Question

I searched around and it turns out the answer to this is surprising hard to find. Theres algorithm out there that can generate a random orientation in quaternion form but they involve sqrt and trig functions. I dont really need a uniformly distributed orientation. I just need to generate (many) quaternions such that their randomness in orientation is "good enough." I cant specify what is "good enough" except that I need to be able to do the generation quickly.

Answer 1

Quoted from http://planning.cs.uiuc.edu/node198.html:

Choose three points u, v, w ∈ [0,1] uniformly at random. A uniform, random quaternion is given by the simple expression:

 h = ( sqrt(1-u) sin(2πv), sqrt(1-u) cos(2πv), sqrt(u) sin(2πw), sqrt(u) cos(2πw))

Answer 2

From Choosing a Point from the Surface of a Sphere by George Marsaglia:

1. Generate independent x, y uniformly in (-1..1) until z = x²+y² < 1.
2. Generate independent u, v uniformly in (-1..1) until w = u²+v² < 1.
3. Compute s = √((1-z) / w).
4. Return the quaternion (x, y, su, sv). It's already normalized.

This will generate a uniform random rotation because 4D spheres, unit quaternions and 3D rotations have equivalent measures.

The algorithm uses one square root, one division, and 16/π ≈ 5.09 random numbers on average. C++ code:

Quaternion random_quaternion() {
  double x,y,z, u,v,w, s;
  do { x = random(-1,1); y = random(-1,1); z = x*x + y*y; } while (z > 1);
  do { u = random(-1,1); v = random(-1,1); w = u*u + v*v; } while (w > 1);
  s = sqrt((1-z) / w);
  return Quaternion(x, y, s*u, s*v);
}