ruby inject and the Mandelbrot set

Ever since I came across ruby’s Enumerable inject function, I have been curious about its applications, and how to best think of it in its most general mathematical form.

As an example, say we have a list of numbers that we want to sum:

[ 2, 3, 5, 7 ]

We can do this in a traditional iterative loop:

sum = 0
[2,3,5,7].each { |x| sum += x }
sum

=> 17
(=> 17 is the output of copying and pasting this code into irb for those who are following along at home.)

Using inject, we can do this in 1 line:

[2,3,5,7].inject(0) { |x,y| x+y }

=> 17
To see what is going on here, it will be helpful to abstract out the addition function:

def f(x,y)
  x + y
end

Let’s redo the previous inject call, and just replace “x+y” with “f(x,y)”:

[2,3,5,7].inject(0) { |x,y| f(x,y) }

=> 17
Let’s expand out what inject is really doing. This is inferred directly from the Ruby documentation:

f(f(f(f(0,2),3),5),7)

=> 17
That is illuminating. It seems that inject allows us to iteratively apply a 2-parameter function to itself, where the output of each step in the iteration is fed back into the first parameter, and the second parameter is read in from the list it is called on. The first time it is called, it needs a value for the first parameter, and this single value is the parameter given to the inject call itself.

That’s quite a mouthful. But let’s test our understanding at least on the inject parameter. If we give it 1,000,000 in the previous examples instead of 0, we should have 1,000,000 added to the result:

[2,3,5,7].inject(1000000) { |x,y| f(x,y) }

=> 1000017
So it feels like we have a better understanding of ruby’s inject now. Another way to think of it is in terms of the f(f(f(...f(f(f(a,b),c),d)...,x),y),z) pattern.

As a final test of our ability to wield the inject method, let’s try to print out the Mandelbrot set onto the console using it as the main iterator.

If you’re not familiar with the Mandelbrot set, I recommend spending some time on that page either before or after reading this.

Let’s start with defining the iterated function:

def m(z,c)
  z*z + c
end

For a given complex number a, to see whether it is included in the Mandelbrot set or not, we start by squaring it and adding the result back to itself:

a*a + a

(set a=0.1 if you are typing this into irb and don’t like to see the NameErrors.)
Or in other words,

m(a,a)

We take the result of that, square it, and add it back to a:

m(a,a)*m(a,a) + a

or in other words,

m(m(a,a),a)

Let’s do it two more times just to be sure we see the pattern:

m(m(m(a,a),a),a)
m(m(m(m(a,a),a),a),a)

This looks like a job for inject! The last line above is equivalent to:

[a,a,a,a].inject(a) { |z,c| m(z,c) }

The number of times the iteration is done is simply the size of the given array. Fortunately, ruby makes it easy to create arrays with repeated elements:

Array.new(4,a).inject(a) { |z,c| m(z,c) }

For the resolution we are aiming for, 50 iterations should be enough. Also, let’s replace m(z,c) with z*z+c since it doesn’t really save us space, and everything we are doing is Mandelbrot-specific so there is no need to abstract it out.

Array.new(50,a).inject(a) { |z,c| z*z+c }

The only free variable here is a, so let’s wrap this into a function called mandelbrot:

def mandelbrot(a)
  Array.new(50,a).inject(a) { |z,c| z*z+c }
end

As I started saying earlier, to test whether a given complex number a belongs to the Mandelbrot set or not, or rather for our purposes to approximate these points since we are only doing 50 iterations instead of an infinite amount, we check the absolute value of mandelbrot(a). If it is less than 2, we will print an asterisk on the screen. Otherwise we will leave it blank.
We’ll have y go from 1.0 to -1.0 in the vertical direction, and x go from -2.0 to 0.5 in the horizontal:

require 'complex'
 
def mandelbrot(a)
  Array.new(50,a).inject(a) { |z,c| z*z + c }
end
 
(1.0).step(-1,-0.05) do |y|
  (-2.0).step(0.5,0.0315) do |x|
    print mandelbrot(Complex(x,y)).abs < 2 ? '*' : ' '
  end
  puts
end

The double-nested loop at the bottom simply iterates through the rows and columns of the screen, printing out the Mandelbrot set line by line. The numerical step values are chosen so as to have 40 rows and 79 columns. The body of the loop creates the complex number Complex(x,y) and calls the mandelbrot(a) function we constructed above with it, and compares the absolute value of its output to 2. If less than 2, display an asterisk, otherwise display a space. After each horizontal line, the call to puts just goes to the beginning of the next line.

I won’t give away the surprise ending! Try it!

Share:
  • del.icio.us
  • Reddit
  • Technorati
  • Twitter
  • Facebook
  • Google Bookmarks
  • HackerNews
  • PDF
  • RSS
This entry was posted in programming. Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.
  • Nate Murray

    Fantastic! The code is succinct and the output is beautiful. Raganwald just wrote another interesting article on Ruby inject that could be interesting to everyone (http://weblog.raganwald.com/2008/02/1100inject.html). As our interview last week said, if these types of constructs (map, inject, etc) should be interesting to anyone who is in the business of programming.

    Thanks for the insightful post!

  • http://www.xcombinator.com/2008/03/05/ruby-inject-and-category-breadcrumbs/ ruby inject and category breadcrumbs

    [...] addition to mapping out the Mandelbrot set, ruby’s inject method can also be used to easily find and/or create nested categories given a [...]

  • http://textgoeshere.org.uk Dave Nolan

    That is a thing of beauty. Cheers!

  • Eimantas

    awsomeness at it’s best! one can expand it to use colors in console ,)

  • http://asemanfar.com Arya Asemanfar

    That’s pretty cool output! :)

    One nit pick though, it seems your usage of inject isn’t appropriate because you’re creating an array of size 50 just to iterate over something 50 times.

    It might be more appropriate to do something like:

    def mandelbrot(a)
      z = 0
      50.times { z = z * z + a }
      z
    end
    

    That way, if you want to do some large number of iterations, you don’t end up creating and destroying huge arrays. But I guess it’s just preference :)

  • http://quantumlab.net Matt Pulver

    @Arya: The meaning of the word “appropriate” depends upon what the goals are. The first goal here is to illustrate use of ruby’s inject function. If you can suggest a nearly equally succinct way to write the function

    def mandelbrot(a)
    Array.new(50,a).inject(a) { |z,c| z*z+c }
    end

    which illustrates use of the inject function that doesn’t use a 50-element array of identical values, then I would consider your nit pick “appropriate”.

  • Michael Fairchild

    This is awesome. Mad props.
    Here is a screenshot from a run of the code.
    http://img.skitch.com/20090526-jdss7n6f8hssmmywnsyiam3ycb.jpg

  • Javi Fontan

    Simply lovely.

    And now for some performance wars I changed the number of iterations from 50 to 1000 and ran it using ruby 1.8.6 (the one that comes with Leopard), ruby 1.9.1p0 (2009-01-30 revision 21907) and MacRuby 0.4:

    ruby 1.8.6
    real 0m54.405s
    user 0m54.209s
    sys 0m0.083s

    ruby 1.9.1p0
    real 0m10.758s
    user 0m8.756s
    sys 0m0.133s

    MacRuby 0.4
    real 1m7.342s
    user 1m19.255s
    sys 0m2.261s

  • karatedog

    Very good example!
    Is it possible to polish the performance by overloading the “*” method of the Complex class, so it won’t always do the 50 cycle loop no matter if the second iteration went over 2?

  • http://quantumlab.net Matt Pulver

    @karatedog: Yes, good idea. However if your goal is performance, I don’t recommend using inject on a 50-element array of identical values; for example, see the above post by Arya.

  • Mike Flores

    The recursiveness of inject captures the idea of fractals: an element that is formed of elements that resemble the original but in a smaller size. One thing that calls my attention is what happens with those values that are not plotted? I.e. the values where the comparison exceeds 2. Are they out of the 2 dimensional plane and hence are disregarded?

    mandelbrot(Complex(x,y)).abs > 2