4-bit random numbers

January 20, 2011

While I accept that a toy 4-bit microprocessor probably isn’t a subject that warrant multiple posts, I’m unable to resist. Apologies.

After playing with my GMC-4 for a couple of days, the initial novelty of hand assembling programs had well and truly worn off, so I turned to the assembler and simulator available on the web. After a couple of minutes of use though, it was obvious that a simulator wasn’t at all what I wanted.

After all, if I wanted to type in a program nibble by nibble, I may as well do it on the hardware itself. What I really wanted was an integrated assembler and debugger. Luckily, the instruction set is very basic, so it didn’t take very long to put one together:

The left pane is the source window. The three columns on the right show the contents of memory; program memory is shown in Wheat & Cornsilk, data memory in DarkSeaGreen & PaleGreen, the current instruction is highlighted in DarkRed. The colouring is intended to make it easier to follow through the code when typing in the machine code on the hardware.

The jumble of text below the memory view shows the state of the eight registers, the status flag (see my previous post), program counter, seven-segment display and binary LEDs. There are buttons for copying the contents of memory to the clipboard, running the program, single-stepping and finally simultaneously compiling the source and resetting the state of the machine. The bottom panel shows any exceptions that might get thrown by the assembler or emulator (I didn’t bother to spend much time on error handling).

The reason op-codes are still shown for data memory is that (aside from addressable ranges) the GMC-4 makes no distinction between code and data memory. The neat thing about this is that the hardware has no problems executing code that lives in data memory; it also doesn’t mind if those instructions get modified during program execution, which means… self-modifying code! I’ve not found a way to make reasonable use of this, but it’s kind of cool nevertheless.

In the unlikely event that anyone’s interested, I’ve shoved the code up on Google. It’s written in Good Ol’ WinForms, as my fleeting love affair with WPF ended once I decided that I’d rather be productive than fashionable.

For one of the “games” I wrote, I needed a random number generator. Unfortunately, with 4-bit addition and subtraction my only available mathematical operations, it wasn’t immediately obvious how to go about it.

A bit of searching around led inevitably to Wikipedia and multiply-with-carry random number generators. I went with lag-1 MWC for simplicity, which is defined as:

x_n = (ax_{n-1}+c_{n-1})\,mod\,b
c_n = \lfloor\frac{ax_{n-1}+c_{n-1}}{b}\rfloor

Being limited to 4-bit numbers, a natural choice for b was 16 and a quick exhaustive search for a showed that a value of 15 yielded the sequence with the longest period (around 120) and distribution of numbers that wasn’t wholly intolerable (it at least covered all the digits). As an added bonus, using these values for a and b meant that the multiplications and divisions could be done away with completely:

x_n = (15x_{n-1}+c_{n-1})\,mod\,16
x_n = 1 + \tilde{x}_{n-1} + c_{n-1}

c_n = \lfloor\frac{15x_{n-1}+c_{n-1}}{16}\rfloor
c_n = \begin{cases} x_{n-1}-1, & c_{n-1} < x_{n-1} \\ x_{n-1}, & otherwise \end{cases}

That crappy little tilde above the x is meant to represent a bitwise not – my LaTeX is pretty weak I’m afraid.

4-bit random number generation is not exactly a widely discussed topic on the internet, so I don’t know if there’s a better method. This worked well enough for my purposes though. Quality wise, it’s probably on par with RANDU.


5 Responses to “4-bit random numbers”

  1. Paul Says:

    Thanks for that. I’m writing TMS1000 Code for an MB Simon toy at the moment (possibly more bonkers than the GMC-4 !) but I couldn’t use key press time randomisers because of the emulators underlying OS 😦 That’s a nice little randomiser for so little code.

    I have a GMC-4 too. I find it concentrates the mind wonderfully development wise writing this stuff, modern systems allow a very lackadaiscal approach to things like memory.

  2. Hi Tom and Paul
    Like your comments on GMC-4 assembly code for TMS1000. I would like to know if you have been able to dump code from a TMS1000. I have a TMS1000 in a model railroad train controller which I would like to dump.
    Catch me on swchuck at gmail dot com
    Charles Harris

  3. Hi Tom
    I have not made any progress on this project. Anything new on your project re TMS1000 ?

    In the comments on that page ‘Paul’ has commented re TMS1000 coding for Simon. How do I find a contact for Paul ?

    Thanks and regards
    Charles Harris

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: