Any good methods for generating pseudo random integer?
Author |
Message |
Enzhe Y #1 / 16
|
Any good methods for generating pseudo random integer?
Any good methods for generating pseudo random integer? --
|
Fri, 09 Nov 2001 03:00:00 GMT |
|
|
Jack Kle #2 / 16
|
Any good methods for generating pseudo random integer?
On Mon, 24 May 1999 21:23:17 GMT, "Enzhe Yu"
Quote: > Any good methods for generating pseudo random integer?
<Jack> What is wrong with rand() from <stdlib.h>, after suitably seeding using srand()? The FAQ has a few links to other random number generators. FAQ for comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html </Jack> -- Do not email me with questions about programming. Post them to the appropriate newsgroup. Followups to my posts are welcome. --
|
Sat, 10 Nov 2001 03:00:00 GMT |
|
|
kgol #3 / 16
|
Any good methods for generating pseudo random integer?
Quote:
> Any good methods for generating pseudo random integer?
Assuming you can't just call rand(), Plauger (The Standard C Library) has sample code for the ANSI C rand() function. --
--
|
Sat, 10 Nov 2001 03:00:00 GMT |
|
|
Keith Willi #4 / 16
|
Any good methods for generating pseudo random integer?
Quote:
> On Mon, 24 May 1999 21:23:17 GMT, "Enzhe Yu"
> > Any good methods for generating pseudo random integer? > What is wrong with rand() from <stdlib.h>, after suitably seeding > using srand()? The FAQ has a few links to other random number > generators.
The main thing that's wrong with it is the quality of the generator. Much better if your system supports it is drand48(). And this is useful for games, simulations and so on, but never for cryptographic use[1]. klw [1] Linear congruential generators were broken by Jim Reeds. See "Cracking a Multiplicative Congruential Encryption Algorithm" in _Information Linkage Between Applied Mathematics and Industry_, Academic Press, 1979. -- The above may or may not represent my own views. It quite probably does not represent the views of HP.
--
|
Fri, 23 Nov 2001 03:00:00 GMT |
|
|
Herman Rub #5 / 16
|
Any good methods for generating pseudo random integer?
Quote:
>On Mon, 24 May 1999 21:23:17 GMT, "Enzhe Yu"
>> Any good methods for generating pseudo random integer? ><Jack> >What is wrong with rand() from <stdlib.h>, after suitably seeding >using srand()? The FAQ has a few links to other random number >generators. >FAQ for comp.lang.c >http://www.eskimo.com/~scs/C-faq/top.html
There are quite a few pseudo-random generators. All of them start out by generating strings. Acceptance-rejection methods can produce integers uniform in a given range, as well as other integer distributions, from these. NONE of the present generators can be considered "safe". One should put in checks if possible, and the seeds for the generators should be in the hundreds, and preferably tens of thousands, of bytes. -- This address is for information only. I do not claim that these views are those of the Statistics Department or of Purdue University. Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
--
|
Fri, 23 Nov 2001 03:00:00 GMT |
|
|
Daniel Barke #6 / 16
|
Any good methods for generating pseudo random integer?
Quote:
> On Mon, 24 May 1999 21:23:17 GMT, "Enzhe Yu"
> > Any good methods for generating pseudo random integer? > <Jack> > What is wrong with rand() from <stdlib.h>, after suitably seeding > using srand()?
[snip] rand() is sometimes implemented in a way that gives a poor series of numbers, in that their departure from randomness may be quite obvious, even to someone who does not know the algorithm used to generate them. Another problem with rand() might be that it is implemented differently on different platforms. This could make it harder to test and debug a port to a new platform. It might also make it difficult to repeat runs, e.g., in a few years when the platform originally used no longer exists. This might matter in a scientific experiment, where the run suggested something controversial. One generator that is said to be statistically good, and gives identical results for the same seed across a wide variety of platforms (and languages), is Marsaglia's UNI. You can get a version of this, based on code kindly provided by the Edinburgh Parallel Computing Centre (EPCC), free at http://www.icmb.ed.ac.uk/sokal.html where it forms part of the program LVB. It is in files "myuni.h" and "myuni.c", which you will find there in the Unix source code distribution, "lvb.tar.Z". I can e-mail the text if the format of this archive is a problem. The code is not Unix-specific: it was also used in the Pentium Win32, PowerPC MacOS, Pentium Windows 3.1 and (not yet on the Web: ask me if you would like a free copy) Pentium OS/2 versions of LVB. The generator was described in: Marsaglia, G., Zaman, A. and Tsang, W. 1990. Towards a universal random number generator. Statistics & probability letters 9(1): 35-39 which gave fortran code, said to include a bug (fixed in the C code mentioned above). See the source code comments for details. Briefly, seed once, by passing rinit() an int in the interval 0..900000000. (If int cannot represent 900000000 on your system, some seeds will not be available to you.) Then call uni() without parameters as required to get a pseudo random number in the interval 0..1. Your problem is then to convert this to an integer. You could do this with something based on function randpint() in file "randpint.c" of the LVB source code, available from the URL above. -- Daniel Barker. --
|
Fri, 23 Nov 2001 03:00:00 GMT |
|
|
Michel Bardiau #7 / 16
|
Any good methods for generating pseudo random integer?
Quote:
> > Any good methods for generating pseudo random integer? > Assuming you can't just call rand(), Plauger (The Standard C Library) > has sample code for the ANSI C rand() function. > --
> --
He said *good* RNG. rand() is *not* good. -- Michel Bardiaux --
|
Fri, 23 Nov 2001 03:00:00 GMT |
|
|
J. Hold #8 / 16
|
Any good methods for generating pseudo random integer?
Quote:
> Any good methods for generating pseudo random integer?
While I do not have any suggestions for you, as no useful information on what you are doing is supplied to help us glean what sort of pseudo-randomness would be acceptable, I am obliged to quote John von Neumann: "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin." --
<jholder> do you like FreeBSD? <hal> I need to get the ISDN line running so that I will tell it to pass over me and replace my SuSE box with FreeBSD. --
|
Fri, 23 Nov 2001 03:00:00 GMT |
|
|
Pete Becke #9 / 16
|
Any good methods for generating pseudo random integer?
Quote:
> He said *good* RNG. rand() is *not* good.
Where in the C standard is this requirement? -- Pete Becker Dinkumware, Ltd. http://www.dinkumware.com --
|
Fri, 23 Nov 2001 03:00:00 GMT |
|
|
Pete Becke #10 / 16
|
Any good methods for generating pseudo random integer?
Quote:
> > What is wrong with rand() from <stdlib.h>, after suitably seeding > > using srand()? The FAQ has a few links to other random number > > generators. > The main thing that's wrong with it is the quality of the generator.
This depends very strongly on how it is implemented. -- Pete Becker Dinkumware, Ltd. http://www.dinkumware.com --
|
Fri, 23 Nov 2001 03:00:00 GMT |
|
|
Dave Hans #11 / 16
|
Any good methods for generating pseudo random integer?
Quote:
>> He said *good* RNG. rand() is *not* good. >Where in the C standard is this requirement?
That's not the issue. The C standard does not (and should not IMHO) specify any performance characteristics for rand() other than it return a "pseudo-random integer" between 0 and RAND_MAX, and that RAND_MAX be no smaller than 32767. The issue is "what is good?" Some applications have stringent requirements about certain "randomness" tests, others care more about speed, or small state space. If you don't have any particular requirements on random numbers, go ahead and use rand(). It's usually fine for things like screensavers. If your application has stringent requirements for random numbers and must be portable, do not use rand(). It is certain that some rand(), somewhere, does not meet your needs. If you have stringent requirements but need only support one platform, test the library's rand() to see if it meets your need. If it does, that's one less bit of code for you to maintain -- but watch out for "upgrades..." If you need something better than rand(), see Knuth's TAOCP, Vol 2 (IIRC) for extensive treatment of PRNGs. Regards, -=Dave Just my (10-010) cents I can barely speak for myself, so I certainly can't speak for B-Tree. Change is inevitable. Progress is not. --
|
Sat, 24 Nov 2001 03:00:00 GMT |
|
|
Pete Becke #12 / 16
|
Any good methods for generating pseudo random integer?
Quote:
> >> He said *good* RNG. rand() is *not* good. > >Where in the C standard is this requirement? > That's not the issue.
No, that's exactly the issue. The statement "rand() is not good" speaks to a particular implementation, not to what the standard requires. A better way to put it would be "most implementations of rand() are not good", if that's the point that was being made. There is nothing in the C standard that prevents writing rand() in a way that produces a "good" random number generator. -- Pete Becker Dinkumware, Ltd. http://www.dinkumware.com --
|
Sun, 25 Nov 2001 03:00:00 GMT |
|
|
Jim Georg #13 / 16
|
Any good methods for generating pseudo random integer?
Not too sure about this, but I've read about various "bifurcation series", such as that generated by Robert May's formula pn = r * n * ( 1 - n), where n is a population, pn the new population and r the growth rate. To quote Fractint's help system, "At growth rates less than 200%, this model is stable: for any starting value, after several generations the population settles down to a stable level. But for rates over 200%, the equation's curve splits or "bifurcates" into two discrete solutions, then four, and soon becomes chaotic.". So why not use this with a high growth rate, and use the "chaotic" numbers as random ones? There must be a catch somewhere, though, else some1 would've thought about this earlier. Inputs appreciated. -Jim --
|
Sun, 02 Dec 2001 03:00:00 GMT |
|
|
Gene Wirchen #14 / 16
|
Any good methods for generating pseudo random integer?
Quote:
>Not too sure about this, but I've read about various "bifurcation series", such >as that generated by Robert May's formula pn = r * n * ( 1 - n), where n is a >population, pn the new population and r the growth rate. To quote Fractint's >help system, "At growth rates less than 200%, this model is stable: for any >starting value, after several generations the population settles down to a >stable level. But for rates over 200%, the equation's curve splits or >"bifurcates" into two discrete solutions, then four, and soon becomes chaotic.". > So why not use this with a high growth rate, and use the "chaotic" numbers as >random ones? There must be a catch somewhere, though, else some1 would've >thought about this earlier. Inputs appreciated.
I suspect the chaotic numbers aren't random numbers. Take a look at a Mandelbrot graph. Sincerely, Gene Wirchenko Computerese Irregular Verb Conjugation: I have preferences. You have biases. He/She has prejudices. --
|
Tue, 04 Dec 2001 03:00:00 GMT |
|
|
Jens Schweikhard #15 / 16
|
Any good methods for generating pseudo random integer?
# Not too sure about this, but I've read about various "bifurcation series", such # as that generated by Robert May's formula pn = r * n * ( 1 - n), where n is a # population, pn the new population and r the growth rate. To quote Fractint's # help system, "At growth rates less than 200%, this model is stable: for any # starting value, after several generations the population settles down to a # stable level. But for rates over 200%, the equation's curve splits or # "bifurcates" into two discrete solutions, then four, and soon becomes chaotic.". # So why not use this with a high growth rate, and use the "chaotic" numbers as # random ones? There must be a catch somewhere, though, else some1 would've # thought about this earlier. Inputs appreciated. Plot the graph of that function, more precisely its iterated version. It's the well known "Logistic Map" (you can explore it online at http://www.mcasco.com/explorin.html You'll see that even in the "chaotic" region (whatever that means) there are some intervals where points accumulate more than elsewhere. Even for maximum r (4 IIRC) there seem to be accumulations at 0 and 1 [the mathematical term in German is "H?ufungspunkt"] but I might be wrong on this one, it's only from optical inspection :-) Making this on-topic for clcm: if my observations aren't bogus, the logistic map would be a suboptimal implementation for rand(), at least for certain applications. Regards, Jens -- Jens Schweikhardt http://www.shuttle.de/schweikh/ SIGSIG -- signature too long (core dumped) --
|
Tue, 04 Dec 2001 03:00:00 GMT |
|
|
Page 1 of 2
|
[ 16 post ] |
|
Go to page:
[1]
[2] |
|