16-bit random number generator?
May T. Young
or source code to generate random, 16 bit integers? Thank you!
Kendall Beaman
:
:May T. Young (myo...@farad.elee.calpoly.edu) wrote:
:
:: Can someone send me or point me towards an algorithm
:Check out rand and srand in the standard C library.
:
:--
:David Fox ro...@belvedere.sbay.org
:5479 Castle Manor Drive
:San Jose, CA 95129 Thanks for letting me change
:408/253-7992 magnetic patterns on your hard disk.
I'm assumming that May wants "an algorithm or source code to generate random,
16 bit integers." Not the standard random number generator which in my
opinion and a few others is not very good. Here's an algorithm that I
picked up from a friend of mine some years ago. It's pretty good.
/* ------------------------------my_rand()-------------------------------------
my_rand, implementation of random number generater described by S. Park
and K. Miller, in Communications of the ACM, Oct 88, 31:10, p. 1192-1201.
---------------------------------------------------------------------------- */
long int my_rand(void)
{
static long int a = 16807L, m = 2147483647L, q = 127773L, r = 2836L;
long int lo, hi, test;
hi = seed / q;
lo = seed % q;
test = a * lo - r * hi;
if (test > 0) seed = test; /* test for overflow */
else seed = test + m;
return(seed);
}
--
------------------------------------------------------------------------------
I don't mind what Congress does, as long as they don't do it in the
streets and frighten the horses. -- Victor Hugo
bea...@andrews.edu
May T. Young
> Can someone send me or point me towards an algorithm
>or source code to generate random, 16 bit integers? Thank you!
Thanks for the responses so far, but I think I should
have been more specific. I am not actually coding in C,
Modula-2, or Pascal -- these are simply languages I am
familiar with. I am programming in a simple, special purpose
language for a 16 bit platform. To give you some idea, I have
16 bit signed integers, no reals, and had to program my own
remainder function.
There are no random number generators in the
libraries so far. I need to generate random numbers in quick
succession and can only access the system clock in units of
one second, so polling the time won't work. I may soon resort
to generating a file of random integers in C/M2/Pascal and
reading the numbers from disk. That *might* be good enough
for the application, but I would like to have an honest random
number generator.
Thanks again!
Paul Laub
> Can someone send me or point me towards an algorithm
>or source code to generate random, 16 bit integers? Thank you!
Caveat emptor - Depending on the sensitivity of your application to the
extent of randomness in the PSEUDOrandom numbers generated, you could get
burned by artefactual results. I have seen it happen.
Check out Numerical Recipes in C both for discussion on pseudorandom number
generators and for reliable code. Note also that the authors of Numerical
Recipes look disapprovingly on stdlib.h's rand().
Knuth's book, volume 2, provides the definitive discussion on pseudorandom
number generation; see also Sedgwick's book "Algorithms" for simple
implementation of a chi squared statistical test of the randomness of your
(pseudo)random number generator's output.
Sincerely, Paul Laub
--
Paul Laub/Institute for Cancer Research/7701 Burholme Ave./Phila. PA 19111 USA
sisy...@astatine.fold.fccc.edu (215)728-2840 and -2748 fax: 728-3574
"He only earns his freedom and existence who daily conquers them anew." -Goethe
Bill Seurer
(*
* Generates random numbers using the Lehmer algorithm, f(z)=az MOD m. The default a is 16,807 and the default m is 2,147,483,647 (2**31-1).
* See "Random number Generators: Good Ones Are Hard To Find", Park, Stephen K., and Miller, Keith W., Communications of the ACM, October, 1988.
*)
PROCEDURE Real(): REAL;
(*
* Returns a random REAL number in the range [0..1)
*)
VAR
lo, hi, test: INTEGER;
BEGIN
hi := seed DIV q;
lo := seed MOD q;
test := a * lo - r * hi;
IF test > 0 THEN
seed := test;
ELSE
seed := test + m;
END (*Else*);
RETURN FLOAT(seed) / FLOAT(m);
END Real;
There's the heart of a random number module I implemented based on the
referenced paper. The a and m I use are for a 32 bit machine but the
article explains what to use for 16 bit machines.
--
- Bill Seurer Language and Compiler Development IBM Rochester, MN
Business: BillS...@vnet.ibm.com Home: BillS...@aol.com
whi...@galileo.meakins.mcgill.ca
An Oberon implementation of an algorithm described in paper
called "Good Random Number Generators are hard to find"
can be found on neptune.inf.ethz.ch. The Oberon implementation
is used in a book by Reiser and Wirth called Programming
in Oberon : Steps beyond Pascal and Modula.
Whitney
Martin Sohnius
Others have already given you the usual caveats about random number
generators in general and in particular. So here is about the
simplest one there is, pretty bad probably, but nevertheless
given as an example in the ISO-standard for C, as reprinted in
Plauger's book:
extern unsigned long Seed; /* initialised by srand() */
seed = seed * 1103515245 + 12345;
return seed/65536;
I've used this to implement a "poor man's" encrytion utility, where I had
to have control over the algorithm so it would return the same sequence on
a 68000 (Mac), SPARC (Sun), and i486 (UnixWare). It did.
--
Martin Sohnius
Novell Labs Europe | Press one for confusion, press two
Bracknell, England | for frustration, and any other number
+44-344-724031 | to hear this message again.
(My opinions may not be those of Novell!)
Steve Wainstead
In a previous article, myo...@farad.elee.calpoly.edu (May T. Young) says:
> Can someone send me or point me towards an algorithm
>or source code to generate random, 16 bit integers? Thank you!
I highly recommend Donald Knuth's Art of Computer Programming Vol 2.
available at any good library. He devotes a few chapters to the subject,
and discusses various ways of generating "random" numbers. I used this for
a class project:
X[n+1] = (a * X[n] - c) mod m
where X[n] is the array (natch), a, c, and m are provided by you somewhere
along the line. m should be very large - I used 12!-1 to get a large prime
number - and I filled an array of 15,000 elements and tested it for repeats
and there were none.
adiosville
>
--
when encryption is outlawed, yewiuy uuewyy8r4u f43y4 dk.
Bruce Pihlamae
>
stuff deleted
>
> X[n+1] = (a * X[n] - c) mod m
>
> where X[n] is the array (natch), a, c, and m are provided by you somewhere
> along the line. m should be very large - I used 12!-1 to get a large prime
> number - and I filled an array of 15,000 elements and tested it for repeats
> and there were none.
Ummmm. You probably know it already but you can't associate Randomness with
uniqueness. If you randomly produce numbers you should get RANDOM numbers
and that means repeats as well.
The thing to beware of with Random numbers is 'patterns' of numbers. The
number sequence 1 to 100 could be produced by a random number generator but
is it really random?
Knuth mentions quite a few tests etc. Have you tested your a,c,&m to see
how well they come out?
On the other hand if it's random enough for what you use it for then ...
--
Bruce... pih...@cbr.hhcs.gov.au
^^^^^^^^^^^^^^^^^^^^^^
NOTE: DEFAULT 'FROM' ADDRESS MAY BE STUFFED BY TEAMLINKS!!
*******************************************************************
* Bruce Pihlamae -- Database Administration *
* Commonwealth Department of Human Services and Health *
* Canberra, ACT, Australia (W) 06-289-7056 *
*=================================================================*
* These are my own thoughts and opinions, few that I have. *
*******************************************************************
"The more complex the argument gets, the easier it is to refute."
"Killing is wrong!" -- Trent 'The Uncatchable' Castanaveras
Mike Wonham
I suggest incorporating date and time into an algorithm for more 'randomness' within
the random number, any variable number can be used as a seed.
Mike Wonham
H{k{ H{kkinen
: Ummmm. You probably know it already but you can't associate Randomness with
: uniqueness. If you randomly produce numbers you should get RANDOM numbers
: and that means repeats as well.
: On the other hand if it's random enough for what you use it for then ...
Steve wrote "random" - not exactly random . I think, if you use the time
for seed or to choose the variable from that 15 000 choises, that would be
random enough for most purposes ? With seconds and minutes you can already
get thousands of choises. Am I right ?
Hannu.
Bruce Wilson
>random numbers then you could use the clock but on a PC you don't have
>a fine enough resolution. It jumps inchunks of hundredths of a second so he
>would need to work out where his significant digits of time are. But even so
>you would still be getting a constant MINUTES and SECONDS depending upon
>how often you sample the time.
Incidentally, notice that a clock-based seed for any card game that uses
52 cards will fall woefully short of hitting all possible games. (If all
possibilities are not equally likely, it ain't random).
52! ~= 8.06e67
24 * 60 * 60 * 100 = 8.64e6
So (dividing) you can see that the ratio of "reachable" decks to
"possible" decks is ~= 1:9.33e60, assuming a 24hr clock with 100th second
accuracy.
For more detail, you could always (like PGP does) ask the user to type
a few characters and time the intervals. If you put this information to
use right, I'm sure you could get much closer.
(Please, let's not let this turn into a "but how do I get a single
keystroke" thread :-)
>What he could do is use the first entry in his 15000 choices to determine
>which of the 15000 slots contains his random number; and then the second
>to find the next and the 3rd to find etc etc. He should recalculate each
>slot that he pulls a number from and when he gets to 15000 he should rebuild
>all 15000 and start again from 1.
>That is a fair bit of overhead but it sounds pseudo-random 8^}
Unfortunately, given the same seed, you'll still get the same sequence.
The only non-deterministic factor in a PC is the user input. (Unless you
have failing RAM or a weak spot on your HD platter). Hmm... possibly the
power-on values of RAM, but I believe the POST wipes them all.
Note the difference between random and arbitrary: random means nothing
can be predicted, where arbitrary means you don't care what the number is.
What I would do is fill an array with clock-seeded random numbers, then
use the keyboard-seeded RNG to select elements until the array is about
2/3 full. (You will get collisions, but that's not much of a tragedy).
Then reseed both RNG's and continue. Kinda like building your own
one-time pad. In a sense, you might think of it as "encrypting" the
sequence {1,2,3,...}, though of course nobody will ever try to decrypt.
>Have fun.
I did...
Salutations from one Bruce to another...
--
_____ _____ _____ __ __ _____ _____
/ ___// _ // ___// // // ___// _ / | Software means never having
/__ // // // / / // // /__ / ___/ | to say "I'm finished."
/____// ___//_/ /____//____//____/ |
/_/ @interaccess.com |
Chris Torek
<spruce@interaccess> writes:
>Incidentally, notice that a clock-based seed for any card game that uses
>52 cards will fall woefully short of hitting all possible games.
(Actually, so will any 16-bit LCRNG. You will do better with a good LFSR
algorithm. Again, see Knuth. One 32-bit LFSR pseudo-random generator is
available in the Berkeley net.2 C library random() function.)
>Unfortunately, given the same seed, you'll still get the same sequence.
>The only non-deterministic factor in a PC is the user input. (Unless you
>have failing RAM or a weak spot on your HD platter). Hmm... possibly the
>power-on values of RAM, but I believe the POST wipes them all.
Power-on values in RAM are decidedly non-random. (Memory with
parity or ECC also requires initialization; whether you can preserve
initial values while while setting the parity or ECC bits depends
on the design of your memory subsystem.) Typically, DRAMs are full
of all-ones areas and all-zeros areas on power-up, with a few
`almost random' bits at the boundaries between the seas of all-zero
and all-one bits.
Randomness is really quite hard to find in nature, at least at the
levels at which humans function.
--
In-Real-Life: Chris Torek, Berkeley Software Design Inc (+1 510 549 1145)
Berkeley, CA Domain: to...@bsdi.com
Bruce Pihlamae
Oh. I thought he was after a repeatable random sequence. If he just wants
random numbers then you could use the clock but on a PC you don't have
a fine enough resolution. It jumps inchunks of hundredths of a second so he
would need to work out where his significant digits of time are. But even so
you would still be getting a constant MINUTES and SECONDS depending upon
how often you sample the time.
What he could do is use the first entry in his 15000 choices to determine
which of the 15000 slots contains his random number; and then the second
to find the next and the 3rd to find etc etc. He should recalculate each
slot that he pulls a number from and when he gets to 15000 he should rebuild
all 15000 and start again from 1.
That is a fair bit of overhead but it sounds pseudo-random 8^}
Have fun.