user
A *subtractive generator* calculates a sequence of random numbers, where each number is congruent to the subtraction of two previous numbers from the sequence.   
The formula is

* r

  n
  =

  r

  (
  n
  −
  i
  )
  −

  r

  (
  n
  −
  j
  )


  (
  mod

  m
  )
  {\displaystyle {\displaystyle r\_{n}=r\_{(n-i)}-r\_{(n-j)}{\pmod {m}}}}

for some fixed values of 

i
{\displaystyle {\displaystyle i}}
, 

j
{\displaystyle {\displaystyle j}}
 and 

m
{\displaystyle {\displaystyle m}}
, all positive integers. Supposing that 

i
>
j
{\displaystyle {\displaystyle i>j}}
, then the state of this generator is the list of the previous numbers from 

r

n
−
i
{\displaystyle {\displaystyle r\_{n-i}}}
 to 

r

n
−
1
{\displaystyle {\displaystyle r\_{n-1}}}
. Many states generate uniform random integers from 

0
{\displaystyle {\displaystyle 0}}
 to 

m
−
1
{\displaystyle {\displaystyle m-1}}
, but some states are bad. A state, filled with zeros, generates only zeros. If 

m
{\displaystyle {\displaystyle m}}
 is even, then a state, filled with even numbers, generates only even numbers. More generally, if 

f
{\displaystyle {\displaystyle f}}
 is a factor of 

m
{\displaystyle {\displaystyle m}}
, then a state, filled with multiples of 

f
{\displaystyle {\displaystyle f}}
, generates only multiples of 

f
{\displaystyle {\displaystyle f}}
.

All subtractive generators have some weaknesses. The formula correlates 

r

n
{\displaystyle {\displaystyle r\_{n}}}
, 

r

(
n
−
i
)
{\displaystyle {\displaystyle r\_{(n-i)}}}
 and 

r

(
n
−
j
)
{\displaystyle {\displaystyle r\_{(n-j)}}}
; these three numbers are not independent, as true random numbers would be. Anyone who observes 

i
{\displaystyle {\displaystyle i}}
 consecutive numbers can predict the next numbers, so the generator is not cryptographically secure. The authors of *Freeciv* (utility/rand.c) and *xpat2* (src/testit2.c) knew another problem: the low bits are less random than the high bits.

The subtractive generator has a better reputation than the linear congruential generator, perhaps because it holds more state. A subtractive generator might never multiply numbers: this helps where multiplication is slow. A subtractive generator might also avoid division: the value of 

r

(
n
−
i
)
−

r

(
n
−
j
)
{\displaystyle {\displaystyle r\_{(n-i)}-r\_{(n-j)}}}
 is always between 

−
m
{\displaystyle {\displaystyle -m}}
 and 

m
{\displaystyle {\displaystyle m}}
, so a program only needs to add 

m
{\displaystyle {\displaystyle m}}
 to negative numbers.

The choice of 

i
{\displaystyle {\displaystyle i}}
 and 

j
{\displaystyle {\displaystyle j}}
 affects the period of the generator. A popular choice is 

i
=
55
{\displaystyle {\displaystyle i=55}}
 and 

j
=
24
{\displaystyle {\displaystyle j=24}}
, so the formula is

* r

  n
  =

  r

  (
  n
  −
  55
  )
  −

  r

  (
  n
  −
  24
  )


  (
  mod

  m
  )
  {\displaystyle {\displaystyle r\_{n}=r\_{(n-55)}-r\_{(n-24)}{\pmod {m}}}}

The subtractive generator from *xpat2* uses

* r

  n
  =

  r

  (
  n
  −
  55
  )
  −

  r

  (
  n
  −
  24
  )


  (
  mod


  10

  9
  )
  {\displaystyle {\displaystyle r\_{n}=r\_{(n-55)}-r\_{(n-24)}{\pmod {10^{9}}}}}

The implementation is by J. Bentley and comes from program\_tools/universal.c of the DIMACS (netflow) archive at Rutgers University. It credits Knuth, TAOCP, Volume 2, Section 3.2.2 (Algorithm A).

Bentley uses this clever algorithm to seed the generator.

1. Start with a single 

   s
   e
   e
   d
   {\displaystyle {\displaystyle seed}}
    in range 

   0
   {\displaystyle {\displaystyle 0}}
    to 

   10

   9
   −
   1
   {\displaystyle {\displaystyle 10^{9}-1}}
   .
2. Set 

   s

   0
   =
   s
   e
   e
   d
   {\displaystyle {\displaystyle s\_{0}=seed}}
    and 

   s

   1
   =
   1
   {\displaystyle {\displaystyle s\_{1}=1}}
   . The inclusion of 

   s

   1
   =
   1
   {\displaystyle {\displaystyle s\_{1}=1}}
    avoids some bad states (like all zeros, or all multiples of 10).
3. Compute 

   s

   2
   ,

   s

   3
   ,
   .
   .
   .
   ,

   s

   54
   {\displaystyle {\displaystyle s\_{2},s\_{3},...,s\_{54}}}
    using the subtractive formula 

   s

   n
   =

   s

   (
   n
   −
   2
   )
   −

   s

   (
   n
   −
   1
   )


   (
   mod


   10

   9
   )
   {\displaystyle {\displaystyle s\_{n}=s\_{(n-2)}-s\_{(n-1)}{\pmod {10^{9}}}}}
   .
4. Reorder these 55 values so 

   r

   0
   =

   s

   34
   {\displaystyle {\displaystyle r\_{0}=s\_{34}}}
   , 

   r

   1
   =

   s

   13
   {\displaystyle {\displaystyle r\_{1}=s\_{13}}}
   , 

   r

   2
   =

   s

   47
   {\displaystyle {\displaystyle r\_{2}=s\_{47}}}
   , ..., 

   r

   n
   =

   s

   (
   34
   ∗
   (
   n
   +
   1
   )


   (
   mod

   55
   )
   )
   {\displaystyle {\displaystyle r\_{n}=s\_{(34\*(n+1){\pmod {55}})}}}
   .
   * This is the same order as 

     s

     0
     =

     r

     54
     {\displaystyle {\displaystyle s\_{0}=r\_{54}}}
     , 

     s

     1
     =

     r

     33
     {\displaystyle {\displaystyle s\_{1}=r\_{33}}}
     , 

     s

     2
     =

     r

     12
     {\displaystyle {\displaystyle s\_{2}=r\_{12}}}
     , ..., 

     s

     n
     =

     r

     (
     (
     34
     ∗
     n
     )
     −
     1


     (
     mod

     55
     )
     )
     {\displaystyle {\displaystyle s\_{n}=r\_{((34\*n)-1{\pmod {55}})}}}
     .
   * This rearrangement exploits how 34 and 55 are relatively prime.
5. Compute the next 165 values 

   r

   55
   {\displaystyle {\displaystyle r\_{55}}}
    to 

   r

   219
   {\displaystyle {\displaystyle r\_{219}}}
   . Store the last 55 values.

This generator yields the sequence 

r

220
{\displaystyle {\displaystyle r\_{220}}}
, 

r

221
{\displaystyle {\displaystyle r\_{221}}}
, 

r

222
{\displaystyle {\displaystyle r\_{222}}}
 and so on. For example, if the seed is 292929, then the sequence begins with 

r

220
=
467478574
{\displaystyle {\displaystyle r\_{220}=467478574}}
, 

r

221
=
512932792
{\displaystyle {\displaystyle r\_{221}=512932792}}
, 

r

222
=
539453717
{\displaystyle {\displaystyle r\_{222}=539453717}}
. By starting at 

r

220
{\displaystyle {\displaystyle r\_{220}}}
, this generator avoids a bias from the first numbers of the sequence. This generator must store the last 55 numbers of the sequence, so to compute the next 

r

n
{\displaystyle {\displaystyle r\_{n}}}
. Any array or list would work; a ring buffer is ideal but not necessary.

Implement a subtractive generator that replicates the sequences from *xpat2*.
assistant
(formerly Perl 6)

**Translation of**: Perl

**Works with**: Rakudo version 2018.03

```
sub bentley-clever($seed) {
    constant $mod = 1_000_000_000;
    my @seeds = ($seed % $mod, 1, (* - *) % $mod ... *)[^55];
    my @state = @seeds[ 34, (* + 34 ) % 55 ... 0 ];

    sub subrand() {
        push @state, (my $x = (@state.shift - @state[*-24]) % $mod);
        $x;
    }

    subrand for 55 .. 219;

    &subrand ... *;
}

my @sr = bentley-clever(292929);
.say for @sr[^10];

```

Here we just make the seeder return the random sequence as a lazy list.

Output:

```
467478574
512932792
539453717
20349702
615542081
378707948
933204586
824858649
506003769
380969305
```