Fibonacci generators

Next: We can generate a Up: Generation of Random Numbers Previous: where bs are only Contents

Fibonacci generators

The prescription described in the last section of constructing a lagged sequence can be done modulo m > 2 e.g. taking the pth and qth preceding numbers with, say, p>q, and combining them, mod m, according to some operation

$\nu _{i}=(\nu _{i-q}$ $\odot$ $\nu _{i-p})$ mod m

Subsections

We can generate a sequence of numbers, given that the first p numbers are provided e.g. from a multiplicative congruential generator. The operation denoted by $\odot$ is conventionally the `exclusive-or'. It may be however just simple addition or subtraction, and recent studies favour the latter operation, giving rise to a subtracted Fibonacci generator.And especially interesting development is the subtract-with-borrow generator of this type. The algorithm is
The `carry' coefficient, $\beta \protect$ , which must be set to 0 or 1, arbitrarily, at initialization, is reassigned in each call as follows; if the quantity in brackets is negative, so that m must be added to it to carry out the modulo m operation, $\beta \protect$ is set to zero otherwise it assumes the value unity. If m, p, and q satisfy certain conditions, the period of this generator is m $^{p}\protect$ -m $^{q}\protect$ .

Amaury LATAILLADE 2002-11-04