Robotron 2084 Disassembly

It’s been a few years since I worked on my Robotron 2084 disassembly, but I’ve recently gotten the bug to modify my machine, so today I finished a decent portion of the disassembly. I needed the ability to assemble the code, and nothing would work with the output that IDAPro generates, so I wrote my own 6800/6809 assembler that handles the format.

I added the 6800 portion for handling the Williams Sound Board rom.

I posted the source for the assembler at https://github.com/ChrisLomont/CLAsmTool.

A Universal FRACTRAN Interpreter in FRACTRAN

Chris Lomont, May 1, 2017

Introduction

FRACTRAN is a Turing-complete esoteric programming language invented by the prolific mathematician John Conway in 1972 [Con72, Con87].

From Wikipedia (with slight edits):

A FRACTRAN program is an ordered list of positive (reduced) fractions together with an initial positive integer input s. The program is run by updating the integer s (which I call the state of the program) as follows:

1. for the first fraction f in the list for which sf is an integer, replace s by sf.

Generating Uniform Random Numbers on [0,1]

Chris Lomont, March 2017

Common advice for generating uniform random numbers in [0,1] in many languages looks like this [1,2,3]:

This however does not generate many possible floating-point numbers in $[0,1]$, leaving gaps – there are many floating-point numbers that should occur but cannot due to this method. To understand why, you need to understand how floating-point numbers are (usually) stored on computers.

Throughout we’ll assume the random number generators produce uniformly random integers in a known range.

Efficient divisibility testing

The example

Here is a low computational cost method to test if an integer $x$ is divisible by another integer $d$, useful in C-like languages (assembly included). It replaces a possibly costly modulus % operation with a usually lower cost multiplication *.

Here is an example illustrating the method for divisibility by 5:

What trickery is this? How does it work? Where do the constants 3435973837U and 858993459U come from?

Note the magic numbers depend on the type of $x$. The above example requires $x$ is an unsigned 32 bit integer, and the language has multiplication overflow computed modulus 32. Many common languages (C,C++,C#,Java, ..) do this.