Re: Geometrically distributed random numbers on Rabbit 2000.

On Wed, 08 Jun 2005 23:18:30 +1000, The Real Andy
<will_get_back_to_you_on_This> wrote:

><snip>
>The knuth algorith I have mentioned is for a uniformly distributed
>RNG. It was already approved by the government regulator for use in
>gaming applications, hence the reason for using it.

If you test the algorithm that Westhues and I mention, note that I did
NOT copy it correctly from the book and he did. I had glanced
casually at the marks and misread the bars there. So use the CEIL
function he mentions, though it may work similarly either way (I've
not thought it through.)

Otherwise, the algorithm mentioned in the exercise I pointed out is
quite simple. You imagine a circle centered inside a square and sized
so that it just touches the sides of the square. Then select only
quadrant 1 to work with and ignore the rest. Then imagine two uniform
deviates from 0 to 1, with one of them taken as the x-axis and the
other as the y-axis. Then:

(1) get two random uniform deviates U and V,
(2) if U^2+V^2 >= 1 then goto 1, else X is set to U.

The number of executions of step 2 has the geometric distribution.,
with a minimum of 1 time, an average of 4/PI times, a maximum of
infinity, and a deviation of (4/PI)*(SQRT(1-PI/4).

Get the book.

Jon
.

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: -- 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: 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)
  • Re: LOS problem
    ... Bresenham's algorithm is suited to none of these ... shadowcasting you can target a square if you can draw an unobstructed ... LoS functions for a particular destination. ... there are libraries for this as well. ...
    (rec.games.roguelike.development)