Anonymous user
Subtractive generator: Difference between revisions
Add Rust version
(→{{header|jq}}: state: []) |
(Add Rust version) |
||
Line 1,887:
<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.
<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);
}
}</lang>
<pre>467478574
512932792
539453717
20349702
615542081</pre>
=={{header|Seed7}}==
| |||