473,573 Members | 4,482 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Random Seeding

If you only use a 32 bit seed for a random number generator,
does that mean you can only ever produce a maximum of
2^32 (approx 4 billion) different sequences?

What about the Mersenne Twister, with it's massive period
of 2^19937-1. Will you only ever have access to a tiny
portion of this ring of numbers, if you only use a 32-bit seed?
Will this set of sequences be confined to the beginning of the
period, ie, your sequence will have to start at some place
between index number 1 and 4 billion of the period (ignores
all the possible data after this)?.

Or have I misunderstood the concept of a seed?

(I am using the original c code from...
http://www.math.sci.hiroshima-u.ac.j...at/MT/emt.html)

May 15 '06 #1
13 3177
I would suggest that your possibly get 2^32 sequences with 2^19937-1
number
of elements in each.

May 15 '06 #2
> (ignores all the possible data after this)?.

this should have read:

(ignores all the possible "starting points" after this)?.
I would suggest that your possibly get 2^32 sequences with 2^19937-1
number of elements in each.


That's kind of what I thought. It seems fairly limited.
However, I just realised the Mersenne Twister c code
provided by it's inventors allows for longer seeds.

"Those who need initial seed with more than 32-bit
length may use init_by_array() for initialization which
admits an array of arbitrary length as seeds"

I guess you could use an array seeded with the time,
the process ID, and some compressed info from
/dev/random or /dev/audio. Still I imagine it would
still be very difficult to guarantee starting points
distibuted uniformly around the ring of numbers?

May 15 '06 #3
>If you only use a 32 bit seed for a random number generator,
does that mean you can only ever produce a maximum of
2^32 (approx 4 billion) different sequences?
Yes, assuming you always start a sequence with the first number
generated after seeding. It may be possible to use a "secondary
seed" by getting and throwing away N pseudo-random numbers before
using one, which, depending on the generator, may or may not improve
anything.
What about the Mersenne Twister, with it's massive period
of 2^19937-1. Will you only ever have access to a tiny
portion of this ring of numbers, if you only use a 32-bit seed?
It is quite possible to cripple a good pseudo-random number generator
with a poor seed.
Will this set of sequences be confined to the beginning of the
period, ie, your sequence will have to start at some place
between index number 1 and 4 billion of the period (ignores
all the possible data after this)?.


I don't think there's any guarantee of that, and it would depend
on the generator.

Gordon L. Burditt
May 15 '06 #4
In article <11************ **********@i39g 2000cwa.googleg roups.com> po*********@yah oo.com writes:
If you only use a 32 bit seed for a random number generator,
does that mean you can only ever produce a maximum of
2^32 (approx 4 billion) different sequences?
Depends on the generator. With some you may generate entirely different
sequences, with others you just generate different starting points in
a single sequence.
What about the Mersenne Twister, with it's massive period
of 2^19937-1. Will you only ever have access to a tiny
portion of this ring of numbers, if you only use a 32-bit seed?
No, you will ultimately get the whole range. If I understand it well,
MT uses a linear congruence method, and they inherently have only a
single loop as result.
Will this set of sequences be confined to the beginning of the
period, ie, your sequence will have to start at some place
between index number 1 and 4 billion of the period (ignores
all the possible data after this)?.


Not at all. In the Mersenne Twister you have a state of 19937 bits.
The state loops around all those different states, but when the state
has the appropriate 19905 bits equal to 0 (representing the 32 bit
starting points) is not clear. So you do indeed jump in a different
position of the generator, but those positions are not regularly
spaced around the loop.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
May 15 '06 #5
po*********@yah oo.com writes:
(ignores all the possible data after this)?.


this should have read:

(ignores all the possible "starting points" after this)?.
I would suggest that your possibly get 2^32 sequences with 2^19937-1
number of elements in each.


That's kind of what I thought. It seems fairly limited.
However, I just realised the Mersenne Twister c code
provided by it's inventors allows for longer seeds.

"Those who need initial seed with more than 32-bit
length may use init_by_array() for initialization which
admits an array of arbitrary length as seeds"

I guess you could use an array seeded with the time,
the process ID, and some compressed info from
/dev/random or /dev/audio. Still I imagine it would
still be very difficult to guarantee starting points
distibuted uniformly around the ring of numbers?


<OT>
If you have /dev/random, why would you bother with the time, the
process ID, or /dev/audio?

For that matter, if you have /dev/random, it's not entirely clear you
need to bother with a Mersenne Twister (but the question is beyond my
expertise).
</OT>

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
May 15 '06 #6
Well, that kind of leads into the next question I
was going to ask. How can I make the seeding
work on all platforms? I have /dev/random on
my linux box, but not on Windows (and I havent
checked if its on my MAC, which is BSD based).

Does Windows have an Entropy Pool like
/dev/random that can be accessed by C.
(OK, I guess that's slightly off topic).

More on topic, do I have to use #ifdef statements
to provide for entropy pools on different platforms?
I was just going to use the functions provided by
#include <time.h>, but I'm not happy that it gives
me a wide enough range of seeds.

(BTW, /dev/random may or may not be "random enough"
compared to the MT, but it more than likely is not fast
enough, since the disk must be accessed).

May 15 '06 #7


Keith Thompson wrote On 05/15/06 16:13,:
po*********@yah oo.com writes:
(ignores all the possible data after this)?.


this should have read:

(ignores all the possible "starting points" after this)?.

I would suggest that your possibly get 2^32 sequences with 2^19937-1
number of elements in each.


That's kind of what I thought. It seems fairly limited.
However, I just realised the Mersenne Twister c code
provided by it's inventors allows for longer seeds.

"Those who need initial seed with more than 32-bit
length may use init_by_array() for initialization which
admits an array of arbitrary length as seeds"

I guess you could use an array seeded with the time,
the process ID, and some compressed info from
/dev/random or /dev/audio. Still I imagine it would
still be very difficult to guarantee starting points
distibuted uniformly around the ring of numbers?

<OT>
If you have /dev/random, why would you bother with the time, the
process ID, or /dev/audio?

For that matter, if you have /dev/random, it's not entirely clear you
need to bother with a Mersenne Twister (but the question is beyond my
expertise).
</OT>


<OT>

A reproducible seed (and a subsequent reproducible
sequence) can be of value. Consider testing a module by
throwing pseudo-random data at it; when a failure turns
up you'd like to be able to regenerate the exact same data
as part of verifying your fix.

For the second matter, data rate is generally the issue.
It takes a significant amount of time for a physical source
to generate random data and pass it through assorted bias-
removing filters. If you try to read a zillion random numbers
from such a source, you may need to wait quite a while. It's
more common to use /dev/random or whatever to concoct a "truly
random" seed for a deterministic pseudo-random generator that
can generate subsequent numbers at computer speeds. For even
less predictability, the "truly random" source can also be
used to perturb the deterministic generator now and then.

Oddly enough, D.H. Lehmer used something very like this
perturbation technique in his original (and oft-criticized)
linear congruential generator. According to Knuth:

It is not fair to blame Lehmer for using a "bad"
random-number generator in 1948, since his actual
use of the generator was quite valid. The ENIAC
computer was a highly parallel machine, programmed
by means of a plugboard; Lehmer set it up so that
one of its accumulators was repeatedly multiplying
its own contents by 23, mod 10^8+1, yielding a new
value every few microseconds. Since this multiplier
23 is too small, we know that each value obtained
by this process was too strongly related to the
preceding value to be considered sufficiently random;
but the durations of time between actual uses of the
values in the special accumulator by the accompanying
program were comparatively long and subject to some
fluctuation. So the effective multiplier was 23^k
for large, varying values of k!

-- "The Art of Computer Programming, Volume II:
Seminumerical Algorithms," section 3.3.1

Similar techniques can be found nowadays in games, where
it is common to generate and discard a pseudo-random value
each time the program polls its input devices; the eventual
sequence used in the main part of the program thus depends in
part on the delays in keystroke, mouse, or joystick timings,
generally considered unpredictable if not downright twitchy.

</OT>

--
Er*********@sun .com

May 15 '06 #8
In article <11************ **********@j73g 2000cwa.googleg roups.com> po*********@yah oo.com writes:
(BTW, /dev/random may or may not be "random enough"
compared to the MT, but it more than likely is not fast
enough, since the disk must be accessed).
No, /dev/random does *not* imply disk access. It is a pseudo device,
just like /dev/zero. The random numbers are generated within the
kernel, but I can find no place where it is stated how. It appears
that most systems that implement it use statistics from kernel
interrupts or whatever to get the information. In general it is
cryptographical ly secure (which MT is not), but there is no way to
ascertain whether it complies to standard randomness tests.

So regarding your earlier question: Does Windows have an Entropy Pool like
/dev/random that can be accessed by C.


/dev/random does not come from an "entropy pool", it just generates
random numbers within the kernel.

When you need various subsequent random numbers /dev/random is a
very bad idea. It appears to be good to generate just a single
random number. When you need more, you can use the output as a
seed for a standard random number generator (e.g. MT).

When you are so bothered about the randomness of your numbers, you
really should study the way the generators work. When you do that
you will also appreciate that there are no generators that cover
all possibilities.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
May 16 '06 #9
> No, /dev/random does *not* imply disk access. It is a pseudo device,
just like /dev/zero.
Thanks, I didn't know that....
When you need various subsequent random numbers /dev/random is a
very bad idea. It appears to be good to generate just a single
random number. When you need more, you can use the output as a
seed for a standard random number generator (e.g. MT).


....whereas I am well aware of this. I will certainly be sticking to the
Mersenne Twister for random sequence generation. My itch is random
seeding, and I want to scratch it in a safe way.

With a 32 bit seed, I will only ever generate 4 billion different
sequences, which I think emasculates the MT. By allowing
seeding by an arbitrary array of 32-bit numbers in their c-code,
the inventors have overcome this limitation, but I still need to
generate this array of 32-bit numbers in a way that is unpredictable,
and which works on all platforms.

<time.h> tools certainly work on all platforms of interest to me
(MAC, M$ & *NIX), but I am looking for one or two other orthogonal
seeds, to fill my array (hence the query about /dev/random and
PID).

May 16 '06 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

3
7366
by: Joe | last post by:
Hi, I have been working on some code that requires a high use of random numbers within. Mostly I either have to either: 1) flip a coin i.e. 0 or 1, or 2) generate a double between 0 and 1. I have utilised the following random number source code http://www.agner.org/random/ What I have found is that there is a problem with seeding. The...
25
2950
by: JNY | last post by:
I am using random to generate random numbers, thus: int x,y; for (y = 0;y < 5;y++) { x = random(50); cout << x; }
4
2689
by: Jack | last post by:
I have two files: sort_comparison.c++ my_sort.h sort_comparison.c++ calls this code in my_sort.h: void my_sort::fillArray(int arr,int n) { // const int random_number_range=1000000;
23
2263
by: Alvin | last post by:
Well, I'm developing a Tetris game in SDL, but when it comes to deciding the next block, I'm stuck. It's random, but when I try something like seeding the randomizer with the time, it won't update as fast as one block can fall, and the next to be determined. Generating different numbers in one spur can work, but people can play Tetris for...
104
5099
by: fieldfallow | last post by:
Hello all, Is there a function in the standard C library which returns a prime number which is also pseudo-random? Assuming there isn't, as it appears from the docs that I have, is there a better way than to fill an array of range 0... RAND_MAX with pre-computed primes and using the output of rand() to index into it to extract a random...
6
5897
by: Intiha | last post by:
Hello all, I am trying to generate random seeds for my simulations. currently i was using srand(time(NULL); for this purpose. But for confidence in my results i ran it using a script in a loop. Since the time b/w execution is very similar, many simulation runs resulted in exact same results. Is there a better way of seeding the random...
11
3587
by: Kevin Williamson | last post by:
Hi, I've written a lottery programme in PHP that selects 10 winners a week from approximately 18,000 shares. The problem I have is that of the ten winners one week the same share number was drawn the next week and an adjacent share number the following week (that just happened to be owned by the same member) The program is now being...
2
3630
by: HumanJHawkins | last post by:
I wrote this question a little differently in the MFC group since it is a bit of a different environment than pure C++, but I hope you will forgive the similarities if anyone is reading both groups. Basically, I need to seed the random number generator in 4 seperate threads at once. So, I can't use the current time as the random seed,...
8
3902
by: Daniel | last post by:
Hey guys Using Random(), how random is it, is it possible to be predicted? I have a requirement for a very good random number generator. I was doing something such as: Random randomSeed = new Random((int)_seedTimer.ElapsedTicks); _random = new Random(randomSeed.Next(0,99999999)); return random.Next(min, max);
0
7978
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. ...
1
7730
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
0
8028
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
0
6349
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
1
5550
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
0
3692
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
0
3688
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
2164
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
0
987
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.