🚀 go-pugleaf

In 'comp.lang.c', "lovens weche" <fw1803@videotron.ca> wrote:

> 1st number genereated: 2
> 2nd number generated: 6
> 3rd number generated: 2 (WRONG!!! bad "period" as they say I think)

If you don't like your built-in pseudo-random generator (srand() once, rand() 
many times), you can implement your own. Search "Mersenne Twister" on Google.

-- 
-ed- emdel at noos.fr
The C-language FAQ: http://www.eskimo.com/~scs/C-faq/top.html
C-library: http://www.dinkumware.com/htm_cl/index.html
FAQ de f.c.l.c : http://www.isty-info.uvsq.fr/~rumeau/fclc/

"Clearly your code does not meet the original spec."
"You are sentenced to 30 lashes with a wet noodle."
                          -- Jerry Coffin in a.l.c.c++

lovens weche escribió:

> Hi, for a lotto program I'm working on I want to code a random number
> generator *but*  numbers generated must be always different.

Use std::random_shuffle over an array with all the numbers in it.

Regards.

lovens weche wrote:
> 
... snip ...
> 
> --- the code (don't you love the C programming language?
> ;) ------------------
> 
> a = 2 ^ 31;
> c = 3;
> m = (2 ^ 31) -1;
> 
... snip ...

i.e.:
  a = 33;
  c = 3;
  m = 32;

somehow I have niggling doubts that this is what you intended.

-- 
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>  USE worldnet address!

Emmanuel Delahaye wrote:
> 
> In 'comp.lang.c', "lovens weche" <fw1803@videotron.ca> wrote:
> 
> > 1st number genereated: 2
> > 2nd number generated: 6
> > 3rd number generated: 2 (WRONG!!! bad "period" as they say I think)
> 
> If you don't like your built-in pseudo-random generator (srand() once, rand()
> many times), you can implement your own. Search "Mersenne Twister" on Google.
> 

Won't help. A random number generator that doesn't repeat values isn't
random.

-- 

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

lovens weche wrote:
> 
> Hi, for a lotto program I'm working on I want to code a random number
> generator *but*  numbers generated must be always different.
> 
> ex:
> 
> 1st number genereated: 2
> 2nd number generated: 6
> 3rd number generated: 2 (WRONG!!! bad "period" as they say I think)
> 
> ok so we can forget the rand() funtion (please don't tell me to code a
> routine that checks numbers generated and if they repeat re-draw a number,
> bad performance code...)
> 
> ok here's the code I have to genereate the random numbers.. the variable a,
> c and m must be set by me the programmer.. hummm thats where my problems
> begin...
> 
> --- the code (don't you love the C programming language?
> ;) ------------------
> 
> a = 2 ^ 31;

This sets a to 2.

> c = 3;
> m = (2 ^ 31) -1;

This sets m to 1.

> 
> // wait 1 millisecond
> 
> VectCurrPtr[0] = (a * time() + c) % m;
> 
> for (i = 1; i < NumElem; i++)
>     VectCurrPtr[i] = (a * VectCurrPtr[i - 1] + c) % m;
> 

This is a linear congruential generator. With the values you've given
above it will do a very bad job of producing random numbers. But even
with good values it will repeat. And it should. Think about it: if you
threw a die and in every six throws you got all six faces exactly once
you'd be very suspicious. And you'd have a game that was very easy to
beat.

You need a second step beyond the random number generator, to supply a
random sequence:

for (i = 0; i < NumElem; i++)
	VectCurrPtr[i] = i;
for (i = NumElem; 1 < i; i--)
	{
	int j = rand() % (i - 1);
	int temp = VectCurrPtr[j];
	VectCurrPtr[j] = VectCurrPtr[i - 1];
	VectCurrPtr[i - 1] = temp;
	}

-- 

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

Pete Becker wrote:
> 
> > a = 2 ^ 31;
> 
> This sets a to 2.

Whoops, this sets a to 29.

> 
> > c = 3;
> > m = (2 ^ 31) -1;
> 
> This sets m to 1.

And this sets m to 28.

-- 

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

In 'comp.lang.c', Pete Becker <petebecker@acm.org> wrote:

>> > 1st number genereated: 2
>> > 2nd number generated: 6
>> > 3rd number generated: 2 (WRONG!!! bad "period" as they say I think)
>> 
>> If you don't like your built-in pseudo-random generator (srand() once,
>> rand() many times), you can implement your own. Search "Mersenne
>> Twister" on Google. 
> 
> Won't help. A random number generator that doesn't repeat values isn't
> random.

AFAIK, there is no 'random' generator here. Just PRNG (pseudo-random 
generator). Do you mean that inside it's period, a PRNG must have 
repetitions? In that case, it means that some values are missing. Always. Not 
very good, IMO.

Lets try with a 2^3 sequence (0-7).

0 1 2 3 4 5 7: balanced but predictable
2 5 1 4 0 1 2: unbalanced (missing values: 3, 7)
1 0 3 4 2 5 7: the kind of sequence I expect.

-- 
-ed- emdel at noos.fr
The C-language FAQ: http://www.eskimo.com/~scs/C-faq/top.html
C-library: http://www.dinkumware.com/htm_cl/index.html
FAQ de f.c.l.c : http://www.isty-info.uvsq.fr/~rumeau/fclc/

"Clearly your code does not meet the original spec."
"You are sentenced to 30 lashes with a wet noodle."
                          -- Jerry Coffin in a.l.c.c++

"lovens weche" <fw1803@videotron.ca> wrote in message news:<SikCa.1506$Z83.788@wagner.videotron.net>...

> Hi, for a lotto program I'm working on I want to code a random number
> generator *but*  numbers generated must be always different.
> 
> ex:
> 
> 1st number genereated: 2
> 2nd number generated: 6
> 3rd number generated: 2 (WRONG!!! bad "period" as they say I think)

No, that's not the period. The period is the point at which the random
sequence generated by rand() repeats itself. If this were the period
of rand(), then further calls to rand() would generate the sequence
(6, 2, 6, 2, 6, ...), and that's not very random at all.

rand() models a uniform distribution, meaning that one number is as
likely to be returned as any other, regardless of whether you received
it before. What you want is a combination (as opposed to permutation)
algorithm. You have N things (e.g., numbered balls in a bin) and you
want to select K of them at random. rand() can be made to do that:

  #include <stdio.h>
  #include <stdlib.h>

  /* return random n such that lo <= n < hi (implies lo < hi) */
  int randrange (int lo, int hi) {
    return rand() / (RAND_MAX / (hi - lo));
  }

  /* swap *p and *q */
  void int_swap (int *p, int *q) { int n = *p; *p = *q; *q = n; }

  /* shuffle the contents of the range [p, q) */
  void int_random_shuffle (int *p, int *q) {
    while (p != q) { int_swap(p, p + randrange(0, q - p)); ++p; }
  }

  int main () {
    int balls[60], i;

    srand(time(0));
    for (i = 0; i < 60; ++i) balls[i] = i + 1;
    int_random_shuffle(balls, balls + 60);
    for (i = 0; i < 6; ++i) printf("%d\n", balls[i]);
  }

NB: If this were C++, I'd've used std::random_shuffle. However, out of
my own courtesy for comp.lang.c, I didn't.

> ok so we can forget the rand() funtion (please don't tell me to code a
> routine that checks numbers generated and if they repeat re-draw a number,
> bad performance code...)

Nothing wrong with rand(); you just don't know how to use it. And I
doubt you need any kind of serious performance for a lottery game.
(I'd be more concerned with the small but real chance that the program
might never end.)

> the code (don't you love the C programming language? ;)

Not particularly. And why did you post this to C++ groups?

> // wait 1 millisecond
> 
> VectCurrPtr[0] = (a * time() + c) % m;
> 
> for (i = 1; i < NumElem; i++)
>     VectCurrPtr[i] = (a * VectCurrPtr[i - 1] + c) % m;

This is the lagged Fibonacci algorithm, a random number generator with
a uniform distribution. It's probably the algorithm that your rand()
uses. In other words, you probably just rewrote rand(), and for no
good reason.

> so if you eant look at the rules, then my code and tell me if my numbers
> will repeat. AND DON'T TELL ME TO CODE ADDITIONAL CODE TO CHECK IF THEY
> REAPEAT!!! already done that :(

Your code implements a uniform random number generator. Of course it's
going to repeat.

BTW: Why did you ask here? Running it should have told you that.

> ps: if you can send reply directly to my emial address that would be great:

C++ FAQ Lite, FAQ 5.4
<http://www.parashift.com/c++-faq-lite/how-to-post.html#faq-5.4>

  Do not say, "Please respond by e-mail because I don't normally read
  this newsgroup". If you don't have enough time for the newsgroup,
  don't expect the newsgroup to have enough time for you. 

- Shane

In 'comp.lang.c', Emmanuel Delahaye <emdelNOSPAM@noos.fr> wrote:

> 0 1 2 3 4 5 7: balanced but predictable
> 2 5 1 4 0 1 2: unbalanced (missing values: 3, 7)
> 1 0 3 4 2 5 7: the kind of sequence I expect.

Dammed! I have only 7 values!
 
0 1 2 3 4 5 6 7: balanced but predictable
2 5 1 4 0 1 6 2: unbalanced (missing values: 3, 7)
1 7 3 4 2 5 0 6: the kind of sequence I expect.

-- 
-ed- emdel at noos.fr
The C-language FAQ: http://www.eskimo.com/~scs/C-faq/top.html
C-library: http://www.dinkumware.com/htm_cl/index.html
FAQ de f.c.l.c : http://www.isty-info.uvsq.fr/~rumeau/fclc/

"Clearly your code does not meet the original spec."
"You are sentenced to 30 lashes with a wet noodle."
                          -- Jerry Coffin in a.l.c.c++

Emmanuel Delahaye wrote:
> 
> In 'comp.lang.c', Pete Becker <petebecker@acm.org> wrote:
> 
> >> > 1st number genereated: 2
> >> > 2nd number generated: 6
> >> > 3rd number generated: 2 (WRONG!!! bad "period" as they say I think)
> >>
> >> If you don't like your built-in pseudo-random generator (srand() once,
> >> rand() many times), you can implement your own. Search "Mersenne
> >> Twister" on Google.
> >
> > Won't help. A random number generator that doesn't repeat values isn't
> > random.
> 
> AFAIK, there is no 'random' generator here. Just PRNG (pseudo-random
> generator).

Sigh. Life is too short for this sort of hypertechnical tripe.

> Do you mean that inside it's period, a PRNG must have
> repetitions? In that case, it means that some values are missing. Always. Not
> very good, IMO.

I mean what I said: a long series of "random" numbers that has no
repetitions is highly suspect. Regardless, replacing rand with some
other generator won't solve the original problem.

-- 

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

Hi Lovens Weche,

Just another simple lotto generator (balls out of 45) and sorted

Good luck, Marco

/*
* Lotto Generator
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define RAND(x)     ((size_t)((x)*rand()/(1.0+RAND_MAX)))
#define SWAP(t,a,b) {t _Swap=a;a=b;b=_Swap;}

static void Lotto(size_t*,size_t,size_t);
static int Compare(const void*,const void*);

int main()
{
    size_t *Array,iDrawing,iCount,iTotal;

    srand((unsigned int)time(NULL));
    iCount=6;
    iTotal=45;
    if ( (Array=calloc(iTotal,sizeof(size_t)))==NULL ) return 1;
    for ( iDrawing=0; iDrawing<20; iDrawing++ ) Lotto(Array,iCount,iTotal);
    free(Array);
    return 0;
}

static void Lotto(size_t *Array,size_t iCount,size_t iTotal)
{
    size_t i,j;

    for ( i=0; i<iTotal; i++ ) Array[i]=i+1;
    for ( i=0; i<iCount; i++ ) {
        j=i+RAND(iTotal-i);
        SWAP(size_t,Array[i],Array[j]);
    }
    qsort(Array,iCount,sizeof(size_t),Compare);
    for ( i=0; i<iCount; i++ )
(void)fprintf(stdout,"%2d%c",Array[i],(i+1==iCount)?'\n':' ');
    return;
}

static int Compare(const void *a,const void *b)
{
    return (*(size_t**)a<*(size_t**)b)?-1:1;
}

sbeasley@cs.uic.edu (Shane Beasley) wrote in message news:<2f2d78e1.0306010613.71adae94@posting.google.com>...

> > // wait 1 millisecond
> > 
> > VectCurrPtr[0] = (a * time() + c) % m;
> > 
> > for (i = 1; i < NumElem; i++)
> >     VectCurrPtr[i] = (a * VectCurrPtr[i - 1] + c) % m;
> 
> This is the lagged Fibonacci algorithm,

Er, it's a linear congruential algorithm, though the two are related, apparently.

  http://www.wikipedia.org/wiki/Linear_congruential_generator
  http://www.wikipedia.org/wiki/Lagged_Fibonacci_Generators

Anyway, they're both drop-in replacements for rand(), which you don't need.

- Shane

WOWZER! 4 times faster than rand()??? cool! Thanx Emmanuel

btw. thanx to everyone who answered my problem, I really love the internet,
best tool for scientist everywhere, thanx all! ;)


Lovens

"Emmanuel Delahaye" <emdelNOSPAM@noos.fr> a �crit dans le message de news:
Xns938D836CA7DEFhsnoservernet@130.133.1.4...
> In 'comp.lang.c', "lovens weche" <fw1803@videotron.ca> wrote:
>
> > 1st number genereated: 2
> > 2nd number generated: 6
> > 3rd number generated: 2 (WRONG!!! bad "period" as they say I think)
>
> If you don't like your built-in pseudo-random generator (srand() once,
rand()
> many times), you can implement your own. Search "Mersenne Twister" on
Google.
>
> --
> -ed- emdel at noos.fr
> The C-language FAQ: http://www.eskimo.com/~scs/C-faq/top.html
> C-library: http://www.dinkumware.com/htm_cl/index.html
> FAQ de f.c.l.c : http://www.isty-info.uvsq.fr/~rumeau/fclc/
>
> "Clearly your code does not meet the original spec."
> "You are sentenced to 30 lashes with a wet noodle."
>                           -- Jerry Coffin in a.l.c.c++

> I mean what I said: a long series of "random" numbers that has no
> repetitions is highly suspect. Regardless, replacing rand with some
> other generator won't solve the original problem.

well I got 2 clever way to solve my problem with rand() via e-mail.. but I
will implement the Mersenne Twister algorithm as I love learning new
algorithms...


Lovens

...snip snip...

> >
>
> This is a linear congruential generator. With the values you've given
> above it will do a very bad job of producing random numbers. But even
> with good values it will repeat. And it should. Think about it: if you
> threw a die and in every six throws you got all six faces exactly once
> you'd be very suspicious. And you'd have a game that was very easy to
> beat.
>
> You need a second step beyond the random number generator, to supply a
> random sequence:
>
> for (i = 0; i < NumElem; i++)
> VectCurrPtr[i] = i;
> for (i = NumElem; 1 < i; i--)
> {
> int j = rand() % (i - 1);
> int temp = VectCurrPtr[j];
> VectCurrPtr[j] = VectCurrPtr[i - 1];
> VectCurrPtr[i - 1] = temp;
> }
>
> --

ok thanx Pete.. I'll try to implement it...


Lovens

lovens weche wrote:
> 
> WOWZER! 4 times faster than rand()???

That really depends on how fast rand() is on your system.
It would be mighty strange if it were true for systems which use 
alogorithms like the ones shown in this post:

http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&selm=TDWdnWU1LqbIiFyjXTWcqg%40comcast.com&rnum=4

-- 
pete

Marco de Boer wrote:
> Hi Lovens Weche,
> 
> Just another simple lotto generator (balls out of 45) and sorted
> 
> Good luck, Marco
> 
> /*
> * Lotto Generator
> */
> 
> #include <stdio.h>
> #include <stdlib.h>
> #include <time.h>
> 
> #define RAND(x)     ((size_t)((x)*rand()/(1.0+RAND_MAX)))
> #define SWAP(t,a,b) {t _Swap=a;a=b;b=_Swap;}
> 
> static void Lotto(size_t*,size_t,size_t);
> static int Compare(const void*,const void*);
> 
> int main()
> {
>     size_t *Array,iDrawing,iCount,iTotal;
> 
>     srand((unsigned int)time(NULL));
>     iCount=6;
>     iTotal=45;
>     if ( (Array=calloc(iTotal,sizeof(size_t)))==NULL ) return 1;
>     for ( iDrawing=0; iDrawing<20; iDrawing++ ) Lotto(Array,iCount,iTotal);
>     free(Array);
>     return 0;
> }
> 
> static void Lotto(size_t *Array,size_t iCount,size_t iTotal)
> {
>     size_t i,j;
> 
>     for ( i=0; i<iTotal; i++ ) Array[i]=i+1;
>     for ( i=0; i<iCount; i++ ) {
>         j=i+RAND(iTotal-i);
>         SWAP(size_t,Array[i],Array[j]);
>     }
>     qsort(Array,iCount,sizeof(size_t),Compare);
>     for ( i=0; i<iCount; i++ )
> (void)fprintf(stdout,"%2d%c",Array[i],(i+1==iCount)?'\n':' ');
>     return;
> }
> 
> static int Compare(const void *a,const void *b)
> {
>     return (*(size_t**)a<*(size_t**)b)?-1:1;
> }
> 
> 

I suppose this combination has as much chance as any of occuring:
Hardy: $ ./lotto
  1  2  3  4  5  6
  1  2  3  4  6  7
  1  2  3  4  5  7
  1  2  4  5  6  7
  1  2  3  4  5  6
  1  2  4  5  6  7
  1  2  3  4  5  6
  1  2  3  4  6  7
  1  2  3  4  5  6
  1  2  3  4  6  7
  1  2  3  4  5  6
  1  2  3  4  5  7
  1  2  3  4  5  7
  1  2  3  4  5  7
  1  2  3  4  5  6
  1  2  3  4  5  6
  1  2  3  4  5  6
  1  2  3  4  5  7
  1  2  3  4  5  6
  1  2  3  4  5  7

In article <SikCa.1506$Z83.788@wagner.videotron.net>, fw1803
@videotron.ca says...
> Hi, for a lotto program I'm working on I want to code a random number
> generator *but*  numbers generated must be always different.

That's not a random number generator, but a random _sample_ generator.  
Chapter 13 (column 13) of _More Programming Pearls_ is devoted to this 
particular problem.  (By Jon Bentley, published by Addison-Wesley, ISBN 
0-201-118899-0).  I'm not sure, but I seem to recall there being a newer 
Programming Pearls book which may contain an (updated version of) this 
as well -- by my memory's far from dependable on subjects like this.

> ok so we can forget the rand() funtion (please don't tell me to code a
> routine that checks numbers generated and if they repeat re-draw a number,
> bad performance code...)

Robert Floyd has designed a deceptively simple looking algorithm that 
produces correct results while still only calling rand once for each 
output number created.  It's outlined in the book above.

-- 
    Later,
    Jerry.

The universe is a figment of its own imagination.