A few years ago when Builderboy wrote his fire graphics turorial, I remember thinking it was super cool and I went on to make my own fire engines designed around it. However, one thing always peeved me-- the design was very clever and made for speed, but it seemed too artificial for my liking-- particularly in the way it masked out pixels.

The idea was to kill a pixel 1/8 of the time, so a PRNG was used to select from one of the following masks:
%01111111
%10111111
%11011111
%11101111
%11110111
%11111011
%11111101
%11111110
Of course an AND mask will kill one bit in a byte, so exactly 1/8 of the pixels in a byte. A few weeks ago, this was bugging me and preventing my sleep. I set out to devise an algorithm that would generate masks that didn't necessarily have a 1/8 kill rate, but over time the probability converges to 1/8. For example, one mask might be %11111111 (0% killed) and the next could be %10110111 (25% killed).

The Idea
Suppose you 3 random bits and you OR them together. The only way this can result in a 0 is if every input was a 0. The probability of that happening is .5^3 = .125 = 1/8. So for our fire mask, we can generate three random bytes, OR them together, and each bit has a 1/8 chance of being reset.
Speed
The disadvantage here is in speed. Builderboy's method requires one pseudo-random number, this method requires three. However, if we consider that we are almost certainly going to use a fast pseudo-random number generator, and that we will want a long (ish) period, we have room to take advantage of the PRNG and achieve almost the same speed. For example, suppose you generate a 24-bit pseudo-random number-- with this method, you can just OR the three bytes generated (12cc) versus using an LUT (Builder's method):
ld hl,LUT
and 7
add a,l
ld l,a
jr nc,$+3
inc hl
ld a,(hl)
;43cc
In the example code I will give, I use a 16-bit PRNG, so I generate three of these numbers (6 8-bit values) for 2 masks, making generation take 1.5 times longer than Builder's as opposed to 3 times as long.
Considerations
In order for this to work, you need an RNG or PRNG in which every bit has a 50% chance of being set or reset. I went with a Lehmer LCG that was fast to compute and had a period of 2^16 and had this property.
Example
The following code works at 6MHz or 15MHz and the LCD will provide almost no bottleneck. Sorry, no screenie:
smc = 1    ;1 for SMC, 0 for no SMC (use 1 if code is in RAM; it's faster)
plotSScreen = 9340h
saveSScreen = 86ECh


;==============================
#IF smc = 0
seed = saveSScreen
#ENDIF
;==============================



.db $BB,$6D
.org $9D95
fire:
;;first, set up. We will be writing bytes to the LCD left to right then down
    di
    ld a,7      ;LCD y-increment
    out (16),a
;;setup the keyboard port to read keys [Enter]...[Clear]
    ld a,%11111101
    out (1),a
;make the bottom row of pixel;s black to feed the flames
    ld hl,plotSScreen+756
    ld bc,$0CFF
    ld (hl),c \ inc hl \ djnz $-2
fireloopmain:
    ld ix,plotSScreen+12
    in a,(1)
    and %01000000
    ret z
    call LCG
    ld b,63
fireloop:
;wait for LCD delay
    in a,(16)
    rla
    jr c,$-3
    ld a,80h+63
    sub b
    out (16),a
    push bc
    call LCG
    ld a,20h
    out (16),a
    call fire_2bytes+3
    call fire_2bytes
    call fire_2bytes
    call fire_2bytes
    call fire_2bytes
    call fire_2bytes
    pop bc
    djnz fireloop
    jp fireloopmain   
fire_2bytes:
    call lcg
    push hl
    call lcg
    pop de
    ld a,e
    or d
    or l
    and (ix)
    out (17),a
    ld (ix-12),a
    inc ix
    push hl
    call lcg
    pop af
    or h
    or l
    and (ix)
    out (17),a
    ld (ix-12),a
    inc ix
    ret
lcg:
;240cc or 241cc, condition dependent (-6cc using SMC)
;;uses the Lehmer RNG used by the Sinclair ZX81
#IF SMC = 1
seed = $+1
    ld hl,1
#ELSE
    ld hl,(seed)
#ENDIF
;multiply by 75
    ld c,l
    ld b,h
    xor a
    ld d,a
    adc hl,hl
    jr nz,$+9
    ld hl,-74
    ld (seed),hl
    ret
    rla
    add hl,hl \ rla
    add hl,hl \ rla \ add hl,bc \ adc a,d
    add hl,hl \ rla
    add hl,hl \ rla \ add hl,bc \ adc a,d
    add hl,hl \ rla \ add hl,bc \ adc a,d
;mod by 2^16 + 1 (a prime)
;current form is A*2^16+HL
;need:
;  (A*2^16+HL) mod (2^16+1)
;add 0 as +1-1
;  (A*(2^16+1-1)+HL) mod (2^16+1)
;distribute
;  (A*(2^16+1)-A+HL) mod (2^16+1)
;A*(2^16+1) mod 2^16+1 = 0, so remove
;  (-A+HL) mod (2^16+1)
;Oh hey, that's easy! :P
;I use this trick everywhere, you should, too.
    ld e,a
    sbc hl,de       ;No need to reset the c flag since it is already
    jr nc,$+3
    inc hl
    ld (seed),hl
    ret
EDIT: .gif attatched. It looks slower in the screenshot than my actual calc, though.
EDIT2: On my actual calc, it is roughly 17.2FPS