It's a way to use a linear congruential generator function (LCG) to permute sequences with no repeats and a known period
https://en.wikipedia.org/wiki/Linear_co ... E2%89%A0_0
That seems to suggest that m must be a power of 2 but that is not correct, m can be anything (some m give crappy sequences though).
So the next term is of the form
x(n+1) = (a * x(n) + c) mod m
the theorem tells you which values of a and c will permute through all the combinations after m iterations (there's quite a lot of choice).
so that tells you which parameters are possible. I used a 24x18 grid of attributes and I am setting them so they are all visited exactly once. Some of the patterns are cool
Basin source:
Code: Select all
10 OUT 254,2
20 DEF FN m(a,b)=a-INT (a/b)*b
30 READ k: IF k=0 THEN STOP
40 FOR i=1 TO 145 STEP 12: PRINT AT 0,20;i;" ";k
50 LET a=431: FOR f=1 TO 432: LET a=FN m(a*i+k,432): LET row=INT (a/18): LET col=FN m(a,18): POKE 22529+row*32+col,0: NEXT f
60 BEEP 0.5,0: PAUSE 0: CLS : OUT 254,2: NEXT i
70 GO TO 30
1000 DATA 1,5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,53,55,59,61,65,67,71,73,77,79,83,85,89,91,95,97,101,103,107,109,113,115,119,121,125,127,131,133,137,139,143,145,149,151,155,157,161,163,167,169,173,175,179,181,185,187,191,193,197,199,203,205,209,211,215,217,221,223,227,229,233,235,239,241,245,247,251,253,257,259,263,265,269,271,275,277,281,283,287,289,293,295,299,301,305,307,311,313,317,319,323,325,329,331,335,337,341,343,347,349,353,355,359,361,365,367,371,373,377,379,383,385,389,391,395,397,401,403,407,409,413,415,419,421,425,427,431,0
Quite a good screensaver anyway.
You can also use it to procedurally generate stuff (the location names in Doomdark's Revenge use something similar).
I can explain how to tweak parameters to fill any size grid if the theorem explanation is a bit too much for people to deal with on a bank holiday... it helps if the width x height has a lot of prime factors though (large powers of 2 are the best of course).
FN m(a, b) is A MOD B
I am setting a = 1 + 12n (note: that form of a is required by the theorem to make sure all cells are visited) but only going up to values of a which will be less than 65536 after multiplying by numbers < 432, for ASM reasons later
I set the initial value to 432-1 which always seems to visit the bottom right cell last... changing that number (LET a = 431 on line 50) starts the sequence at a different point.
Anyway it's fun to watch it working
If I do a version in assembler I will use modulo a power of 2 so I can do the modulo via a bitwise AND (and throw away any results >= the modulo amount).