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:
- 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]:
double value = ((double)rand())/(RAND_MAX);
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
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:
uint32_t x = ...
// common method
if ((x%5) == 0)
// do something
// cheaper method, completely equivalent
if (x * 3435973837U <= 858993459U)
\\ do something
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.
Efficient divisibility testing full post
(595 words, estimated 2:23 mins reading time)
LZCL: An embedded compression library
Copyright Chris Lomont, Sept 2016
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.
Coming soon (as soon as I get this parser working!)
Permanent link to this post
(11 words, estimated 3 secs reading time)