Generating Randomness: LCG and LFSR on Commodore 64 and PicoCalc

By Michael Doornbos

- 7 minutes read - 1422 words

Recap

We’ve scracted a few of the concepts we’ll talk about today in the past.

We’ve had:

  • TK
  • TK
  • TK

Generating Randomness: LCG and LFSR on Commodore 64 and PicoCalc

Ever wondered how your favorite retro games managed to keep you guessing? Picture this: you’re dodging pixelated invaders in Space Invaders or charting unknown star systems in Elite, and every twist feels fresh, unpredictable—like the machine’s got a mind of its own. Back in the 8-bit era, though, there was no fancy random number chip tucked inside your Commodore 64. Nope, it was all down to clever coders wielding algorithms like the Linear Congruential Generator (LCG) and the Linear Feedback Shift Register (LFSR)—two unsung heroes of pseudo-random chaos.

Here at Imapenguin.com, we’re suckers for a good retro tech tale, so let’s take a trip back to Commodore BASIC’s quirky world, then fast-forward to the shiny present with MMBasic on the PicoCalc (that’s a Raspberry Pi Pico running BASIC, for the uninitiated). We’ll code up LCG and LFSR on both, explore what makes them tick, and even mash them together for some extra-random fun. Whether you’re a C64 diehard or a microcontroller newbie, grab your virtual tape drive—we’re diving into the wild world of pseudo-random number generation!

Understanding LCG and LFSR: The Basics of Chaos

Before we get our hands dirty with code, let’s meet the two main methods.

Linear Congruential Generator (LCG)

The LCG is like the reliable old pickup truck of random number generation. It churns out numbers with a simple formula:
X(n+1) = (A * X(n) + C) mod M

  • X(n) is your current number (starting with a “seed” you pick).
  • A is the multiplier, C is the increment, and M is the modulus—tweak these right, and you’ve got a decent sequence.
    It’s fast and easy, but it’s not perfect—those lower bits can get a bit predictable if you squint hard enough.

Linear Feedback Shift Register (LFSR)

The LFSR, meanwhile, is the punk rocker of the pair. It works at the bit level, shifting a binary number and tossing in some feedback via an XOR operation on specific “tap” positions. A 16-bit LFSR with the right taps can crank out 2^16 - 1 = 65,535 unique steps before looping. It’s lean, mean, and loves spitting out bit streams, though it’s less handy for big integers straight out of the box.

LCG vs. LFSR: The Showdown

  • Output: LCG hands you nice, chunky integers; LFSR gives you a drizzle of bits.
  • Speed: LFSR’s bit-twiddling is a champ on simple hardware.
  • Period: LFSR often stretches further for the same bit count.
  • Randomness: Both have quirks—LCG’s got some arithmetic patterns; LFSR’s taps can spill its secrets if you’re clever.

LCG in Commodore BASIC: Wrestling with the Retro Beast

Commodore BASIC—oh, how we love its oddball charm. But coding an LCG here? It’s like trying to cook a gourmet meal with a camping stove. No modulo operator, and integers max out at 32767. Let’s make it work anyway.

The Code

10 X=42 : REM OUR SEED, BECAUSE HITCHHIKER’S GUIDE SAYS SO
20 A=69069 : REM MULTIPLIER, A CLASSIC PICK
30 C=1 : REM INCREMENT, KEEPING IT SIMPLE
40 M=32768 : REM MODULUS, FITTING THE C64’S LIMITS
50 FOR I=1 TO 10
60 X=(A*X+C)-INT((A*X+C)/M)*M : REM POOR MAN’S MODULO
70 PRINT X
80 NEXT I

How It Works We kick off with a seed of 42 (because, why not?), a multiplier of 69069 (it’s got a good rep), and a modulus of 32768 to dodge overflow. No MOD? No problem—we fake it with (AX+C) - INT((AX+C)/M)*M. Run this, and you’ll see numbers like 13819, 14188, 14557 pop out—random enough for a dungeon generator or a dice roll in your next BASIC RPG.

LFSR in Commodore BASIC: Bit-Shifting Without the Bits

Now, LFSR on the C64. Here’s the catch: no bitwise operators. No AND, no XOR, no shifts. It’s like asking a penguin to fly—time to flap creatively.

The Code

10 R=1 : REM SEED, ANYTHING BUT ZERO
20 FOR I=1 TO 10
30 B=(R AND 1) : REM LSB, WE'LL PRETEND
40 T=((R AND 1)XOR(R AND 4)/4 XOR(R AND 8)/8 XOR(R AND 32)/32) : REM TAPS AT 16,14,13,11
50 R=INT(R/2)+(T*32768) : REM SHIFT RIGHT, FEEDBACK TO TOP
60 PRINT B; : REM SHOW THE BIT
70 NEXT I

How It Works

We start with a 16-bit register (R=1). Without AND, we mimic it—(R AND 1) is just the least significant bit, and (R AND 4)/4 checks bit 3. The feedback bit T comes from XORing taps at positions 16, 14, 13, and 11, faked with division. Shift right with INT(R/2), slap the feedback bit at the top, and you get a bit stream: 1, 0, 0, 0, 1—perfect for flipping coins in your retro game.

LCG in MMBasic for PicoCalc: Modern BASIC Bliss

Now, let’s jump to MMBasic on the PicoCalc. With a real modulo operator and 32-bit integers, it’s like upgrading from a tricycle to a sports car.

The Code

' LCG Implementation
X = 42          ' Seed, still 42
A = 1664525     ' Multiplier, Knuth's choice
C = 1013904223  ' Increment, big and bold
M = 2^32        ' Modulus, 4294967296

Print "LCG Output:"
For i = 1 To 10
  X = (A * X + C) MOD M
  Print X
Next i

How It Works

We’re rocking Knuth’s MMIX parameters here—big numbers, long periods. The MOD operator makes life sweet, and the Pico’s horsepower handles it all. Output? Think 701188840, 2831944757—big, juicy integers ready for anything from simulations to pixel art generators.

LFSR in MMBasic for PicoCalc: Bitwise Heaven

MMBasic’s bitwise operators turn LFSR into a walk in the park.

The Code

' LFSR Implementation
R = 1           ' Seed, non-zero
Print "LFSR Output (bits):"
For i = 1 To 10
  B = R AND 1   ' Grab the LSB
  T = (R AND 1) XOR ((R AND 4) >> 2) XOR ((R AND 8) >> 3) XOR ((R AND 32) >> 5)  ' Taps: 16,14,13,11
  R = (R >> 1) OR (T << 15)  ' Shift and feedback
  Print B;
Next i
Print

How It Works

With AND, », and OR, we’re in business. Tap positions 16, 14, 13, and 11 feed into an XOR dance, and the result gets shifted back into a 16-bit register. You’ll see bits like 1, 0, 0, 0, 1—same vibe as the C64, but oh-so-smooth.

Combining LCG and LFSR: Double the Fun

Why pick one when you can have both? Mixing LCG and LFSR boosts randomness and stretches the period—think of it as peanut butter and jelly for your PRNG.

Why Bother?

  • Randomness Boost: LCG’s patterns get scrambled by LFSR’s bit chaos.
  • Longer Loops: More steps before repetition.
  • Flexibility: Integers from LCG, binary spice from LFSR.

Commodore BASIC Combo

10 X=42 : A=69069 : C=1 : M=32768 : REM LCG SETUP
20 R=1 : REM LFSR SEED
30 FOR I=1 TO 5
40 X=(A*X+C)-INT((A*X+C)/M)*M : REM LCG STEP
50 T=((R AND 1)XOR(R AND 4)/4 XOR(R AND 8)/8 XOR(R AND 32)/32) : REM LFSR TAPS
60 R=INT(R/2)+(T*32768) : REM LFSR STEP
70 N=INT(X/32768*100)XOR INT(R/32768*100) : REM COMBINE TO 0-99
80 PRINT N
90 NEXT I

MMBasic Combo

' Hybrid LCG + LFSR
X = 42 : A = 1664525 : C = 1013904223 : M = 2^32  ' LCG setup
R = 1                                              ' LFSR seed
Print "Hybrid Output (0-99):"
For i = 1 To 5
  X = (A * X + C) MOD M                            ' LCG step
  T = (R AND 1) XOR ((R AND 4) >> 2) XOR ((R AND 8) >> 3) XOR ((R AND 32) >> 5)  ' LFSR taps
  R = (R >> 1) OR (T << 15)                       ' LFSR step
  N = Int(X / M * 100) XOR Int(R / 65536 * 100)   ' Combine, scale to 0-99
  Print N
Next i

How It Works

We run both generators side by side, scale their outputs to 0-99, and XOR them together. The result? A sequence that’s tougher to crack and livelier than either alone—great for a retro slot machine or a Pico-powered fortune teller.

Wrapping Up: From 8-Bit to Today

From the C64’s clunky quirks to the PicoCalc’s sleek power, LCG and LFSR prove that simplicity can still pack a punch. They’re the building blocks of randomness that fueled a generation of games and laid the groundwork for today’s cryptographic wizards. So, dust off that emulator or flash your Pico—play with the seeds, tweak the taps, and let chaos reign. Because in coding, as in life, a little randomness keeps things interesting.