# 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 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]

.

**Follow-Ups**:**Re: BBC BASIC's RND Function***From:*Nick Roberts

**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

- 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):