A Universal FRACTRAN Interpreter in FRACTRAN

A Universal FRACTRAN Interpreter in FRACTRAN

Chris Lomont, May 1, 2017


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]

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

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.

LZCL: An embedded compression library

LZCL: An embedded compression library

Copyright Chris Lomont, Sept 2016
Version 1.0


See my Compression Notes article for compression background on useful for this article. The README at the GitHub page has usage details .

For a recent project, I needed to design a low resource compression scheme. Over the years I’ve designed many, and this time I decided to unify some code, clean it up, and make some tools to ease development of such algorithms (mostly for my own use). The result this particular time is several very low memory decoders, necessarily slow, including Huffman, Arithmetic, LZ77, and my own new invention, LZCL, which outperforms the others quite well. All are designed for minimal RAM usage.