Hull-Dobell theorem for procedural generation/screen fades etc.

[ParadigmShifter]

I can't believe I only found out about this theorem today

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

sorry about the enormous data statement at the end there, was pasted into BASIN from Wolfram Alpha, it's a list of all N < 432 which are coprime to 432, terminated with 0. I expect some of the values will produce the same sequences though, not sure? So you can either try some values at random, see if they look good, or write down a few nice values for the parameters.

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).

[ParadigmShifter]

Obviously for procedural generation you want to use the inverse function which is just a case of setting x(n) to some value based on the grid coordinates and x(n+1) will tell you the next value in the sequence which is your output. (99.9% certain that will work, not sure if the numbers will come out in the same order, I will do some tests on that later on I think). EDIT: They do come out in a different order but all elements are still visited (from my tests so far anyway).

EDIT2: Nope the patterns are too regular... will investigate more. What I posted above is ideal for screen fade out effects though anyway.

EDIT3: Although after running emulator on faster speed and watching a fair few I think the overflowing 16 bits might be important to make it look more random, hmm. Or maybe a power of 2 will be less samey... quite a lot of the fades look pretty similar at the moment. Anyway, I'm glad I found out the criteria for which parameters will work for any modulo m, so that's handy. Surprised it was only proven in 1962 though! "Number theory is hard" - Barbie. And Barbie was right about that I didn't understand most of it at uni lol

[ParadigmShifter]

Ok so after watching that program with emulation speed increased to make it less slow... that seems promising but maybe a tad too regular.

I think the classic method (I think this is the classic method anyway) of doing a pixel (or attributes) transition is maybe best for completely random fadeouts/transitions, which is

pick a random number in the range width x height

if that location has not yet been visited (requires an extra bit, if it's attribs you can use the flash bit if you don't use that I guess), visit it and mark it visited.
else check next pixel along, go back to the if statement above.

That basically requires a linear search for the last location and you need to check the visited flag every time you visit or to skip a cell. EDIT: But you only need to get a random number once then of course which I am assuming is quite slow.

EDIT2: I'm also guessing that the BASIC code is the fastest way to do it in pure BASIC since it doesn't require loads of looping to find an unvisited location? At least the algorithm anyway, I'm sure people who know BASIC better can make it faster still.

Code I posted above always visits each location exactly once but does require a multiply (by a constant, unless you change the constant of course since there's a lot of values which are feasible) and a modulus (which is fine if it's a power of 2). If not a power of 2 you have to keep fetching new numbers until it is in range, or actually implement a modulo function. Checking my usual first place to go gives the fastest modulo function for arbitrary 16 bit values to be this

Code: Select all

BC_Div_DE:
;BC/DE ==> BC, remainder in HL
;NOTE: BC/0 returns 0 as the quotient.
;min: 738cc
;max: 898cc
;avg: 818cc
;144 bytes
  xor a
  ld h,a
  ld l,a
  sub e
  ld e,a
  sbc a,a
  sub d
  ld d,a

  ld a,b
  rla \ adc hl,hl \ add hl,de \ jr c,$+4 \ sbc hl,de
  rla \ adc hl,hl \ add hl,de \ jr c,$+4 \ sbc hl,de
  rla \ adc hl,hl \ add hl,de \ jr c,$+4 \ sbc hl,de
  rla \ adc hl,hl \ add hl,de \ jr c,$+4 \ sbc hl,de
  rla \ adc hl,hl \ add hl,de \ jr c,$+4 \ sbc hl,de
  rla \ adc hl,hl \ add hl,de \ jr c,$+4 \ sbc hl,de
  rla \ adc hl,hl \ add hl,de \ jr c,$+4 \ sbc hl,de
  rla \ adc hl,hl \ add hl,de \ jr c,$+4 \ sbc hl,de
  rla
  ld b,a

  ld a,c
  rla \ adc hl,hl \ add hl,de \ jr c,$+4 \ sbc hl,de
  rla \ adc hl,hl \ add hl,de \ jr c,$+4 \ sbc hl,de
  rla \ adc hl,hl \ add hl,de \ jr c,$+4 \ sbc hl,de
  rla \ adc hl,hl \ add hl,de \ jr c,$+4 \ sbc hl,de
  rla \ adc hl,hl \ add hl,de \ jr c,$+4 \ sbc hl,de
  rla \ adc hl,hl \ add hl,de \ jr c,$+4 \ sbc hl,de
  rla \ adc hl,hl \ add hl,de \ jr c,$+4 \ sbc hl,de
  rla \ adc hl,hl \ add hl,de \ jr c,$+4 \ sbc hl,de
  rla
  ld c,a

  ret

which is pretty slow still lol, there's a less unrolled version which is nearly as fast and takes up less code space too.

From here:

http://z80-heaven.wikidot.com/advanced-math#toc25

I know there are routines around which turn modulo into multiplication (also by a constant) but I'm having trouble finding them, they use magic constants IIRC for each modulo value? So if anyone knows about that, that would be handy.

I can probably improve the randomness a bit by overcovering the space say 8 times and only visiting if the lower 3 bits are 0 I suppose (may have to do a lot more calculations though to make the transition complete fast enough) - if I visit 1 attrib per frame that will take 432/50 = 15.36 seconds so I'd want to visit more than 1 attrib per frame really (somewhere between 4 and 8 I guess).

I'll probably round to the nearest power of 2 and keep generating values if they return >= m though first. I'd still have to implement a multiply though, but hey there's a first time for everything (and that site above has decent multiplication code anyway).

I'll probably do a version which visits all 768 attribute locations (have to change m to be 768, and work out acceptable values for a and c as well) while I'm at it. Although if I use the rejection method for values >= 768 to avoid a modulo that will reject 1/4 of the values returned on average lol.

I do like how you get a predictable deterministic effect though with what I posted in the OP, and even the ones with obvious patterns look interesting most of the time.

[ParadigmShifter]

Ok I've remembered another algorithm which is fairly quick to do a random dissolve but is only really suitable for small arrays (my 432 size array might be fine though, since have to weigh that against the code size of a more complicated algorithm)... just stash the numbers 0...431 (in my case, 0...n-1 in general) in an array and do a random shuffle on that array.

Standard random_shuffle in C++ is O(n) swaps... obvious templated up the wazoo C++ code warning, all of the standard library is like this This is the most basic version of the alg to do a random shuffle.

Code: Select all

template<class RandomIt>
void random_shuffle(RandomIt first, RandomIt last)
{
    typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
 
    for (diff_t i = last - first - 1; i > 0; --i)
    {
        using std::swap;
        swap(first[i], first[std::rand() % (i + 1)]);
        // rand() % (i + 1) is not actually correct, because the generated number is
        // not uniformly distributed for most values of i. The correct code would be
        // a variation of the C++11 std::uniform_int_distribution implementation.
    }
}

which still uses modulo for non powers of 2 sizes. And swap is quite slow for 16 bit values on a Z80 too. And 432*2 bytes storage requirement is quite big, totally impractical for pixels instead of attribs. You have to pay the up front cost of shuffling the array as an initialisation step of course.

On modern CPUs where modulo is quite fast (if the compiler optimiser knows the tricks to turn modulo into multiplication) I think the original algorithm is probably pretty good as well.

One to add to my toolbox anyway I was using the standard "check if we visited and if so skip to the next node (wrapping around if we reach the end)" implementation before I discovered this theorem. (I already knew the case where the period is a prime number... that's a basic result in group theory, so AS levels probably in the UK?). Reason: Z/p where p is prime is a finite field and is generated by any element except 0. (i.e. {a, 2a, 3a, 4a, ..., n*a} mod p for any a != 0 gives the same field (i.e. it's a bijective map so is 1-1 and has an inverse), just reordered).

[zxbruno]

This reminded me of a question I asked on the WOS forums 16 years ago:

https://worldofspectrum.org/forums/disc ... -effect/p1

[ParadigmShifter]

Well I wouldn't have been very good in that thread since I only discovered the theorem today (which gives necessary and sufficient criteria for an LCG to have a maximal period).

Alcoholics Anonymous got closest but only gave 1 example and still checking whether the cell has been visited and looping if not. Of course modulo is pretty slow so looping may be faster (but using a power of 2 and rejecting if result is >= m may be good, will try that in ASM at some point). EDIT: nope, it just rejects values >= 768 and relies on the fact that when you return to the initial value you have visited all cells. Good solution but doesn't say what the criteria is for maximal period and period is always a power of 2 with what they used... which might be (in fact very likely I suspect) the fastest way - since it bins off the modulo operation. Worst case is the period is a (power of 2) + 1, reject nearly 50% of the numbers generated by the LCG then. Which may be faster than doing a divide. I'm sure there's a cleverer way to optimise a mod k where k is constant involving turning it into a multiplication though... might involve double precision multiplications though.

EDIT: gasman (and PeeJay in the first reply) also suggested the random shuffle method but that's not good for large shuffle sizes. That's the best method for "truly (pseudo-)random" results though, but uses a lot of memory and the setup is slow.

Jof posting in the thread made me a bit sad RIP. EDIT: OMG he suggested INC D \ DEC D instead of LD A, D \ OR A before a JR Z to preserve A register (same speed but may be useful if I save A before doing that)... never thought of doing that before hmm... I do use that for the A register sometimes, never any other though! time to look at my code again lol)

The theorem doesn't even have it's own entry on Wikipedia it's sort of mentioned and linked to (and they kind of suggest m needs to be a power of 2 although they clarify that later, it's FALSE, m can be anything, needs to have a lot of factors though to look convincingly random - repeated prime factors are fine), which is pretty poor for wikipedia.

Was looking again earlier at the program running. I thought having a and c both prime would help (with the random appearance of the patterns) but it seems random whether it does or not... primes are pretty wacky objects in maths So maybe it's better if a and c have a lot of factors in common, dunno, could be completely random like most things prime related. I'm not Bernhard Riemann lol

EDIT: As I said anyway I think that method will be fastest in pure BASIC if someone good at optimising BASIC has a look at it. Can obviously unroll the loop quite a bit... Multiplying by a variable constant 1/18 instead of dividing by 18 might be ok, it's not a power of 2 denominator though so you probably need to round.., best use a power of 2 denominator probs?... It doesn't give all possible permutations (only ones using an LCG) but many of them are "pretty good" I think especially if the dissolve is fast. Many of the aren't what I'd call "pretty good" but some of those have interesting patterns like it looks like the screen is melting/dripping and such I can't be arsed optimising BASIC myself lol. I'll write a BASIC proof of concept before doing something in ASM though sometimes.

It only takes about 18-20 seconds to fill all 432 attribs (and running time per iteration is pretty uniform - which is a good thing to have in BASIC... don't want the last iteration to take ages) so it's nearly changing 1 attrib per frame, not bad for BASIC lol

EDIT2: Another reason it's pretty random is that it uses an iterated system f(f(f(n)))) etc. which is where chaos theory starts rearing it's head.

EDIT3: I see you started that thread on WoS lol

[patters]

This sounds quite interesting but it's beyond my comprehension. Any chance of some example screen dissolves as gif attachments for the idiots in the cheap seats?

[ParadigmShifter]

Yeah. Spin always hangs after recording a GIF so consider yourself lucky

I only remembered to whack up the emulator speed to 500% after a bit... BASIC sucks etc.



It's not a proper dissolve obvs but I'm sure you can work out how to adapt it to do that.

The maths isn't hard, just the proof was I think?

I think the sweet spot may be around the halfway mark (I only got to 7 there and stopped in the coprime list) but with prime numbers it's hard to predict what will happen until you see it. I guess people just pick some that combo that seems nice (when the period is much larger obvs) and go with that. I'm going to stash some nice values and use them I think (may pick from all of them for ultimate surprise not knowing what will happen though).

To do a fade or transition you need to store 2 sets of attribs and flick between which ones you copy to the screen (which is very easy to do) and once you have finished doing 1 switch to the other.

[MustardTiger]

I've had this tatty old photocopy of an old Dr Dobbs article for decades which had a really nice way of doing digital dissolves. I found an online copy of it here https://archive.org/details/1986-11-dr- ... 8/mode/2up

It's the Galois LFSR which is on the wikipedia page in the WOS thread, but the article above has all the masks for each size of sequence which is great.

I coded up an attribute dissolve, I think it looks fairly random.



This is my code for 8 and 16 bit versions.

Code: Select all

; https://archive.org/details/1986-11-dr-dobbs-journal/page/48/mode/2up

Dissolve16
		ld de,1			;initial value
		ld hl,#240		;mask
		ld bc,1024
.loop	
		srl d			;value = value >> 1
		rr e
		jr nc,.noxor	;if carry clear, no xor
		ld a,d
		xor h			;value = value xor mask
		ld d,a
		ld a,e
		xor l
		ld e,a
.noxor
		ld a,d			;if value >= 0x300 don't draw
		cp #3
		jr nc,.nodraw

		push hl
		ld hl,#5800		;attribute address
		add hl,de		;add value
		ld a,(discolor)	;set to current color
		ld (hl),a	
		pop hl	

		ld a,c			;slow down effect, halt every 15 blocks
		and 15
		jr nz,.nohalt
		halt
.nohalt

.nodraw
		dec bc
		ld a,b
		or c
		jr nz,.loop

		ld a,(discolor)	;increment color
		add 0b00001000
		and 0b00111000
		ld (discolor),a
		jp Dissolve16


Dissolve8
		ld e,1
		ld d,#b8

		ld b,0
.loop
		ld a,e
		srl a
		jr nc,.noxor1
		xor d
.noxor1	ld e,a
		ld h,#58
		ld l,e
		ld a,(discolor)
		ld (hl),a

		ld a,b
		and 7
		jr nz,.nohalt
		halt
.nohalt
		djnz .loop
		ld a,(discolor)
		add 0b00001000
		and 0b00111000
		ld (discolor),a
		jp Dissolve8

discolor	
		db 0b00001000

[patters]

I did always wonder how these were done, so yes I will have to muddle my way through this.

[MustardTiger]

Yeah. Spin always hangs after recording a GIF so consider yourself lucky

I only remembered to whack up the emulator speed to 500% after a bit... BASIC sucks etc.

I love the ones that look like liquid falling down the screen.

[ParadigmShifter]

I've had this tatty old photocopy of an old Dr Dobbs article for decades which had a really nice way of doing digital dissolves. I found an online copy of it here https://archive.org/details/1986-11-dr- ... 8/mode/2up

It's the Galois LFSR which is on the wikipedia page in the WOS thread, but the article above has all the masks for each size of sequence which is great.

I coded up an attribute dissolve, I think it looks fairly random.



This is my code for 8 and 16 bit versions.

Code: Select all

; https://archive.org/details/1986-11-dr-dobbs-journal/page/48/mode/2up

Dissolve16
		ld de,1			;initial value
		ld hl,#240		;mask
		ld bc,1024
.loop	
		srl d			;value = value >> 1
		rr e
		jr nc,.noxor	;if carry clear, no xor
		ld a,d
		xor h			;value = value xor mask
		ld d,a
		ld a,e
		xor l
		ld e,a
.noxor
		ld a,d			;if value >= 0x300 don't draw
		cp #3
		jr nc,.nodraw

		push hl
		ld hl,#5800		;attribute address
		add hl,de		;add value
		ld a,(discolor)	;set to current color
		ld (hl),a	
		pop hl	

		ld a,c			;slow down effect, halt every 15 blocks
		and 15
		jr nz,.nohalt
		halt
.nohalt

.nodraw
		dec bc
		ld a,b
		or c
		jr nz,.loop

		ld a,(discolor)	;increment color
		add 0b00001000
		and 0b00111000
		ld (discolor),a
		jp Dissolve16


Dissolve8
		ld e,1
		ld d,#b8

		ld b,0
.loop
		ld a,e
		srl a
		jr nc,.noxor1
		xor d
.noxor1	ld e,a
		ld h,#58
		ld l,e
		ld a,(discolor)
		ld (hl),a

		ld a,b
		and 7
		jr nz,.nohalt
		halt
.nohalt
		djnz .loop
		ld a,(discolor)
		add 0b00001000
		and 0b00111000
		ld (discolor),a
		jp Dissolve8

discolor	
		db 0b00001000

That's very good and the code is tiny! Nice one.

[ParadigmShifter]

The theory isn't hard anyway. If x(n) is an LCG defined by

x(n+1) = (a*x(n) + c) mod m

and m is not a prime number (prime number case is already well known) then this produces a sequence of length m with no repeats if and only if

1. m and c are coprime. You can get a list of coprime integers to any number from WolframAlpha (you have to keep hitting the "more" button though which is a bit annoying, you only care about 0 < c < m

e.g.

https://www.wolframalpha.com/input?i=in ... ime+to+432

2. (a-1) must be divisible by all prime factors of m. So if m is of the form p1^a1 * p2^a2 * ... * pn^an (e.g. 432 = 2^4 * 3^3) so (a-1) needs to be divisible by p1, ... pn) (so 2 and 3 in the case of m = 432, the powers of the primes does not matter - although a large number of prime powers is better) i.e. (a-1) is divisible by 6 => a is of the form 1 + 6*n for the case m = 432 (but see part 3 also for an extra condition in this case)

https://www.wolframalpha.com/input?i=factorize+432

3. If m is divisible by 4 then (a-1) must be divisible by 4 too. 432 is divisible by 4 so (a-1) also needs to be divisible by 4... which makes 1+6n not good enough, since 6 is not divisible by 4, so we need to correct a to be of the form 1+12n instead. Note I limited a to be suitable for 16 bit multiply but that's not required, you can limit a to be of the form 0 < a < m though since the sequences repeat when a is not in that range cos of the modulo arithmetic thing.

And that's it.

Also note (a*x + c) mod m = ((a*x mod m) + (c mod m)) mod m which is why you only need to consider 0 < c < m and also 0 < a < m.

Note a and c are dependent on the properties of m (in particular its prime factorisation).

That explains the big list in the DATA statement of numbers < 432 coprime to 432, and the STEP 12 in the loop variable. Only other variable is the initial value which I chose as 432 - 1 since it made the bottom right corner always be visited last (for some reason I don't fully understand lol)

[ParadigmShifter]

I think the Galois thingio is probs the way to go (no multiplies required, just XOR) but I don't think there's as much control over the parameters you pick since I couldn't find a similar theorem to Hull-Dobell for that.

Probably best to pick a few decent parameters for the Galois one if you want variety (and changing initial value gives a different starting point of the sequence) and manually code in other effects (like a random drip effect/diagonal swipe/spiral etc.) as alternatives.

I coded a drip style thing for a matrix intro (letters falling down screen) and that was easy (you just store the current offset per column and pick a column at random and bump the offset down 1 cell).

EDIT: Result of that here, was going to use this as the intro screen to SJOE but removed it for some reason? Bit of tearing you don't notice since it updates as fast as possible without VSync. This just uses 8 columns though (1 4 letter word per column)



Max respect to Galois anyway (he didn't invent any of this but he did study finite fields of which XOR shift is an implementation of - it's basically a vector space over the finite field {0, 1}). He had a good excuse though (too busy revolutionising modern mathematics with his Galois theory and dying in a duel aged 21).

[ParadigmShifter]

I've had this tatty old photocopy of an old Dr Dobbs article for decades which had a really nice way of doing digital dissolves. I found an online copy of it here https://archive.org/details/1986-11-dr- ... 8/mode/2up

It's the Galois LFSR which is on the wikipedia page in the WOS thread, but the article above has all the masks for each size of sequence which is great.

I coded up an attribute dissolve, I think it looks fairly random.



This is my code for 8 and 16 bit versions.

Code: Select all

; https://archive.org/details/1986-11-dr-dobbs-journal/page/48/mode/2up

Dissolve16
		ld de,1			;initial value
		ld hl,#240		;mask
		ld bc,1024
.loop	
		srl d			;value = value >> 1
		rr e
		jr nc,.noxor	;if carry clear, no xor
		ld a,d
		xor h			;value = value xor mask
		ld d,a
		ld a,e
		xor l
		ld e,a
.noxor
		ld a,d			;if value >= 0x300 don't draw
		cp #3
		jr nc,.nodraw

		push hl
		ld hl,#5800		;attribute address
		add hl,de		;add value
		ld a,(discolor)	;set to current color
		ld (hl),a	
		pop hl	

		ld a,c			;slow down effect, halt every 15 blocks
		and 15
		jr nz,.nohalt
		halt
.nohalt

.nodraw
		dec bc
		ld a,b
		or c
		jr nz,.loop

		ld a,(discolor)	;increment color
		add 0b00001000
		and 0b00111000
		ld (discolor),a
		jp Dissolve16


Dissolve8
		ld e,1
		ld d,#b8

		ld b,0
.loop
		ld a,e
		srl a
		jr nc,.noxor1
		xor d
.noxor1	ld e,a
		ld h,#58
		ld l,e
		ld a,(discolor)
		ld (hl),a

		ld a,b
		and 7
		jr nz,.nohalt
		halt
.nohalt
		djnz .loop
		ld a,(discolor)
		add 0b00001000
		and 0b00111000
		ld (discolor),a
		jp Dissolve8

discolor	
		db 0b00001000

I've just noticed your routine does not visit cell 0 = (0, 0)... you can map 768 to 0 if you want (that's probably more efficient than subtracting 1 from the result, since you can just do an AND ~3 of the high byte)

[ParadigmShifter]

Rejinked & simplified my code for 768 attribs so full screen

Code: Select all

10 OUT 254,2
20 DEF FN m(a,b)=a-INT (a/b)*b: REM FN m(a,b) = a MOD b
30 LET k=INT (RND*768): IF FN m(k,2)=0 OR FN m(k,3)=0 THEN GO TO 30: REM pick random number 0 < k < 768 that is coprime to 768
40 FOR i=1 TO 768 STEP 12: PRINT AT 0,0;i;" ";k
50 LET a=INT (RND*768): FOR f=1 TO 768: LET a=FN m(a*i+k,768): POKE 22528+a,0: NEXT f
60 OUT 254, 4: PAUSE 0: CLS : OUT 254,2: NEXT i
70 GO TO 30

Also replaced massive DATA statement with a simple divisibility by 2 or 3 check. (divisible by 2 or 3 => not coprime to 768 = 2^8 * 3)

Obviously it helped that 768 and 432 both have the same prime factors (2 and 3) so I didn't need to update the FOR ... STEP 12 bit much (I just changed the upper bound so it goes through all i = 1 + 12n <= 768). Different prime factors would mean different STEP values. Also no need to do a divide and a modulo to convert index into row, column

Still fastest (method, not code - I'm not a BASIC wonk) in pure ZX BASIC I think, but GLFSR method is better for ASM cos no multiply or modulo required. (No rolls or XOR in basic sadly).

[ParadigmShifter]

New GIF... whacked up to 500% speed a bit earlier this time

[DoctorRad]

I've had this tatty old photocopy of an old Dr Dobbs article for decades which had a really nice way of doing digital dissolves. I found an online copy of it here https://archive.org/details/1986-11-dr- ... 8/mode/2up

Thanks, very interesting. One thing I'm not getting - maybe it's an old dialect of C? - is how the following code snippet includes an XOR operator? Shouldn't there be a '^' in there somewhere?

Code: Select all

element = (element >> 1) mask;

[ParadigmShifter]

Looks like a typo/misprint. It's definitely not old (K&R) C (which is the variant that preceded ANSI C). ANSI added (optional) function prototypes and such.

I can't see the article My browser or ISP doesn't like it... do you know what issue it was from I can probably find it on another site then?

Wikipedia page about GLFSR

https://en.wikipedia.org/wiki/Linear-fe ... lois_LFSRs

[MustardTiger]

Yeah, should be element = (element >> 1) ^ mask; I guess their typewriters didn't have the xor symbol

I've also realised there's more than the three pages I originally photocopied in the full article.

[ParadigmShifter]

C has totally got that covered, although looks like it is now optional for C++17

https://learn.microsoft.com/en-us/cpp/c ... w=msvc-170

Code: Select all

#define XOR ??'

should work if you have a keyboard with no ^ symbol

[DoctorRad]

I can't see the article My browser or ISP doesn't like it...

I made a copy on my OneDrive.