Re: BBC BASIC's RND Function



In message <a96349324f.tigger@xxxxxxxxxxxxxxxxxxxxxxxxxx>
Nick Roberts <tigger@xxxxxxxxxxxxxxxxxxxxx> wrote:

In message <yGt*rUjXr@xxxxxxxxxxxxxxxxxxxxxxxxxxx>
Theo Markettos <theom+news@xxxxxxxxxxxxxxxxxxxxxx> wrote:

Seeding the random number generator is a good way to produce longer
sequences, but remember the entropy in the system is still the 32 bit
random seed. If you're using this to generate crypto keys, for
example, that means you only have 2^32 possible keys because you only
have 2^32 seeds (and the rest of the process is deterministic) - and
a 32 bit key is trivial to brute-force these days. Hence the need
for more entropy in the system.

One thing that has been missed in this thread is the purpose for which
the stream is needed.

Not at all, we have been discussing the all important task of
shuffling cards, which turned out to be surprisingly difficult. :-)

If the only requirement is a much longer cycle length than RND (while
retaining the ability to guarantee repeatability by seeding it), then
it shouldn't take much ingenuity to implement a BASIC version of the
Mersenne Twister (cycle length 2^19937 - 1), which is pretty fast[1]
for a generator of such cycle length.

The standard implementation of MT 19937 has a 32-bit seed, so we are
back to a maximum of 2^32 different arrangements of the cards, no
matter how big the cycle length is. :-( In fact, the cycle length is
not really that important for this particular application. It is
important in that it limits the starting entropy because you cannot
have more different seed values than the length of the cycle. Unless
you have at least 226 bits of entropy to start with (i.e., in the
seed) it is impossible to achieve all permutations of a pack of 52
cards.

It should be possible to create MTs with larger word lengths but then,
I suppose that speed will suffer.

Martin
--
---------------------------------------------------------------------
Martin Wuerthner MW Software http://www.mw-software.com/
ArtWorks 2 -- Designing stunning graphics has never been easier
spamtrap@xxxxxxxxxxxxxxx [replace "spamtrap" by "info" to reply]
.