Algorithmic composition with Langton’s Ant

Langton’s Ant is a simulation in two dimensions which has been proven to be a universal Turing machine – it can in principal be used to compute anything computable by a computer.

The simulation consists of an infinite board of either squares which can be either white or black. Now, an “ant” walks around the board. If the ant lands on a white square, it turns right, flips the color of the square and moves forward. If the square is black, the ant turns left, flips the color of the square and moves forward.

When visualised, the behaviour of this system changes over time from structured and simple to completely chaotic. However, the system is completely deterministic, determined only by the starting state.

In the video above, a simulation with two ants runs over 500 steps, and every time a square flips from black to white, a note is played. The note to be played is determined as follows:

  • The board is divided into 7×7 sub-boards of 49 squares.
  • These squares are enumerated from the bottom reading each row from left ro right from 0 to 48.
  • When a square is flipped from black to white, the number assigned to the square determines the note as the number of semitones above A1.

Seven is chosen as the width of the sub-squares because it is the number of semitones in a fifth, so the ants moves either chromatically (horizontally) or by fifths (vertically). In the beginning, the are moving independently and very structured, but when their paths meet, a more complex, chaotic behaviour emerges.

Ruffini – abstract algebra in Java

Class inheritance and generics/templates makes it possible to write code with nice abstractions very similar to the abstractions used in math, particularly in abstract algebra, where a computation can be described for an entire class of algebraic structures sharing some similar properties (eg. groups and rings). This has been described nicely in the book “From Mathematics to Generic Programming” by Alexandra A. Stepanov and Daniel E. Rose.

Inspired by this book, I have implemented a library for computations on algebraic structures called Ruffini using Java generics to get the same kind of abstraction that is used in abstract algebra, eg. that you do not specify what specific algebraic structure is used, only that is eg. a group or a ring.

Abstract algebraic structures are defined by a number of interfaces extending each other, the simplest being a semigroup:

public interface Semigroup<E> {

  /**
   * Return the result of the product <i>ab</i> in this 
   * semigroup.
   * 
   * @param a
   * @param b
   * @return
   */
  public E multiply(E a, E b);

}

The semigroup is extended by a monoid interface which adds a getIdentity() method and by a group interface which adds an invert(E) method etc. Continuing like this we get end up with interfaces for more complicated structures like rings, fields and vector spaces.

Now, each of these interfaces describes functions that can be applied to a generic type E (eg. that given two instances of E, the multiply method above returns a new instance of type E). As in abstract algebra, these functions can be used to describe complicated computations without specifying exactly what algebraic structure is being used.

Ruffini currently implements a number of algorithms that is defined and described for the abstract structures, including the discrete Fourier transform, the Euclidean algorithm, Gröbner bases, the Gram-Schmidt process and Gaussian elimination. The abstraction makes it possible to write the algorithms only once, while still being usable on any of the algebraic structures defined in the library, including integers, rational numbers, integers modulo n, finite fields, polynomial rings and matrix rings. Below is the code for the Gram-Schmidt process:

public List<V> apply(List<V> vectors) {
  List<V> U = new ArrayList<>();

  Projection<V, S> projection = new Projection<>(vectorSpace, innerProduct);
  for (V v : vectors) {
    for (V u : U) {
      V p = projection.apply(v, u);
      v = vectorSpace.subtract(v, p);
    }
    U.add(v);
  }
  return U;
}

Here V and S are the generic types for resp. the vectors and scalars of the underlying vector space, and Projection is a class defining projection given a specific vector space and an inner product. Note that the vector space has a subtract method which subtracts two vectors. Now, the above algorithm can be executed on any of the vector spaces defined in Ruffini.

The library is can be downloaded from GitHub: https://github.com/jonas-lj/Ruffini.

Solving the 0-1 Knapsack problem with Excel

Given a list of items each with a value and a weight, the Knapsack problem seeks to find the set of items with the largest combined value within a given weight limit. There are a nice dynamic programming solution which I decided to implement in a spread sheet. I used Google Sheets but the solution is exported as an excel-sheet.

The solution builds a Knapsack table for round 0,1,…,limit. In each round r the solution for the problem with limit r is constructed as a column in the table, so the table has to be as wide as the maximum limit. Once the table is built, the solution can be found using backtracking. This is all described pretty well on Wikipedia, https://en.wikipedia.org/wiki/Knapsack_problem#0/1_knapsack_problem.

The main challenge was to translate this algorithm from procedural pseudocode to a spreadsheet. Building the table is simple enough (once you learn the OFFSET command in Excel which allows you to add or subtract a variable number of rows and columns from a given position), but the backtracking was a bit more tricky.

Assuming that the weights are stored in column A from row 3 and the corresponding values are stored in column B, the table starts in column D. The round numbers are stored in row 1 from columnD. Row 2 are just 0’s and all other entries are (the one below is from D3):

=IF($A3>D$1; D2; MAX(D2; OFFSET(INDIRECT(ADDRESS(ROW(); COLUMN()));-1;-$A3) + $B3))

The table stops after round 40, so we find the solution with weight at most 40.

The backtracking to find the actual solution after building the table is done in column AT and AU. In the first column, the number of weight spent after 40 rounds are calculated from bottom to top row using the formula (from AT3):

=IF(OFFSET(INDIRECT(ADDRESS(ROW(); COLUMN()));0;-AT23-2) <> OFFSET(INDIRECT(ADDRESS(ROW(); COLUMN()));-1;-AT23-2); A22 + AT23; AT23)

The solution is shown in column AU where for each row we simply check if the accumulated weight increased with this item.

Gram-Schmidt process for integers

Given a set of linearly independent vectors, the Gram-Schmidt process produces a new set of vectors spanning the same subset, but the new set of vectors are now mutually orthogonal. The algorithm is usually stated as working over a vector space, but will in this post be altered to work over a module which is a vector space where the scalars are elements in a ring instead of a field. This could for instance be the case if we are given a set of integer vectors we wish to orthogonalise.

The original version can be described as follows: Given a set of vectors \(v_1, \ldots, v_n\) we define \(u_1 = v_1\) and

\(u_k = v_k – \text{proj}_{u_1}(v_k) – \text{proj}_{u_2}(v_k) – \cdots – \text{proj}_{u_{k-1}}(v_k)\)

for \(k = 2,3,\ldots,n\). The projection operator is defined as

\(\text{proj}_u(v) = \frac{\langle u, v \rangle}{\langle u, u \rangle} u\).

If we say that all \(v_i\) have integer entries, we see that \(u_i\) must have rational entries, and simply scaling each vector with a multiple of all the denominators of the entries will give a vector parallel to the original vector but with integer entries. But what if we are interested in an algorithm that can only represent integers?

The algorithm is presented below. Note that the algorithm works over any module with inner product (aka a Hilbert Module).

# Given: Set of vectors V.
# Returns: A set of mutually orthogonal vectors spanning 
# the same subspace as the vectors in V.

U := Ø
k := 1

while V ≠ Ø do
  poll vector v from V
  w := kv

  for (u,m) in U do
    w -= m〈v,u〉u
  
  # Optional: Divide all entries in w by gcd of entries

  if V ≠ Ø do
    n :=〈w,w〉
    for (u,m) in U do
      m *= n
    Put (w,k) in U
    k *= n
  else do
    # No more iterations after this one
    Put (w,k) in U

return first coordinates of elements in U

When used on integers, the entries in the vectors grow very fast, but this may be avoided by dividing \(w\) by the greatest common divisor of the entries.

DIY preamp for Leslie 760

I have recently bought a used Leslie 760 amplifier, but unfortunately it came without the pedal used to change the speed of the rotator and which also acts as preamp. A used pedal and the necessary cables is priced at about €400 so I decided to build one myself.

Luckily, some nice people has posted scanned versions of the old manuals for Leslie amps and put them online: http://www.captain-foldback.com/Leslie_sub/leslie_manuals.htm.

The amplifier does not have a normal jack-plug for connection with an instrument but has instead a 9-pole plug. At first glance, this seems a bit confusing, but it is quite simple: Pole 1 is ground and pole 2 is sound input. The rotator is activated by grounding pole 6 (slow) or pole 7 (fast).

With this information it was easy to build everything I needed: I built a small box with room for two jack plugs to be put on the amp. The first plug is mono for instrument connection, and is attached to pole 1 and 2. The other plug is for stereo which is connected to pole 6 and 7 (and ground). At the other end of this stereo cable I attached a switch pedal with two buttons: One for switching between grounding the two poles of the stereo jack and another for switching the connection on/off. I got everything for about €25 on musik-ding.de.

I still needed a preamp and found one by the brand ‘Art’ at 4Sound.dk for €35, so for about 60€ I got everything I needed to run the amp.

You are more than welcome to write me at mail@jonaslindstrom.dk if you have any questions.