Notes from the Field:
Care is Needed when (Re)Seeding "tt800."

by Jeff Szuhay, Psychology Software Tools, Inc.
August 9, 2000

This "field report" is intended to serve as an implementor's precaution when using "tt880." When we were investigating and ultimately choosing a PRNG for our product, we found only hints of using an LCG to (re)seed an FSR. This field note is intended to give emphasis to the potential pitfall of not paying attention to the (re)seeding algorithm.

Contact Jeff Szuhay, <mailto:jeff.szuhay@pstnet.com> for related documents, comments, and questions.

At the outset it should be noted that this field report pertains the initialization of "tt800" and a problem we encountered when our too-simple initialization routine was used in an unexpected way. "tt800" itself is not in question.

Quick Table of Contents

Some New Considerations

We at Psychology Sotfware Tools < http://www.pstnet.com> chose to implement the Pseudo Random Number Generator (PRNG) "tt800" [2] in our experimentation product E-Prime. "tt800" is from a class of PRNGs known as "twisted feedback shift register" (tFSR). "tt800" was chosen because of its very long sequence of reliably proven random numbers (~10^240).

The implementation of this PRNG involves 800 bits that are manipulated each time a random number is requested. Seeding "tt800" involves manipulating these 800 bits from a default state to one that is modified by the given seed [2]. The Randomize function is used to do this initialization.

Particular care should be taken when implementing the initialization function.

An FSR is a bit more complicated than the popular class of Linear Congruent Generators (LCGs) which only depend upon a given number to generate the next number in their sequence. These have been shown to fail in their patterns of randomness and were thus discarded for consideration [1] in E-Prime. Nevertheless, LCGs have been widely implemented and used, despite their shortcomings.

One benefit of LCGs is their simple use. Given a seed (or a single value in the PRNGs sequence), generate the next random number. This number is then used to generate the next one, and so on.

It was this very manner of usage that we overlooked in implementing "tt800" in E-Prime. It should be noted that it is not "tt800" itself that is in question here, it is how the PRNG is applied in a specific psychological experiment.

The Problem

One researcher wished to have many trial blocks each with a repeatable "random" sequence. The researcher used Randomize at the start of each trial block with seed values they thought were significantly different and further asked for a relatively narrow range within the target random number set

The observed behavior was that for various seed values, for example, 197 and 301, the exact same sequence of numbers was produced. This clearly was not an acceptable outcome for our PRNG.

In implementing "tt800," we had not expected it to be used in this manner. In fact, we had expected it to be reseed seldom, if at all, in an experiment.

To illustrate this problem, a table of 4 sequences of random numbers is presented in Table 1 each with a delta h seed value of 1 and a target number set between 1 and 10. A seed value of 0 represents the default bit pattern given with the "tt800" code [2].

Table 1 demonstrates 4 identical sequences; an obvious failure in the application of "tt800" when initialized with seed values which are very close.

seed:

0

1

2

3

1:

8

8

8

8

2:

7

7

7

7

3:

1

1

1

1

4:

5

5

5

5

5:

6

6

6

6

6:

10

10

10

10

7:

1

1

1

1

8:

2

2

2

2

9:

1

1

1

1

10:

5

5

5

5

11:

10

10

10

10

12:

9

9

9

9

13:

8

8

8

8

14:

4

4

4

4

15:

1

1

1

1

16:

9

9

9

9

17:

1

1

1

1

18:

2

2

2

2

19:

2

2

2

2

20:

1

1

1

1

21:

4

4

4

4

22:

4

4

4

4

23:

2

2

2

2

24:

4

4

4

4

25:

10

10

10

10

Table 1. 4 sequences using simple XOR in Randomize function

The Cause

Careful examination revealed that the problem was caused, not by "tt800," but by its initialization function, Randomize. It turns out that Randomize was poorly implemented leading to catastrophic failure in this specific application of the PRING.

Internally, the 800 bits of "tt800" are represented as an array of 25 unsigned integer keys (32 bits each). The initialization routine applied a simple XOR operator on the seed and each of the 25 keys. Consequently, this did not produce a starting key state that was significantly different from the default key state. For example, both 197 and 301 involve only 8 bits of each 32-bit key. And their bit patterns are similar enough that only 5 low order bits will be different. Applying XOR to each key may then yield no more than a 5 bit difference for each key but more likely only 1 or 2 low order bits will be different. From this we conclude that the simple use of the XOR with the key and seed is inadequate.

In addition, small differences in the generated numbers were further removed due to the relatively narrow target number set (between 100 and 500).

Clearly, this is an important aspect of psychological experimentation. Trial blocks may be run in a different order from subject to subject. However, the experimenter may want to have a given sequence for a given trial block regardless of when it appears to the subject. It is this special case that we omitted from our functional requirements when implementing and testing "tt800."

"tt800" without repeated use of the "Randomize" function would indeed produce an extremely random sequence but would omit one aspect of the researcher's needs -- repeatable, random sequences within a trial block regardless of when it occurs in an experiment.

The focus of the solution to this problem turned to the Randomize function itself.

"tt800" Revisited

To eliminate this special-case deficiency an initialization routine was needed which itself generated a sequence of very wide numbers from a given seed. Furthermore, for even small increments in the seed (delta h=1) it should produce a significantly different sequence.

For this, we turned to Marsaglia's "Super Duper" LCG [3] which is a part of the "McGill Random Number Package" designed to be used in conjunction with a different shift register generator in that package. It should be noted in [1], above, that this LCG fails standard randomness tests when used in isolation. But as a part of "tt800's" initialization, it performs quite well.

To illustrate this solution, a table of 4 sequences of random numbers is presented in Table 2 each with a delta h seed value of 1 and a target number set between 1 and 10.

seed:

0

1

2

3

1:

8

3

3

2

2:

7

10

8

4

3:

1

9

8

10

4:

5

3

10

8

5:

6

5

5

5

6:

10

4

10

9

7:

1

6

2

10

8:

2

8

9

2

9:

1

2

2

5

10:

5

9

5

4

11:

10

1

3

2

12:

9

2

7

2

13:

8

8

10

8

14:

4

9

8

8

15:

1

1

6

8

16:

9

10

5

4

17:

1

9

2

3

18:

2

7

10

5

19:

2

6

3

10

20:

1

5

9

3

21:

4

3

7

4

22:

4

8

7

5

23:

2

4

3

9

24:

4

3

4

1

25:

10

1

7

4

Table 2. 4 sequences using Super Duper LCG in Randomize function

As can be seen from a rapid visual inspection of Table 2, the sequences show a marked improvement over those given in Table 1.

Implementation details and source code are available upon request.


[1] see A collection of selected pseudorandom number generators with linear structures by Karl Entacher, January 13, 1998, for a graphic display of the deficiencies of this class of generator. < http://random.mat.sbg.ac.at/~charly/server/server.html>

[2] "tt800" source code, available from < http://random.mat.sbg.ac.at/ftp/pub/data/tt800.c>.

[3] Marsaglia's "Super Duper" source code, available from < http://www.prismtk.de/docs/ccref/test/stdc/rand2-c.txt>.