Re: Generation of range permutations?

From: Benjamin Goldberg (goldbb2@earthlink.net)
Date: 02/18/03 

From: Benjamin Goldberg <goldbb2@earthlink.net>
Date: Tue, 18 Feb 2003 14:34:12 -0500

Michael Amling wrote:
[snip]
> where uniform() can be implemented using Benjamin Goldberg's
> bit-at-a-time algorithm. Let's see if I can recall it:
>
> int uniform(int upper) {
> // Return a random number uniformly distributed in 0..upper-1.
> int xx=1, yy=0;
> while (true) {
> while (xx<upper) {
> // Invariant: yy is uniform in 0..xx-1
> xx=xx*2;
> yy=yy*2+rbit();
> }
> if (yy<upper) {
> return yy;
> }
> xx=xx-upper;
> yy=yy-upper;
> }
> }

While this is a good algorithm for generating uniform random integers in
a range, it's not "my" algorithm; someone else invented it.

PS: I recently discovered that the divide and conquer shuffle algorithm
which I had thought was my own invention was previously discovered on
comp.lang.lisp -- my C and Perl implementations, though, had the
advantage of performing the shuffle in-place, without allocating new
memory for the data, and limiting the depth of recursion to at most
log_2(N). 

-- 
$;=qq qJ,krleahciPhueerarsintoitq;sub __{0 &&
my$__;s ee substr$;,$,&&++$__%$,--,1,qq;;;ee;
$__>2&&&__}$,=22+$;=~y yiy y;__ while$;;print

Relevant Pages

  • 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: -- 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: -- 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 ... Here's my Mathematica implementation ...
    (sci.math)
  • 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)