Re: -- random points on the unit n-sphere

On Jan 12, 3:08 pm, quasi <qu...@xxxxxxxx> wrote:
What is an efficient algorithm to find random points on the unit
n-sphere?

In the intended application, n will be moderately large, say n = 99.

By random I mean "uniformly random" with respect to "surface area".

Of course, it will only be pseudorandom, that's ok.

Also, the random point may have a norm slightly off from 1, due to
rounding, that's also expected.

Precision is reasonably important (about 10 decimal places or better),
but speed is most important since the program will need to generate
thousands of such points.

I came up with one algorithm on my own, and I implemented it in Maple.
The algorithm is mathematically correct (i.e., the distribution is
uniform with respect to surface area), and the implementation works as
intended, but I sense there are probably faster methods.

Suggested algorithms, links, possible packages are all welcome.

For a given (normal) PC, to benchmark the various methods, I'd be
interested in the time required by each method to generate 1000 random
points on the unit 99-sphere.

quasi

Sample angle uniformly from 0..2 Pi, and height uniformly from 0..1,
then find point on half-sphere corresponding to that angle/height.
Surprising fact that this distribution is in fact uniform follows from
http://mathworld.wolfram.com/ArchimedesHat-BoxTheorem.html

Here's my Mathematica implementation
p := (th = RandomReal[{0, 2 Pi}];
z = RandomReal[{0, 1}]; {Sqrt[1 - z^2] Cos[th],
Sqrt[1 - z^2] Sin[th], z})
points = p & /@ Range[1000];
ListPointPlot3D[points]
.

Relevant Pages

  • Re: -- random points on the unit n-sphere
    ... I came up with one algorithm on my own, and I implemented it in Maple. ... Surprising fact that this distribution is in fact uniform follows from ...
    (sci.math)
  • Re: Geometrically distributed random numbers on Rabbit 2000.
    ... If you test the algorithm that Westhues and I mention, ... You imagine a circle centered inside a square and sized ... get two random uniform deviates U and V, ...
    (sci.electronics.design)
  • Re: Generation of range permutations?
    ... > where uniform() can be implemented using Benjamin Goldberg's ... it's not "my" algorithm; ... I recently discovered that the divide and conquer shuffle algorithm ... which I had thought was my own invention was previously discovered on ...
    (sci.crypt)
  • Re: Geometrically distributed random numbers on Rabbit 2000.
    ... i wonder if its possible to somehow converge the ... >where 'uniform' is a uniform deviate and p is the probability. ... >Are you only looking for an algorithm that will iterate geometrically? ... >If so, Knuth discusses, in exercise 6 on page 133, such an algorithm. ...
    (sci.electronics.design)