Talk:Subtractive generator
So... what am I doing wrong?
I've implemented this algorithm, including Bentley's cleverness, and it just does not look right to me.
For example: i= 55, j=24, m= 1e9, picking a random seed: 109488485
This gives me an initial sequence that looks something like this: 109488485 1 890511516 890511515 999999999 109488484 109488485 1 890511516 890511515 999999999 ... and when I re-order it and run the generator for an extra 165 iterations S looks like this: 275363168 101452672 275363168 275363169 275363169 1 1 724636832 724636832 724636833 724636831 449273662 999999998 999999998
In other words, the resulting sequence has some extremely predictable artifacts. And using J=21 instead of J=24 might improve the situation slightly (I got 337354485 325291032 674708968 325291034 674708966 325291034 999999998 2 ... for my initial S, picking a different random S0), but I still see the artifacts.
And the artifacts seem to have a life of their own, independent of my .
Is the algorithm really this bad? Or am I doing something wrong? --Rdm 15:14, 2 August 2011 (UTC)
- Did you get the sequence as in example with seed 292929? The following code<lang perl>use 5.10.0;
use strict;
my @state; my $mod = 1_000_000_000;
sub init_state { my @s = ( shift() % $mod, 1); push @s, ($s[-2] - $s[-1]) % $mod while @s < 55;
@state = (); $state[ (21 * $_) % 55 ] = $s[$_] for (0 .. 54);
subrand() for (55 .. 219); }
sub subrand() { my $x = ($state[-55] - $state[-24]) % $mod; #shift @state; push @state, $x; return $x; }
init_state(292929); for (0 .. 9, 210 .. 219) { say "$_: $state[$_]"; } say ""; for (1 .. 10) { say scalar(@state), ": ", subrand(); }</lang> gave me different answers. --Ledrug 17:32, 2 August 2011 (UTC)
- EDIT I looked at Bentley's C code, and the task description is incorrect. After step 4, the sequence r0 ... r54 needs to be reversed. Bentley's code performs step 3 forward, but generates rand numbers by iterating the r array backward. --Ledrug 17:51, 2 August 2011 (UTC)
- I found my problem. I was using s[-1] - s[-2] instead of the other way around. --Rdm 19:06, 2 August 2011 (UTC)
- I wrote this task. I thank Rdm and Ledrug for trying to solve the task. Ledrug found a mistake. My test code used r(n) = r(n + 55) + r(n + 24) (mod 55). In the task, I wrote r(n) = r(n - 55) + r(n - 24) (mod 55) and accidentally reversed the subscripts of r. I now edit step 4, reversing the order of r0, ..., r54. --Kernigh 19:39, 2 August 2011 (UTC)