Rosetta Code

Subtractive generator: Difference between revisions

Page Discussion

Subtractive generator (view source)

Revision as of 16:52, 10 February 2024

26,807 bytes added ,  3 months ago
m
→‎{{header|Wren}}: Changed to Wren S/H
(Added F# version)
m (→‎{{header|Wren}}: Changed to Wren S/H)
 
(42 intermediate revisions by 19 users not shown)
Line 1:
{{task|Randomness}}
 
A ''subtractive generator'' calculates a sequence of [[random number generator|random numbers]], where each number is congruent to the subtraction of two previous numbers from the sequence. <br>
The formula is
 
* <big><math>r_n = r_{(n - i)} - r_{(n - j)} \pmod m</math></big>
 
for some fixed values of <big><math>i</math></big>, <big><math>j</math></big> and <big><math>m</math></big>, all positive integers. Supposing that <big><math>i > j</math></big>, then the state of this generator is the list of the previous numbers from <big><math>r_{n - i}</math></big> to <big><math>r_{n - 1}</math></big>. Many states generate uniform random integers from <big><math>0</math></big> to <big><math>m - 1</math></big>, but some states are bad. A state, filled with zeros, generates only zeros. If <big><math>m</math></big> is even, then a state, filled with even numbers, generates only even numbers. More generally, if <big><math>f</math></big> is a factor of <big><math>m</math></big>, then a state, filled with multiples of <big><math>f</math></big>, generates only multiples of <big><math>f</math></big>.
 
All subtractive generators have some weaknesses. The formula correlates <big><math>r_n</math></big>, <big><math>r_{(n - i)}</math></big> and <big><math>r_{(n - j)}</math></big>; these three numbers are not independent, as true random numbers would be. Anyone who observes <big><math>i</math></big> consecutive numbers can predict the next numbers, so the generator is not cryptographically secure. The authors of ''Freeciv'' ([http://svn.gna.org/viewcvs/freeciv/trunk/utility/rand.c?view=markup 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 <big><math>r_{(n - i)} - r_{(n - j)}</math></big> is always between <big><math>-m</math></big> and <big><math>m</math></big>, so a program only needs to add <big><math>m</math></big> to negative numbers.
 
The choice of <big><math>i</math></big> and <big><math>j</math></big> affects the period of the generator. A popular choice is <big><math>i = 55</math></big> and <big><math>j = 24</math></big>, so the formula is
 
* <big><math>r_n = r_{(n - 55)} - r_{(n - 24)} \pmod m</math></big>
 
The subtractive generator from ''xpat2'' uses
 
* <big><math>r_n = r_{(n - 55)} - r_{(n - 24)} \pmod{10^9}</math></big>
 
The implementation is by J. Bentley and comes from program_tools/universal.c of [ftp://dimacs.rutgers.edu/pub/netflow/ the DIMACS (netflow) archive] at Rutgers University. It credits Knuth, [[wp:The Art of Computer Programming|''TAOCP'']], Volume 2, Section 3.2.2 (Algorithm A).
Line 23 ⟶ 24:
Bentley uses this clever algorithm to seed the generator.
 
# Start with a single <big><math>seed</math></big> in range <big><math>0</math></big> to <big><math>10^9 - 1</math></big>.
# Set <big><math>s_0 = seed</math></big> and <big><math>s_1 = 1</math></big>. The inclusion of <big><math>s_1 = 1</math></big> avoids some bad states (like all zeros, or all multiples of 10).
# Compute <big><math>s_2, s_3, ..., s_{54}</math></big> using the subtractive formula <big><math>s_n = s_{(n - 2)} - s_{(n - 1)} \pmod{10^9}</math></big>.
# Reorder these 55 values so <big><math>r_0 = s_{34}</math></big>, <big><math>r_1 = s_{13}</math></big>, <big><math>r_2 = s_{47}</math></big>, ..., <big><math>r_n = s_{(34 * (n + 1) \pmod{55})}</math></big>.
#* This is the same order as <big><math>s_0 = r_{54}</math></big>, <big><math>s_1 = r_{33}</math></big>, <big><math>s_2 = r_{12}</math></big>, ..., <big><math>s_n = r_{((34 * n) - 1 \pmod{55})}</math></big>.
#* This rearrangement exploits how 34 and 55 are relatively prime.
# Compute the next 165 values <big><math>r_{55}</math></big> to <big><math>r_{219}</math></big>. Store the last 55 values.
 
This generator yields the sequence <big><math>r_{220}</math></big>, <big><math>r_{221}</math></big>, <big><math>r_{222}</math></big> and so on. For example, if the seed is 292929, then the sequence begins with <big><math>r_{220} = 467478574</math></big>, <big><math>r_{221} = 512932792</math></big>, <big><math>r_{222} = 539453717</math></big>. By starting at <big><math>r_{220}</math></big>, 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 <big><math>r_n</math></big>. Any array or list would work; a [[ring buffer]] is ideal but not necessary.
 
Implement a subtractive generator that replicates the sequences from ''xpat2''.
<br><br>
 
=={{header|11l}}==
{{trans|Python: With explanation}}
 
<syntaxhighlight lang="11l">Deque[Int] s
V seed = 292929
 
s.append(seed)
s.append(1)
 
L(n) 2..54
s.append((s[n - 2] - s[n - 1]) % 10 ^ 9)
 
Deque[Int] r
L(n) 55
V i = (34 * (n + 1)) % 55
r.append(s[i])
 
F py_mod(a, b)
R ((a % b) + b) % b
 
F getnextr()
:r.append(py_mod((:r[0] - :r[31]), 10 ^ 9))
:r.pop_left()
R :r[54]
 
L 0 .< 219 - 54
getnextr()
 
L 5
print(‘result = ’getnextr())</syntaxhighlight>
 
{{out}}
<pre>
result = 467478574
result = 512932792
result = 539453717
result = 20349702
result = 615542081
</pre>
 
=={{header|Ada}}==
 
subtractive_generator.ads:
<langsyntaxhighlight Adalang="ada">package Subtractive_Generator is
type State is private;
procedure Initialize (Generator : in out State; Seed : Natural);
Line 48 ⟶ 90:
Last : Natural;
end record;
end Subtractive_Generator;</langsyntaxhighlight>
 
subtractive_generator.adb:
<langsyntaxhighlight Adalang="ada">package body Subtractive_Generator is
 
procedure Initialize (Generator : in out State; Seed : Natural) is
Line 83 ⟶ 125:
end Next;
 
end Subtractive_Generator;</langsyntaxhighlight>
 
Example main.adb:
<langsyntaxhighlight Adalang="ada">with Ada.Text_IO;
with Subtractive_Generator;
 
Line 99 ⟶ 141:
Ada.Text_IO.Put_Line (Integer'Image (I) & ":" & Integer'Image (N));
end loop;
end Main;</langsyntaxhighlight>
 
{{out}}
Line 108 ⟶ 150:
=={{header|AutoHotkey}}==
{{works with|AutoHotkey_L}}
<langsyntaxhighlight AutoHotkeylang="autohotkey">r := InitR(292929)
 
Loop, 10
Line 132 ⟶ 174:
, r[i] := Mod(r[i] - r[Mod(A_Index + 30, 55)], r["m"])
return, r
}</langsyntaxhighlight>
{{out}}
<pre>220: 467478574
Line 145 ⟶ 187:
229: 380969305</pre>
 
=={{header|BBC BASIC}}==
==={{header|BBC BASIC}}===
{{works with|BBC BASIC for Windows}}
<langsyntaxhighlight lang="bbcbasic"> dummy% = FNsubrand(292929)
FOR i% = 1 TO 10
PRINT FNsubrand(0)
Line 172 ⟶ 215:
IF FNsubrand(0)
NEXT
= 0</langsyntaxhighlight>
{{out}}
<pre>
Line 185 ⟶ 228:
506003769
380969305
</pre>
 
==={{header|FreeBASIC}}===
{{trans|Kotlin}}
<syntaxhighlight lang="vb">Const As Integer mod_ = 1e9
Dim Shared As Integer state(0 To 55)
Dim Shared As Integer sk = 0, sj = 0
 
Declare Function subrand() As Integer
 
Sub subrandSeed (p1 As Integer)
Dim As Integer i, j, p2
state(0) = p1 Mod mod_
p2 = 1
j = 21
For i = 1 To 54
If j >= 55 Then j -= 55
state(j) = p2
p2 = p1 - p2
If p2 < 0 Then p2 += mod_
p1 = state(j)
j += 21
Next
sk = 0
sj = 24
For i = 1 To 165
subrand()
Next
End Sub
 
Function subrand() As Integer
If sk = sj Then
subrandSeed(0)
Else
If sk = 0 Then sk = 54 Else sk -= 1
If sj = 0 Then sj = 54 Else sj -= 1
Dim As Integer x = state(sk) - state(sj)
If x < 0 Then x += mod_
state(sk) = x
Return x
End If
End Function
 
subrandSeed(292929)
For i As Integer = 0 To 9
Print Using "r[###] = &"; i+220; subrand()
Next i
 
Sleep</syntaxhighlight>
{{out}}
<pre>Same as Kotlin entry</pre>
 
==={{header|Gambas}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="vbnet">Public mod_ As Integer = 1e9
Public state[55] As Integer
Public sk As Integer = 0
Public sj As Integer = 0
 
Public Sub Main()
subrandSeed(292929)
For i As Integer = 0 To 9
Print "r["; i + 220; "] = "; subrand()
Next
End
 
Sub subrandSeed(p1 As Integer)
 
Dim i As Integer
Dim p2 As Integer = 1
Dim j As Integer = 21
 
state[0] = p1 Mod mod_
For i = 1 To 54
If j >= 55 Then j -= 55
state[j] = p2
p2 = p1 - p2
If p2 < 0 Then p2 += mod_
p1 = state[j]
j += 21
Next
sk = 0
sj = 24
For i = 1 To 165
subrand()
Next
 
End Sub
 
Function subrand() As Integer
If sk = sj Then
subrandSeed(0)
Else
If sk = 0 Then sk = 54 Else sk -= 1
If sj = 0 Then sj = 54 Else sj -= 1
Dim x As Integer = state[sk] - state[sj]
If x < 0 Then x += mod_
state[sk] = x
Return x
End If
 
End Function</syntaxhighlight>
 
==={{header|uBasic/4tH}}===
<syntaxhighlight lang="text">Push 292929 : Gosub 100 : d = Pop()
 
For i = 1 To 10
Push 0 : Gosub 100
Print Pop()
Next
 
End
 
100 s = Pop()
If s = 0 Then
p = (p + 1) % 55
@(p) = @(p) - @((p + 31) % 55)
If @(p) < 0 Then
@(p) = @(p) + 1000000000
Endif
Push (@(p)) : Return
Endif
 
@(54) = s : @(33) = 1
p = 12
 
For i = 2 To 54
@(p) = @((p + 42) % 55) - @((p + 21) % 55)
If @(p) < 0 Then
@(p) = @(p) + 1000000000
Endif
p = (p + 34) % 55
Next
 
For i = 55 To 219
Push 0 : Gosub 100 : d = Pop()
Next
 
Push 0 : Return</syntaxhighlight>
{{out}}
<pre>467478574
512932792
539453717
20349702
615542081
378707948
933204586
824858649
506003769
380969305
 
0 OK, 0:864
</pre>
 
Line 190 ⟶ 390:
This is a translation of the C example.
 
<langsyntaxhighlight lang="bracmat">1000000000:?MOD;
tbl$(state,55);
0:?si:?sj;
Line 241 ⟶ 441:
));
 
Main$;</langsyntaxhighlight>
 
{{out}}
Line 257 ⟶ 457:
=={{header|C}}==
This is basically the same as the reference C code, only differs in that it's C89.
<langsyntaxhighlight lang="c">#include<stdio.h>
 
#define MOD 1000000000
Line 299 ⟶ 499:
 
return 0;
}</langsyntaxhighlight>
 
=={{header|C sharp|C#}}==
<syntaxhighlight lang="csharp">
public class SubtractiveGenerator {
public static int MAX = 1000000000;
private int[] state;
private int pos;
 
private int mod(int n) {
return ((n % MAX) + MAX) % MAX;
}
 
public SubtractiveGenerator(int seed) {
state = new int[55];
 
int[] temp = new int[55];
temp[0] = mod(seed);
temp[1] = 1;
for(int i = 2; i < 55; ++i)
temp[i] = mod(temp[i - 2] - temp[i - 1]);
 
for(int i = 0; i < 55; ++i)
state[i] = temp[(34 * (i + 1)) % 55];
 
pos = 54;
for(int i = 55; i < 220; ++i)
next();
}
 
public int next() {
int temp = mod(state[(pos + 1) % 55] - state[(pos + 32) % 55]);
pos = (pos + 1) % 55;
state[pos] = temp;
return temp;
}
 
static void Main(string[] args) {
SubtractiveGenerator gen = new SubtractiveGenerator(292929);
for(int i = 220; i < 230; ++i)
Console.WriteLine(i.ToString() + ": " + gen.next().ToString());
}
}
</syntaxhighlight>
 
{{out}}
<pre>
220: 467478574
221: 512932792
222: 539453717
223: 20349702
224: 615542081
225: 378707948
226: 933204586
227: 824858649
228: 506003769
229: 380969305
</pre>
 
=={{header|C++}}==
{{libheader|Boost}}
<langsyntaxhighlight lang="cpp">
// written for clarity not efficiency.
 
Line 367 ⟶ 624:
return 0;
}
</syntaxhighlight>
</lang>
 
{{out}}
Line 378 ⟶ 635:
result = 378707948
result = 933204586
</pre>
 
=={{header|C sharp|C#}}==
<lang csharp>
public class SubtractiveGenerator {
public static int MAX = 1000000000;
private int[] state;
private int pos;
 
private int mod(int n) {
return ((n % MAX) + MAX) % MAX;
}
 
public SubtractiveGenerator(int seed) {
state = new int[55];
 
int[] temp = new int[55];
temp[0] = mod(seed);
temp[1] = 1;
for(int i = 2; i < 55; ++i)
temp[i] = mod(temp[i - 2] - temp[i - 1]);
 
for(int i = 0; i < 55; ++i)
state[i] = temp[(34 * (i + 1)) % 55];
 
pos = 54;
for(int i = 55; i < 220; ++i)
next();
}
 
public int next() {
int temp = mod(state[(pos + 1) % 55] - state[(pos + 32) % 55]);
pos = (pos + 1) % 55;
state[pos] = temp;
return temp;
}
 
static void Main(string[] args) {
SubtractiveGenerator gen = new SubtractiveGenerator(292929);
for(int i = 220; i < 230; ++i)
Console.WriteLine(i.ToString() + ": " + gen.next().ToString());
}
}
</lang>
 
{{out}}
<pre>
220: 467478574
221: 512932792
222: 539453717
223: 20349702
224: 615542081
225: 378707948
226: 933204586
227: 824858649
228: 506003769
229: 380969305
</pre>
 
=={{header|Clojure}}==
<langsyntaxhighlight lang="clojure">(defn xpat2-with-seed
"produces an xpat2 function initialized from seed"
[seed]
Line 460 ⟶ 660:
 
(println (xpat2) (xpat2) (xpat2)) ; prints: 467478574 512932792 539453717
</syntaxhighlight>
</lang>
 
=={{header|Common Lisp}}==
<langsyntaxhighlight lang="lisp">(defun sub-rand (state)
(let ((x (last state)) (y (last state 25)))
;; I take "circular buffer" very seriously (until some guru
Line 485 ⟶ 685:
;; test it (output same as everyone else's)
(let ((f (bentley-clever 292929)))
(dotimes (x 10) (format t "~a~%" (funcall f))))</langsyntaxhighlight>
 
=={{header|D}}==
{{trans|C}}
 
<langsyntaxhighlight lang="d">import std.stdio;
 
struct Subtractive {
Line 541 ⟶ 741:
foreach (i; 0 .. 10)
writeln(gen.subrand());
}</langsyntaxhighlight>
{{out}}
<pre>467478574
Line 555 ⟶ 755:
 
=={{header|dc}}==
<langsyntaxhighlight lang="dc">[*
* (seed) lsx --
* Seeds the subtractive generator.
Line 606 ⟶ 806:
lrx psz
lrx psz
lrx psz</langsyntaxhighlight>
 
This program prints 467478574, 512932792, 539453717.
 
This implementation never uses multiplication, but it does use modulus (remainder from division) to put each random number in range from 0 to 10^9 - 1.
 
=={{header|EasyLang}}==
{{trans|C}}
<syntaxhighlight>
MOD = 1000000000
len state[] 55
arrbase state[] 0
global si sj .
funcdecl subrand .
proc subrand_seed p1 . .
p2 = 1
state[0] = p1 mod MOD
j = 21
for i = 1 to 54
state[j] = p2
p2 = (p1 - p2) mod MOD
p1 = state[j]
j = (j + 21) mod 55
.
si = 0
sj = 24
for i = 0 to 164
h = subrand
h = h
.
.
func subrand .
if si = sj
subrand_seed 0
.
si = (si - 1) mod 55
sj = (sj - 1) mod 55
x = (state[si] - state[sj]) mod MOD
state[si] = x
return x
.
subrand_seed 292929
for i to 10
print subrand
.
</syntaxhighlight>
 
=={{header|Elixir}}==
{{trans|Ruby}}
<langsyntaxhighlight lang="elixir">defmodule Subtractive do
def new(seed) when seed in 0..999_999_999 do
s = Enum.reduce(1..53, [1, seed], fn _,[a,b|_]=acc -> [b-a | acc] end)
Line 633 ⟶ 874:
 
Subtractive.new(292929)
for _ <- 1..10, do: IO.puts Subtractive.rand</langsyntaxhighlight>
 
{{out}}
Line 651 ⟶ 892:
=={{header|F_Sharp|F#}}==
<p>Similar to Haskell, using lazy evaluation.</p>
<langsyntaxhighlight lang="fsharp">[<EntryPoint>]
let main argv =
let m = 1000000000
Line 665 ⟶ 906:
r |> Seq.skip 220 |> Seq.take 3
|> Seq.iter (printfn "%d")
0</langsyntaxhighlight>
{{out}}
<pre>467478574
Line 673 ⟶ 914:
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<langsyntaxhighlight lang="fortran">module subgenerator
implicit none
 
Line 728 ⟶ 969:
end do
end program</langsyntaxhighlight>
{{out}}
<pre>
Line 744 ⟶ 985:
 
=={{header|Go}}==
<langsyntaxhighlight lang="go">package main
 
import (
Line 843 ⟶ 1,084:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 852 ⟶ 1,093:
 
=={{header|Haskell}}==
<syntaxhighlight lang ="haskell">subtractgen seed:: =Int drop 220 out-> where[Int]
subtractgen seed = drop 220 out
out = mmod $ r ++ zipWith (-) out (drop 31 out) where
where
r = take 55 $ shuffle $ cycle $ take 55 s
shuffle x out = headmmod xx:shuffle$ xxr where<> xxzipWith =(-) out (drop 3431 xout)
where
s = mmod $ seed:1:zipWith (-) s (tail s)
r = take 55 $ shuffle $ cycle $ take 55 s
mmod = map (`mod` 10^9)
shuffle x = (:) . head <*> shuffle $ drop 34 x
s = mmod $ seed : 1 : zipWith (-) s (tail s)
mmod = fmap (`mod` 10 ^ 9)
 
main :: IO ()
main = mapM_ print $ take 10 $ subtractgen 292929</lang>
main = mapM_ print $ take 10 $ subtractgen 292929</syntaxhighlight>
{{out}}
<pre>
Line 875 ⟶ 1,120:
 
=={{header|Icon}} and {{header|Unicon}}==
<langsyntaxhighlight Iconlang="icon">procedure main()
every 1 to 10 do
write(rand_sub(292929))
Line 900 ⟶ 1,145:
put(ring,get(ring))
return ring[-1]
end</langsyntaxhighlight>
 
{{out}}
Line 921 ⟶ 1,166:
Yes! '''f^:(-1)''' IS the inverse of '''f''' . When known.
 
<langsyntaxhighlight Jlang="j">came_from_locale_sg_=: coname''
cocurrent'sg' NB. install the state of rng sg into locale sg
 
Line 938 ⟶ 1,183:
cocurrent came_from_locale NB. return to previous locale
sg=: sg_sg_ NB. make a local name for sg in locale sg
</syntaxhighlight>
</lang>
 
Use:
<langsyntaxhighlight lang="sh">$ jconsole
load'sg.ijs'
sg 2
Line 948 ⟶ 1,193:
539453717 20349702 615542081 378707948
</syntaxhighlight>
</lang>
 
=={{header|Java}}==
Translation of [[Subtractive_generator#C|C]] via [[Subtractive_generator#D|D]]
{{works with|Java|8}}
<langsyntaxhighlight lang="java">import java.util.function.IntSupplier;
import static java.util.stream.IntStream.generate;
 
Line 1,005 ⟶ 1,250:
.forEach(System.out::println);
}
}</langsyntaxhighlight>
 
<pre>467478574
Line 1,018 ⟶ 1,263:
380969305</pre>
 
=={{header|Mathematicajq}}==
'''Adapted from [[#Wren|Wren]]'''
<lang Mathematica>initialize[n_] :=
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
 
Note that `subrand` as defined here returns the object representing
the current state of the PRNG, with .x set to the most recent PRN.
 
Note also that because jq does not support forward declarations
except insofar as a subfunction may call its parent (or grandparent, etc),
we have defined `subrand` as an accessible subfunction of `subrandSeed`.
<syntaxhighlight lang="jq"># If $p is null, then call `subrand`,
# which sets .x as the PRN and which expects the the input to
# be the PRNG state, which is updated.
def subrandSeed($p):
 
def subrand:
if (.si == .sj) then subrandSeed(0) else . end
| .si |= (if . == 0 then 54 else . - 1 end)
| .sj |= (if . == 0 then 54 else . - 1 end)
| .mod as $mod
| .x = ((.state[.si] - .state[.sj]) | if . < 0 then . + $mod else . end)
| .state[.si] = .x ;
 
if $p == null then subrand
else
{mod: 1e9, state: [], si: 0, sj: 0, p: $p, p2: 1, j: 21}
| .state[0] = ($p % .mod)
| reduce range(1; 55) as $i (.;
if .j >= 55 then .j += -55 else . end
| .state[.j] = .p2
| .p2 = .p - .p2
| if .p2 < 0 then .p2 = .p2 + .mod else . end
| .p = .state[.j]
| .j += 21)
| .si = 0
| .sj = 24
| reduce range(1; 166) as $i (.; subrand)
end;
 
def subrand:
subrandSeed(null);
 
subrandSeed(292929)
| foreach range(0; 10) as $i (.;
subrand;
"r[\($i+220)] = \(.x)")</syntaxhighlight>
{{out}}
<pre>
r[220] = 467478574
r[221] = 512932792
r[222] = 539453717
r[223] = 20349702
r[224] = 615542081
r[225] = 378707948
r[226] = 933204586
r[227] = 824858649
r[228] = 506003769
r[229] = 380969305
</pre>
 
=={{header|Julia}}==
Here is a script, which does not use multiplicative operators, without relying on the optimizer.
{{works with|Julia|1.0}}
 
<syntaxhighlight lang="julia">i,j,m,d,seed = 55,24,10^9,34,292929 # parameters
s = Array{Int32}(undef,i); r = similar(s)
s[1:2] = [seed,1] # table initialization
for n = 3:i; (s[n] = s[n-2]-s[n-1]) < 0 && (s[n] += m) end
t = 1; for u=1:i; (global t+=d)>i && (t-=i); r[u]=s[t] end # permutation, r = s[(d*(1:i) .% i).+1]
 
u,v,n = i,i-j,i-1
while (n += 1) > 0
(global u += 1) > i && (u = 1) # circular indexing: u,v = ((n,n-j) .% i).+1
(global v += 1) > i && (v = 1)
(r[u] -= r[v]) < 0 && (r[u] += m) # table update
n < 220 && continue # 165 silent values
print((n,r[u])) # show (index,value) of next pseudorandom number
x = readline(stdin) # wait until the ENTER key is pressed
length(x) > 0 && break # any other key before ENTER => exit
end</syntaxhighlight>
{{out}}
<pre>(220, 467478574)
(221, 512932792)
(222, 539453717)
(223, 20349702)
(224, 615542081)
(225, 378707948)
(226, 933204586)
(227, 824858649)
(228, 506003769)
(229, 380969305)
(230, 442823364)
(231, 994162810)
(232, 261423281)</pre>
 
=={{header|Kotlin}}==
{{trans|C}}
<syntaxhighlight lang="scala">// version 1.1.51
 
const val MOD = 1_000_000_000
 
val state = IntArray(55)
var si = 0
var sj = 0
 
fun subrandSeed(p: Int) {
var p1 = p
var p2 = 1
state[0] = p1 % MOD
var j = 21
for (i in 1..54) {
if (j >=55) j -= 55
state[j] = p2
p2 = p1 - p2
if (p2 < 0) p2 += MOD
p1 = state[j]
j += 21
}
si = 0
sj = 24
repeat(165) { subrand() }
}
 
fun subrand(): Int {
if (si == sj) subrandSeed(0)
if (si-- == 0) si = 54
if (sj-- == 0) sj = 54
var x = state[si] - state[sj]
if (x < 0) x += MOD
state[si] = x
return x
}
 
fun main(args: Array<String>) {
subrandSeed(292_929)
for (i in 0..9) println("r[${i + 220}] = ${subrand()}")
}</syntaxhighlight>
 
{{out}}
<pre>
r[220] = 467478574
r[221] = 512932792
r[222] = 539453717
r[223] = 20349702
r[224] = 615542081
r[225] = 378707948
r[226] = 933204586
r[227] = 824858649
r[228] = 506003769
r[229] = 380969305
</pre>
 
=={{header|Lua}}==
<syntaxhighlight lang="lua">function SubGen(seed)
local n, r, s = 54, {}, { [0]=seed, 1 }
for n = 2,54 do s[n] = (s[n-2] - s[n-1]) % 1e9 end
for n = 0,54 do r[n] = s[(34*(n+1))%55] end
local next = function()
n = (n+1) % 55
r[n] = (r[(n-55)%55] - r[(n-24)%55]) % 1e9
return r[n]
end
for n = 55,219 do next() end
return next
end
subgen = SubGen(292929)
for n = 220,229 do print(n,subgen()) end</syntaxhighlight>
{{out}}
<pre>220 467478574
221 512932792
222 539453717
223 20349702
224 615542081
225 378707948
226 933204586
227 824858649
228 506003769
229 380969305</pre>
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">initialize[n_] :=
Module[{buffer},
buffer =
Line 1,027 ⟶ 1,452:
nextValue[buffer_] :=
Flatten@{Rest@buffer, Mod[Subtract @@ buffer[[{1, 32}]], 10^9]}</langsyntaxhighlight>
 
<pre>buffer = initialize[292929];
Line 1,044 ⟶ 1,469:
 
</pre>
 
=={{header|Nim}}==
<syntaxhighlight lang="nim">import deques, sequtils
 
template shfl(idx): untyped = (K*(idx+1)) mod I
 
func mutuallyprime(I, K: int16): bool {.compiletime.} =
## compile time check shuffling works properly
let
x = {1'i16..I}
s = x.toSeq
var r: set[int16]
for n in 0..<I:
r.incl s[n.shfl]
r == x
 
func `%`(i: int, m: int): int = (if i < 0: i+m else: i)
## positive modulo, and we don't need to test if > m
## because (i-j) is always less than m
 
template next(state): untyped =
state.addLast (state[^I]-state[^J]) % M
discard state.popFirst()
 
func seedGen[I, J, K, M: static int](seed: range[0..M-1]): Deque[int] =
var s = @[seed, 1]
for _ in 2..<I:
s.add (s[^2]-s[^1]) % M
#reorder and put into ring buffer
for i in 0..<I:
result.addLast s[i.shfl]
#cycle through the next 165 values
for _ in 0..<3*I:
result.next
 
func initSubGen[I, J, K, M: static int](seed: range[0..M-1]): auto =
##check parameters at compile time
##seed will be checked to be in the range 0..M-1
static:
for x in [I, J, K, M]:
assert x > 0, "all params must be positive"
assert I > J, "I must be > J"
assert mutuallyprime(I, K), "I, K must be relatively prime"
var r = seedGen[I, J, K, M](seed)
result = proc(): int =
r.next
r.peekLast
 
let subGen* = initSubGen[55, 24, 34, 1e9.int]
 
when isMainModule:
let rand = subGen(292929)
for _ in 1..3:
echo rand()</syntaxhighlight>
{{out}}
<pre>467478574
512932792
539453717</pre>
 
=={{header|OCaml}}==
{{trans|C}}
 
<langsyntaxhighlight lang="ocaml">let _mod = 1_000_000_000
let state = Array.create 55 0
let si = ref 0
Line 1,081 ⟶ 1,564:
let () =
subrand_seed 292929;
for i = 1 to 10 do Printf.printf "%d\n" (subrand()) done</langsyntaxhighlight>
 
{{out}}
Line 1,095 ⟶ 1,578:
506003769
380969305</pre>
 
=={{header|ooREXX}}==
{{trans|REXX}}
<syntaxhighlight lang="oorexx">/*REXX program uses a subtractive generaTor,and creates a sequence of ranDom numbers. */
/* array index must be positive! */
s=.array~new
r=.array~new
s[1]=292929
s[2]=1
billion=1e9
numeric digits 20
ci=55
Do i=2 To ci-1
s[i+1]=mod(s[i-1]-s[i],billion)
End
cp=34
Do j=0 To ci-1
r[j+1]=s[mod(cp*(j+1),ci)+1]
End
m=219
cj= 24
Do k=ci To m
_=k//ci
r[_+1]=mod(r[mod(k-ci,ci)+1]-r[mod(k-cj,ci)+1],billion)
End
t=235
Do n=m+1 To t
_=n//ci
r[_+1]=mod(r[mod(n-ci,ci)+1]-r[mod(n-cj,ci)+1],billion)
Say right(r[_+1],40)
End
Exit
mod: Procedure
Parse Arg a,b
Return ((a//b)+b)//b </syntaxhighlight>
{{out|output|text=&nbsp; when using the default input:}}
<pre>same as with REXX</pre>
 
=={{header|PARI/GP}}==
<langsyntaxhighlight lang="parigp">sgv=vector(55,i,random(10^9));sgi=1;
sg()=sgv[sgi=sgi%55+1]=(sgv[sgi]-sgv[(sgi+30)%55+1])%10^9</langsyntaxhighlight>
 
=={{header|Perl}}==
<langsyntaxhighlight lang="perl">use 5.10.0;
use strict;
 
Line 1,126 ⟶ 1,646:
 
bentley_clever(292929);
say subrand() for (1 .. 10);</langsyntaxhighlight>
{{out}}
<pre>467478574
Line 1,135 ⟶ 1,655:
...</pre>
 
=={{header|Perl 6Phix}}==
{{trans|PerlC#}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
{{works with|niecza}}
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
{{works with|rakudo|nom}}
<span style="color: #004080;">sequence</span> <span style="color: #000000;">state</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">55</span><span style="color: #0000FF;">)</span>
<lang perl6>sub bentley_clever($seed) {
<span style="color: #004080;">integer</span> <span style="color: #000000;">pos</span>
constant $mod = 1_000_000_000;
my @seeds = ($seed % $mod, 1, (* - *) % $mod ... *)[^55];
<span style="color: #008080;">constant</span> <span style="color: #000000;">MAX</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1e9</span>
my @state = @seeds[ 34, (* + 34 ) % 55 ... 0 ];
<span style="color: #008080;">function</span> <span style="color: #000000;">cap</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
 
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">MAX</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
sub subrand() {
<span style="color: #008080;">return</span> <span style="color: #000000;">n</span>
push @state, (my $x = (@state.shift - @state[*-24]) % $mod);
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
$x;
}
<span style="color: #008080;">function</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">()</span>
 
<span style="color: #000000;">pos</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">,</span><span style="color: #000000;">55</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
subrand for 55 .. 219;
<span style="color: #004080;">integer</span> <span style="color: #000000;">temp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cap</span><span style="color: #0000FF;">(</span><span style="color: #000000;">state</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">state</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">+</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">55</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
 
<span style="color: #000000;">state</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">temp</span>
&subrand ... *;
<span style="color: #008080;">return</span> <span style="color: #000000;">temp</span>
}
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
 
my @sr := bentley_clever(292929);
<span style="color: #008080;">procedure</span> <span style="color: #000000;">init</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">seed</span><span style="color: #0000FF;">)</span>
.say for @sr[^10];</lang>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">temp</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">55</span><span style="color: #0000FF;">)</span>
Here we just make the seeder return the random sequence as a lazy list.
<span style="color: #000000;">temp</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cap</span><span style="color: #0000FF;">(</span><span style="color: #000000;">seed</span><span style="color: #0000FF;">)</span>
 
<span style="color: #000000;">temp</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span> <span style="color: #008080;">to</span> <span style="color: #000000;">55</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">temp</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cap</span><span style="color: #0000FF;">(</span><span style="color: #000000;">temp</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">temp</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">55</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">state</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">temp</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">34</span><span style="color: #0000FF;">*</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">55</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">pos</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">55</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">55</span> <span style="color: #008080;">to</span> <span style="color: #000000;">219</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">292929</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">220</span> <span style="color: #008080;">to</span> <span style="color: #000000;">222</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d: %d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">next</span><span style="color: #0000FF;">()})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>467478574
220: 467478574
512932792
221: 512932792
539453717
222: 539453717
20349702
</pre>
615542081
378707948
933204586
824858649
506003769
380969305</pre>
 
=={{header|PicoLisp}}==
Using a circular list (as a true "ring" buffer).
<langsyntaxhighlight PicoLisplang="picolisp">(setq
*Bentley (apply circ (need 55))
*Bentley2 (nth *Bentley 32) )
Line 1,189 ⟶ 1,722:
(when (lt0 (dec *Bentley (pop '*Bentley2)))
(inc *Bentley 1000000000) )
(pop '*Bentley) )</langsyntaxhighlight>
Test:
<langsyntaxhighlight PicoLisplang="picolisp">(subRandSeed 292929)
(do 7 (println (subRand)))</langsyntaxhighlight>
{{out}}
<pre>467478574
Line 1,203 ⟶ 1,736:
 
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
<lang PL/I>
subtractive_generator: procedure options (main);
 
Line 1,235 ⟶ 1,768:
 
end subtractive_generator;
</syntaxhighlight>
</lang>
<pre>
Required 3 results:
Line 1,263 ⟶ 1,796:
The first 55 generated values are placed directly into their reordered slots in the ring.
An array object is used along with a rotating index object to simulate a ring.
<syntaxhighlight lang="powershell">
<lang PowerShell>
function Get-SubtractiveRandom ( [int]$Seed )
{
Line 1,310 ⟶ 1,843:
Get-SubtractiveRandom
Get-SubtractiveRandom
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,324 ⟶ 1,857:
Uses collections.deque as a ring buffer
 
<langsyntaxhighlight lang="python">
import collections
s= collections.deque(maxlen=55)
Line 1,367 ⟶ 1,900:
for i in xrange(5):
print "result = ", getnextr()
</syntaxhighlight>
</lang>
 
===Python: As a class within a module===
Python 2 and 3 compatable.
<langsyntaxhighlight lang="python">import collections
 
_ten2nine = 10**9
Line 1,393 ⟶ 1,926:
if __name__ == '__main__':
srand = Subtractive_generator()
print([srand() for i in range(5)])</langsyntaxhighlight>
 
{{out}}
<pre>[467478574, 512932792, 539453717, 20349702, 615542081]</pre>
 
=={{header|Quackery}}==
 
<syntaxhighlight lang="Quackery"> [ stack ] is randoms ( --> s )
 
' [ 292929 1 ]
53 times
[ dup -2 peek
over -1 peek
- 1000000000 mod
join ]
dup witheach
[ swap
i^ 34 * 1 - 55 mod
poke ]
randoms put
 
[ randoms take
behead over 30 peek
- 1000000000 mod
tuck join
randoms put ] is rand ( --> n )
 
165 times [ rand drop ]
 
10 times [ rand echo cr ]</syntaxhighlight>
 
{{out}}
 
<pre>467478574
512932792
539453717
20349702
615542081
378707948
933204586
824858649
506003769
380969305</pre>
 
=={{header|Racket}}==
<langsyntaxhighlight Racketlang="racket">#lang racket
(define (make-initial-state a-list max-i)
(for/fold ((state a-list))
Line 1,428 ⟶ 2,000:
;that returns a new random number each time it's called
(define rand (create-substractive-generator 292929))
(build-list 3 (lambda (_) (rand))) ;returns a list made from the 3 wanted numbers</langsyntaxhighlight>
 
=={{header|Raku}}==
(formerly Perl 6)
{{trans|Perl}}
{{works with|Rakudo|2018.03}}
 
<syntaxhighlight lang="raku" line>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];</syntaxhighlight>
Here we just make the seeder return the random sequence as a lazy list.
 
{{out}}
<pre>467478574
512932792
539453717
20349702
615542081
378707948
933204586
824858649
506003769
380969305</pre>
 
=={{header|REXX}}==
{{trans|PL/I}}
 
<lang rexx>/*REXX program uses a subtractive generator, and creates a sequence of random numbers.*/
Some optimization was done so that the first two &nbsp; '''do''' &nbsp; loops executed faster.
numeric digits 20; s.0=292929; s.1=1; billion=10**9 /* ◄────────┐*/
<syntaxhighlight lang="rexx">/*REXX program uses a subtractive generator, and creates a sequence of random numbers. */
cI=55; cJ=24; cP=34; billion=1e9 /*same as─►─┘*/
s.0= 292929; s.1= 1; do i=2 to cI-1 billion= 1e9
numeric digits 20
s.i=mod(s(i-2) - s(i-1), billion)
cI= 55; do i=2 for cI-2; s.i= mod( s(i-2) - s(i-1), end /*i*/billion)
do j=0 to cI-1 end /*i*/
Cp= 34
r.j=s(mod(cP*(j+1), cI))
end /* do j=0 for cI; r.j= s( mod( cP */ (j+1), cI))
end /*j*/
m=219
m= 219; Cj= 24
do k=cI to m; x=k//cI
r.x=mod(r(mod( do k-=cI, cI)) - r(mod(to m; _= k-cJ, cI)),// billion)cI
r._= mod( r( mod(k-cI, cI)) - r( mod(k-cJ, cI) ), billion)
end /*m*/
end /*m*/
t=235
t= 235
do n=m+1 to t; y=n//cI
r.y=mod(r(mod( do n-cI,=m+1 cI)) -to t; _= r(mod(n-cJ, cI)),// billion)cI
say right( r.y_= mod( r( mod(n-cI, 40cI)) - r( mod(n-cJ, cI) ), billion)
end /*n*/ say right(r._, 40)
exit end /*stick a fork in it, we're all done. n*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
mod: procedure; parse arg a,b; return ( (a // b) + b) // b
r: parse arg _#; return r._#
s: parse arg _#; return s._#</langsyntaxhighlight>
'''{{out|output''' |text=&nbsp; when using the default input:}}
<pre>
467478574
Line 1,473 ⟶ 2,083:
563900213
</pre>
 
=={{header|RPL}}==
Here, most data manipulation is performed directly in the stack. This requires less code, but slows down execution: when handling large amounts of data in RPL, it is better to store them in array variables and perform operations directly on them.
{{works with|Halcyon Calc|4.2.7}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪ 1
2 54 '''START''' DUP2 - 1E9 MOD '''NEXT'''
55 →ARRY ''''SEEDS'''' STO
0 54 '''FOR''' j
''''SEEDS'''' j 1 + 34 * 55 MOD GET 1 + GET '''NEXT'''
55 →ARRY ''''SEEDS'''' STO
≫ ''''INITX'''' STO
≪
'''SEEDS''' ARRY→ DROP
55 ROLL 25 PICK - 1E9 MOD
55 →ARRY ''''SEEDS'''' STO
≫ ''''XPAT2'''' STO
|
'''INITX''' ''( seed -- )''
calculate in stack s(n)=mod(s(n-2)-s(n-1),10^9) for 2≤n≤54
Store s(0)..s(54) as an array in SEEDS variable
for j=0 to 54
r(j) = s(mod(34*(j+1),55)) & keep it in stack
Store r(0)..r(54) as an array in SEEDS variable
'''XPAT2''' ''( -- )''
Put SEEDS in stack
r(n+1) = mod(r(n-55)-r(n-24),10^9)
Transfer stack to SEEDS
|}
{{in}}
<pre>
≪ 292929 INITX
55 222 START XPAT2 NEXT
220 222 FOR j SEEDS j GET NEXT
≫ EVAL
</pre>
{{out}}
<pre>
3: 467478574
2: 512932792
1: 539453717
</pre>
Runs in 97 seconds on a basic HP-28S
 
=={{header|Ruby}}==
This implementation aims for simplicity, not speed. <code>SubRandom#rand</code> pushes to and shifts from an array; this might be slower than a ring buffer. The seeding method must call <code>rand</code> 55 extra times (220 times instead of 165 times). The code also calls [[Arithmetic/Integer#Ruby|Ruby's modulus operator]], which always returns a non-negative integer if the modulus is positive.
 
<langsyntaxhighlight lang="ruby"># SubRandom is a subtractive random number generator which generates
# the same sequences as Bentley's generator, as used in xpat2.
class SubRandom
Line 1,513 ⟶ 2,174:
 
rng = SubRandom.new(292929)
p (1..3).map { rng.rand }</langsyntaxhighlight>
 
<pre>[467478574, 512932792, 539453717]</pre>
 
=={{header|Rust}}==
 
{{works with|Rust|2021}}
This implementation uses a ring buffer in the form of a <code>Vec<i32></code>. It is fully configurable, although the seeding algorithm is only implemented for a generator with i = 55, j = 24, and m = 10<sup>9</sup>.
Like C, Rust's <code>%</code> will give negative results for some negative parameters. This algorithm uses [https://doc.rust-lang.org/std/primitive.i32.html#method.rem_euclid the <code>i32::rem_euclid()</code> method] instead.
<syntaxhighlight lang="rust">struct SubtractiveGenerator {
/// m in the formula
modulo: i32,
/// i and j in the formula
offsets: (u32, u32),
/// r in the formula. It is used as a ring buffer.
state: Vec<i32>,
/// n in the formula
position: usize,
}
 
impl SubtractiveGenerator {
fn new(modulo: i32, first_offset: u32, second_offset: u32) -> Self {
// The state size has to fit into a usize to index state properly
// without overflow.
let state_size: usize = first_offset.try_into().unwrap();
 
// Both offsets have to fit in i32 for the substractions to work
// without overflow.
assert!(first_offset <= i32::MAX as u32);
assert!(first_offset > second_offset);
SubtractiveGenerator {
modulo,
offsets: (first_offset, second_offset),
state: Vec::with_capacity(state_size),
position: 0,
}
}
}
 
impl Iterator for SubtractiveGenerator {
type Item = i32;
 
fn next(&mut self) -> Option<<Self as Iterator>::Item> {
let state_size = self.offsets.0 as usize;
 
assert_eq!(self.state.len(), state_size);
 
self.position = (self.position + 1) % self.offsets.0 as usize;
 
let i1 = (self.position as i32 - self.offsets.0 as i32).rem_euclid(state_size as i32);
let i2 = (self.position as i32 - self.offsets.1 as i32).rem_euclid(state_size as i32);
 
let p1 = self.state[i1 as usize];
let p2 = self.state[i2 as usize];
 
self.state[self.position] = (p1 - p2).rem_euclid(self.modulo);
 
Some(self.state[self.position])
}
}
 
/// Returns a pre-seeded subtractive generator, which generates the same
/// sequences as Bentley's generator, as used in xpat2.
fn get_seeded_xpat2_gen(seed: i32) -> SubtractiveGenerator {
let mut gen = SubtractiveGenerator::new(1_000_000_000, 55, 24);
 
let state_size = gen.offsets.0 as usize;
 
let mut pre_state = Vec::with_capacity(state_size);
pre_state.push(seed);
pre_state.push(1);
for i in 2..state_size {
pre_state.push((pre_state[i - 2] - pre_state[i - 1]).rem_euclid(gen.modulo));
}
 
for i in 0..state_size {
gen.state.push(pre_state[(34 * (i + 1)) % 55]);
}
 
gen.position = 54;
for _ in 0..165 {
gen.next();
}
 
gen
}
 
fn main() {
let gen = get_seeded_xpat2_gen(292929);
 
for n in gen.take(5) {
println!("{}", n);
}
}</syntaxhighlight>
<pre>467478574
512932792
539453717
20349702
615542081</pre>
 
=={{header|Seed7}}==
<langsyntaxhighlight lang="seed7">$ include "seed7_05.s7i";
 
const integer: MOD is 1000000000;
Line 1,571 ⟶ 2,328:
writeln(subrand(gen));
end for;
end func;</langsyntaxhighlight>
 
{{out}}
Line 1,588 ⟶ 2,345:
 
=={{header|Sidef}}==
<langsyntaxhighlight lang="ruby">class SubRandom(seed, state=[]) {
 
const mod = 1_000_000_000;
Line 1,609 ⟶ 2,366:
 
var r = SubRandom(292929);
10.times { say r.subrand };</langsyntaxhighlight>
{{out}}
<pre>
Line 1,626 ⟶ 2,383:
=={{header|Tcl}}==
{{trans|C}}
<langsyntaxhighlight lang="tcl">package require Tcl 8.5
namespace eval subrand {
variable mod 1000000000 state [lrepeat 55 0] si 0 sj 0
Line 1,660 ⟶ 2,417:
for {set i 0} {$i < 10} {incr i} {
puts [subrand::gen]
}</langsyntaxhighlight>
 
=={{header|uBasic/4tHWren}}==
{{trans|C}}
<lang>Push 292929 : Gosub 100 : d = Pop()
<syntaxhighlight lang="wren">var mod = 1e9
var state = List.filled(55, 0)
var si = 0
var sj = 0
 
var subrand // forward declaration
For i = 1 To 10
Push 0 : Gosub 100
Print Pop()
Next
 
var subrandSeed = Fn.new { |p|
End
var p2 = 1
state[0] = p % mod
var j = 21
for (i in 1..54) {
if (j >= 55) j = j - 55
state[j] = p2
p2 = p - p2
if (p2 < 0) p2 = p2 + mod
p = state[j]
j = j + 21
}
si = 0
sj = 24
for (i in 1..165) subrand.call()
}
 
subrand = Fn.new {
100 s = Pop()
Ifif s(si == 0sj) ThensubrandSeed.call(0)
psi = (psi +== 10) %? 5554 : si - 1
sj = @(p)sj == @(p0) -? @((p54 +: 31)sj %- 55)1
var x = Ifstate[si] @(p)- < 0 Thenstate[sj]
if (x < 0) @(p)x = @(p)x + 1000000000mod
state[si] = Endifx
return x
Push (@(p)) : Return
}
Endif
 
subrandSeed.call(292929)
@(54) = s : @(33) = 1
for (i in 0..9) System.print("r[%(i+220)] = %(subrand.call())")</syntaxhighlight>
p = 12
 
For i = 2 To 54
@(p) = @((p + 42) % 55) - @((p + 21) % 55)
If @(p) < 0 Then
@(p) = @(p) + 1000000000
Endif
p = (p + 34) % 55
Next
 
For i = 55 To 219
Push 0 : Gosub 100 : d = Pop()
Next
 
Push 0 : Return</lang>
{{out}}
<pre>467478574
r[220] = 467478574
512932792
r[221] = 512932792
539453717
r[222] = 539453717
20349702
r[223] = 20349702
615542081
r[224] = 615542081
378707948
r[225] = 378707948
933204586
r[226] = 933204586
824858649
r[227] = 824858649
506003769
r[228] = 506003769
380969305
r[229] = 380969305
 
0 OK, 0:864
</pre>
 
Line 1,717 ⟶ 2,476:
{{trans|Python}}
{{trans|C}}
<langsyntaxhighlight lang="zkl">fcn rand_sub(x){
var ring=L(),m=(1e9).toInt();
mod:='wrap(n){ if(n<0) n+m else n };
Line 1,728 ⟶ 2,487:
ring.append((ring.pop(0)-ring[-24]):mod(_));
return(ring[-1]);
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">do(4){ println(rand_sub(292929)) } //seed ignored after first call</langsyntaxhighlight>
{{out}}
<pre>
PureFox
9,482

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/196320...351050"