Papers, etc.

What's in the Paper

Although it includes technical details, the paper is written to be accessible to a broad audience.

The paper

• Articulates in detail the desirable properties of a random number generator including performance, correctness, uniformity, and unpredictability, as well as sound mathematical grounding. It also describes some less well-known desirable features, such as k-dimensional equidistribution and seekability (a.k.a. jump-ahead).
• Describes a new permutation technique, founded on the idea of permutation functions on tuples, that can dramatically improve the output quality of a medium-quality random number generator while preserving important qualities such as uniformity.
• Develops a new random number generation technique, using a base RNG with weak statistical properties but other desirable ones (specifically, a linear congruential generator) combined with an output function based on permutation functions on tuples.

The name for the family, PCG, stands for permuted congruential generator, combining both concepts that underly the generation scheme, namely permutation functions on tuples and a base linear congruential generator.

In addition to describing the PCG family, the paper also assesses its performance. To further that goal, the paper

• Develops a model for the performance of an ideal uniform random number generator with b bits of state, including the notion of the point at which such a generator becomes overtaxed and the constraints of uniformity make it unable to deliver truly random behavior.
• Determines an approximation of the point at which any uniform generator, even an ideal one, could be expected to fail TestU01's statistical tests.
• Presents a new way to contrast the statistical performance of different random number generation schemes capturing the concept of headroom to pass more stringent tests in the future.
• Uses the above statistical-performance comparison scheme, as well as time and space performance, to contrast PCG generators with existing ones.

Check out pcg-random.org for details on the PCG family of random number generators which provides a combination of features rarely seen on existing generators.

What's in the Paper

For more than 30 years, people used the following example to show the elegance of functional programming:

primes = sieve [2..]
sieve (p : xs) = p : sieve [x | x <− xs, x ‘mod‘ p > 0]

People claimed that this code showed the Sieve of Eratosthenes; unfortunately however, it isn't that algorithm.

This paper shows

• Why this widely-seen implementation is not the Sieve of Eratosthenes (and is in fact an inefficient implementation of trial division);
• How an algorithm that is the Sieve of Eratosthenes may be written in a lazy functional style; and
• How our choice of data structure matters.

It also analyses time complexity of prime-finding methods described.

What's in the Paper?

This paper is about some of the techniques I apply when teaching. The basic idea is that teachers also need to be applied psychologists, because our classrooms are a minefield of subtle influences. When we design classes, we can take account of framing effects and use them to create a better classroom experience.

What's in the Paper?

The field of generic programming often struggles with the problem of avoiding invalid programs. This paper shows that combinator expressions are a useful program representation for genetic programming, because they provide the expressive power of high-level strongly-typed functional programming languages while avoiding the problems of variables by eliminating them. Specifically, it shows that

• Combinator expressions can represent programs that introduce local variables, but the genetic operators to manipulate combinator expressions do not require special cases for variables;
• Generating combinator expressions is efficient compared to prior work on several problems (including even parity on N inputs, and devising representations and implementations for stacks and queues);
• Sometimes exhaustive enumeration of all possible programs is competitive with genetic programming; and,
• Some purportedly difficult GP problems become trivial to solve with exhaustive enumeration, given the constraints of types and well-formed programs.

What is OCM?

Observationally Cooperative Multithreading (OCM) is a new approach to shared-memory parallelism. It addresses a key problem of mainstream concurrency control mechanisms—they can be prohibitively hard to reason about and debug. Programmers using OCM simply write code as if they were using the cooperative multithreading model (CM) for uniprocessors. The underlying OCM implementation then optimizes execution—running threads in parallel when possible - in such a way that the results are consistent with CM. In addition to providing easier reasoning and debugging, OCM is also highly adaptable in terms of its underlying concurrency-control mechanism. Programmers using OCM have the capability to take a finished program and choose the strategy (e.g., locks or transactions) that provides optimal performance.