Re: looking for a random function

From: Richard Heathfield (dontmail_at_address.co.uk.invalid)
Date: 03/28/04 

Date: Sun, 28 Mar 2004 09:55:40 +0000 (UTC)

Carsten Hansen wrote:

>
> "Pacsek" <pacsek@bellsouth.net> wrote in message
> news:uNm9c.69547$zP2.21068@bignews5.bellsouth.net...
> I'm trying to get an algorithm, preferably in C, that would pick up a
> random positive integer number, say, between 1 and n, n being a positive
> integer, too, but there would be a linear probability of picking the
> smaller number first. The higher the number, the less likely it will be
> selected. So 1 would have the most, n the least chance to be picked, and
> so on for the numbers in between.
>
> TIA
> Andrew
>
>
> Think of flipping a coin. You count how many times to you have to flip it
> until you get Heads.
> If you get Heads the first time, you return 1.
> If you first get Tails and then Heads, you return 2.
> If you have to flip the coin more than n times, you wrap around and start
> over at 1.
>
> int nrand(int n)
> {
> int counter = 0;
> for (;;)
> {
> int x = rand();
> if (x > MAX_RAND / 2)
> break;
> counter++;
> }
> return 1 + counter % n;
> }
>
> Carsten Hansen

Firstly, I think your algorithm can be expressed a little more naturally as:

int nrand(int n)
{
  int counter = 0;
  int x;
  while((x = rand()) <= RAND_MAX / 2)
  {
    ++counter;
  }
  return 1 + counter % n;
}

Secondly, I'm not sure it answers the question. The OP calls for a linear
approach but, in your solution, 1 has (roughly!) a 50% chance of being
selected, 2 has a 25% chance of being selected, 3 has a 12.5% chance of
being selected, and so on. If you plot these on a graph, you get a curve,
rather than a straight line. (Well, I know a straight line /is/ a curve,
but it's not a very bendy one.)

I believe the OP is after a straight-line function, so y = mx + c may prove
to be more enlightening than y = 1/(2^x). 

-- 
Richard Heathfield : binary@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

Relevant Pages

  • Re: C++ more efficient than C?
    ... If you want to do language comparisons, ... complicated algorithm, though). ... int compare ... not been in C's standard library. ...
    (comp.lang.c)
  • Re: Mersenne Twister -- A Revised C++ Implementation
    ... "That algorithm is a slight elaboration on the basic linear congruential ... takes an int, and an int on the target you seem to be developing on -- ... unless you qualify it by stressing that you ... compilation to pick the appropriate type in a more general manner. ...
    (comp.lang.cpp)
  • Re: Non-restoring binary square root and convergence
    ... I took the algorithm from "Algorithms for Extracting Square Roots and Cube ... % sqrt 9 16 ... int main ...
    (comp.programming)
  • Re: Non-restoring binary square root and convergence
    ... I took the algorithm from "Algorithms for Extracting Square Roots and Cube ... % sqrt 9 16 ... int main ...
    (sci.math)
  • Re: dijkstra algorithm issue
    ... I am just trying to implement Dijkstra's algorithm but i am not sure ... int n_vertices; ... draw a graph on paper,consider its adjacency matrix ... then compute by hand the shortest path you want on paper, ...
    (comp.programming)