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 $\scriptstyle S_{0}$.

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

code scrubbed

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)

Eh wait, current description is still off by 1. $r(34n-1\mod 55)=s(n)$ is equiv to $s(34(1+n)\mod 55)=r(n)$ for $n=0\cdots 54$ --Ledrug 19:54, 2 August 2011 (UTC)

While the introductory text uses i=55, j=24, the step by step breakdown seems to use i=55, j=21 and 34 just happens to be i-j. And my implementation still does not quite work right, but maybe I should wait a bit for the task description to settle down. --Rdm 19:58, 2 August 2011 (UTC)

No no, 21 is used for shuffling state array during init, while 24 is used for generating random numbers, they are not the same number. --Ledrug 20:02, 2 August 2011 (UTC)

Ok... but I do not see why 21 is being introduced. Ok, sure, 21 and 55 are relatively prime and so are (55-21=34) and 55. But the same holds 24 and 55 and (55-24=31) and 55. This would not be such a big thing, but this seems to be being explained as a general concept as opposed to a cookbook technique where only the listed values are appropriate. --Rdm 22:13, 2 August 2011 (UTC)