Libraryless. Click here for Pure Java version (10149L/56K).
1 | // This is an LFSR (aka the XORSHIFT algorithm) which is a deterministic, |
2 | // very fast random number generator cycling through all integers |
3 | // between 1 and 2^n-1 (incl.). |
4 | |
5 | sclass TripletLSFR {
|
6 | // params |
7 | int n; |
8 | int value = 1; // start value, but is also changed during execution |
9 | int a, b, c; // the triplet |
10 | |
11 | // calculated |
12 | gettable int cycleLength; |
13 | |
14 | // changing variables |
15 | int step; |
16 | |
17 | // triplets table for n's from 1 to 31 |
18 | // (just the first triple that gives a full cycle, including degenerate ones, |
19 | // so not optimized for "randomness") |
20 | |
21 | static final int[][] tripletsTable = {
|
22 | { 0, 0, 0 },
|
23 | { 0, 1, 1 },
|
24 | { 0, 1, 1 },
|
25 | { 0, 1, 3 },
|
26 | { 0, 1, 1 },
|
27 | { 0, 1, 1 },
|
28 | { 0, 1, 3 },
|
29 | { 1, 1, 2 },
|
30 | { 0, 1, 1 },
|
31 | { 0, 3, 7 },
|
32 | { 0, 1, 1 },
|
33 | { 1, 1, 4 },
|
34 | { 0, 1, 6 },
|
35 | { 0, 1, 1 },
|
36 | { 0, 1, 4 },
|
37 | { 1, 1, 14 },
|
38 | { 0, 3, 7 },
|
39 | { 1, 3, 14 },
|
40 | { 0, 1, 3 },
|
41 | { 1, 5, 6 },
|
42 | { 0, 1, 6 },
|
43 | { 0, 1, 21 },
|
44 | { 0, 1, 1 },
|
45 | { 1, 5, 18 },
|
46 | { 0, 1, 12 },
|
47 | { 0, 1, 1 },
|
48 | { 0, 2, 7 },
|
49 | { 0, 3, 25 },
|
50 | { 0, 1, 1 },
|
51 | { 0, 1, 1 },
|
52 | { 0, 3, 28 }
|
53 | }; |
54 | |
55 | *(int *n) {
|
56 | if (n < 1 || n > tripletsTable.length) |
57 | fail("Don't have triples for " + nBits(n));
|
58 | init(tripletsTable[n-1]); |
59 | } |
60 | |
61 | *(int *n, int a, int b, int c) {
|
62 | init(a, b, c); |
63 | } |
64 | |
65 | void init(int[] triplet) {
|
66 | init(triplet[0], triplet[1], triplet[2]); |
67 | } |
68 | |
69 | void init(int a, int b, int c) {
|
70 | // handle triplets with 0s (meaning to skip one of the 3 xorshifts) |
71 | meta-for a in a, b, c {
|
72 | this.a = a == 0 ? n : a; |
73 | } |
74 | |
75 | cycleLength = (1 << n)-1; |
76 | } |
77 | |
78 | int next() {
|
79 | step++; |
80 | |
81 | int x = value; |
82 | x ^= (x << a) & cycleLength; |
83 | x ^= x >>> b; |
84 | x ^= (x << c) & cycleLength; |
85 | ret value = x; |
86 | } |
87 | |
88 | bool cycleComplete() { ret step >= cycleLength(); }
|
89 | |
90 | // takes any integer |
91 | selfType start aka value(int start) {
|
92 | value = mod(start, cycleLength)+1; |
93 | this; |
94 | } |
95 | } |
download show line numbers debug dex old transpilations
Travelled to 4 computer(s): bhatertpkbcr, ekrmjmnbrukm, mowyntqkapby, mqqgnosmbjvj
No comments. add comment
| Snippet ID: | #1035196 |
| Snippet name: | TripletLSFR - linear feedback shift register (repeating pseudo-RNG with a cycle length of 2^n-1, using ints) |
| Eternal ID of this version: | #1035196/42 |
| Text MD5: | 1a99c53ffdc4932f7ae1cc948bc466ea |
| Transpilation MD5: | bb0a510ac035799545269b0132483436 |
| Author: | stefan |
| Category: | javax |
| Type: | JavaX fragment (include) |
| Public (visible to everyone): | Yes |
| Archived (hidden from active list): | No |
| Created/modified: | 2023-02-12 11:56:33 |
| Source code size: | 2080 bytes / 95 lines |
| Pitched / IR pitched: | No / No |
| Views / Downloads: | 233 / 478 |
| Version history: | 41 change(s) |
| Referenced in: | [show references] |