Gilbert Strang is really the best teacher or didact I know. His course on linear algebra is - just great. He explains thinks like vectors, vector spaces, matrices, rank and dimension, kernel and null space, determinants, orthogonality, eigenvalues and eigenvectors, solving linear or differential equations and much more in simple yet very concise words. Even if the material is more advanced, I have to say that it’s much easier to understand than the mathematics I was taught by my teacher at high-school.

Any high-school teacher or anyone else starting to learn or teach linear algebra should watch Strangs recorded Video Lectures. They are a pleasure! His book, Introduction to Linear Algebra (or Lineare Algebra how the german translation is named) is a must-have, too. It contains a bunch of excersises and solutions. And even if it’s not always easy to solve them, it’s nevertheless fun!

The picture below is a shot from one of the video lectures. The topic of the lecture was on determinants. Prof. Strang commented the situation with the hangman with: "Okay, let’s execute the determinant" ;-)

I recommended the lectures to my friend and fellow student. Read his comments here (in German).

Here’s a Ruby implementation of the simple Haskell algorithm given on page 2 of An Unbounded Spigot Algorithm for the Digits of Pi.

def calc_pi
  q, r, t, k = 1, 0, 1, 1
  loop do
    n = (3*q+r) / t
    if (4*q+r) / t == n then
      yield n
      q, r, t, k = 10*q, 10*(r-n*t), t, k
    else
      q, r, t, k = q*k, q*(4*k+2)+r*(2*k+1), t*(2*k+1), k+1
    end
  end
end

calc_pi {|n| print n; $stdout.flush }

The algorithm generates an infinite number of the digits of Pi.

Today, I implemented Julia sets in Ruby and C. I first prototyped a Ruby version, then quickly recognized that it is simply too slow to generate larger images. So I translated it to C which resulted in a performance boost of factor 180!

Here’s the fractal created by the example.

The Ruby version is given below. It creates PNM bitmap files which can be viewed for example with display on Un*x.

Feel free to modify the parameters, especially c, rx and ry. And of course the colormap.

require "complex"

c = Complex(-0.75, 0.136)          # the Julia set parameter
iters = 50                         # max iterations
w, h = 400, 300                    # bitmap extents
rx, ry = -1.0 .. 1.0, -1.0 .. 1.0  # view area

sx = (rx.last - rx.first).abs / w  # x-scale
sy = (ry.last - ry.first).abs / h  # y-scale

colmap = Array.new(256, "\000"*3)  # color map

# initialize colormap
(1..255).each {|i| colmap[i] = [10+i*10, 0, rand*100].pack("CCC") }

# write PNM header
print "P6\n#{w} #{h}\n255\n"

# do the real stuff
for j in 0...h
  for i in 0...w
    n, zn = 0, Complex(sx*i+rx.first, sy*j+ry.first)
    while n <= iters
      # sequence runs away to infinity
      break if (zn-c).abs > 2

      # calculate next iteration
      zn = zn**2 + c; n += 1
    end

    # draw/print pixel
    print colmap[n]
  end
end

The same example written more compactly with only 228 bytes :-)

require"complex";c,m,w,h=Complex(-0.75,0.136),50,200,100;puts "P6\n#{w} #{h}\n255";(0...h).each{|j|(0...w).each{
|i|n,z=0,Complex(0.9*i/w,0.9*j/h);while n<=m&&(z-c).abs<=2;z=z*z+c;n+=1 end;print [20+n*10,0,rand*99].pack("C*")}}

Or on the command line:

ruby -rcomplex -e'c,m,w,h=Complex(-0.75,0.136),50,200,100;puts"P6\n#{w} #{h}\n255";(0...h).each{|j|(0...w).each{|i|n,\
z=0,Complex(0.9*i/w,0.9*j/h);while n<=m&&(z-c).abs<=2;z=z*z+c;n+=1 end;print [20+n*10,0,rand*99].pack("C*")}}'|display

This months editon (11/2003) of the German c’t magazin contains an article about Lindenmayer systems. I’ve read about them some years ago in an IBM science jounal, and implemented it afterwards in OCaml. Today I implemented them in Ruby.

Lindenmayer systems are similar to Markov or Semi-Thue systems (both are very simple text replacing systems), with the exception that at each production step, all matching rules are applied, whereas Markov or Semi-Thue systems apply only one rule at a time.

All three systems have in common that they have production rules and a start symbol. Markov systems further have special terminating rules (unlike Semi-Thue) and rules have a specific order in which they are tried (Semi-Thue systems may apply the rules in random order). Due to the specific order, Markov systems are deterministic, Semi-Thue usually not. A Markov system is incorrect if no more rules are applicable, it must terminate by explicitly "calling" the terminating rule (usually denoted as dot).

Here’s an example of a simple Markov system (or algorithm) that can substract two numbers:

|-| ::= -
|-  ::= .|
-|  ::= .-|
-   ::= `e
`e  ::= .`e

The `e denotes the empty symbol (epsilon), the dot marks a terminating rule. Read ::= as bebecomes or produces.

Applying the Markov algorithm onto the start symbol |-|| will lead to:

|-|| ==> -|   (rule 1)
-|   ==> -|   (rule 3)

You see that it correctly subtracts two from one, giving negative one (-|). You can even express any algorithm as Markov or Semi-Thue system, as they are Turing-complete.

During the Computer Science I reading, I wrote a Markov simulator, which is available here: raa.ruby-lang.org/list.rhtml?name=markov

Lindenmayer Systems

I told above that they are very similar to Markov systems, with the difference that at each step any matching rule is applied. Look at the following example which should clarify this (the second step is important):

Rules:
  F => (F+F)

Start symbol:
  F

Markov:
  1.  F     => (F+F)
  2.  (F+F) => ((F+F)+F)

Lindenmayer:
  1.  F     => (F+F)
  2.  (F+F) => ((F+F)+(F+F))

The subsitution step of a Lindenmayer system can be written in only a few lines of Ruby code:

class String
  def explode; scan(/./m) end
end

class Producer
  def initialize(rules)
    @rules = rules
  end

  def produce(str, n=1)
    n.times { str = str.explode.map {|s| @rules[s] || s}.to_s }
    str
  end
end

# use it
l = Producer.new { "F" => "(F+F)" }
l.produce(start="F", n=2)

Once you have produced a pattern with a Lindenmayer system, you could interpret every character of it as a command to a turtle graphics engine, with the following meanings:

F

Forward one step with pen down

f

Forward one step, but do not draw (pen up)

+

Turn right for a predefined angle

-

Turn left for a predefined angle

[

Push current state on stack (position, angle etc.)

]

Pop state from stack and make it current

Implementing this and the turtle engine is another 100 lines of Ruby code.

Examples

One well known Lindenmayer system is the Koch curve. It is constructed by the rule F ::= F+F—F+F, the start symbol F—F—F and an angle of 60 degree. The picture shows a Koch curve after the 5th iteration.

Botanic ferns or grasses are other examples of Lindenmayer systems.

The fern below (4th iteration) was constructed by the rule F ::= FF-[-F+F+F]+[+F-F-F], the start symbol F and an angle of 22 degree.

The grass below (7th iteration) was constructed by the two rules X ::= F[+X][-X]FX and F ::= FF, the start symbol X and an angle of 29.7 degree.

The X symbol as well as all other unknown symbols are ignored by the turtle graphics engine.

Downloads

You can download the sources for the turtles engine and the Lindenmayer systems here (you must put all sources into one directory):

www.ntecs.de/downloads/Turtle.tgz

www.ntecs.de/downloads/Lindenmayer.tgz

To view the turtles, you’ll need RMagick as well:

raa.ruby-lang.org/list.rhtml?name=rmagick