Re: BBC BASIC's RND Function
 From: Martin Wuerthner <spamtrap@xxxxxxxxxxxxxxx>
 Date: Mon, 15 Oct 2007 23:18:52 +0200
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 bruteforce 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 32bit 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.mwsoftware.com/
ArtWorks 2  Designing stunning graphics has never been easier
spamtrap@xxxxxxxxxxxxxxx [replace "spamtrap" by "info" to reply]
.
 FollowUps:
 Re: BBC BASIC's RND Function
 From: Nick Roberts
 Re: BBC BASIC's RND Function
 References:
 BBC BASIC's RND Function
 From: Michael Emerton
 Re: BBC BASIC's RND Function
 From: VinceH
 Re: BBC BASIC's RND Function
 From: Michael Emerton
 Re: BBC BASIC's RND Function
 From: Ste (news)
 Re: BBC BASIC's RND Function
 From: Richard Russell
 Re: BBC BASIC's RND Function
 From: Rob Kendrick
 Re: BBC BASIC's RND Function
 From: Ste (news)
 Re: BBC BASIC's RND Function
 From: Richard Russell
 Re: BBC BASIC's RND Function
 From: Ste (news)
 Re: BBC BASIC's RND Function
 From: Theo Markettos
 Re: BBC BASIC's RND Function
 From: Nick Roberts
 BBC BASIC's RND Function
 Prev by Date: Re: BBC BASIC's RND Function
 Next by Date: Re: BBC BASIC's RND Function
 Previous by thread: Re: BBC BASIC's RND Function
 Next by thread: Re: BBC BASIC's RND Function
 Index(es):
Relevant Pages
