Tuesday, December 4, 2012

On fractals

I did say I'd talk about fractals, didn't I? I've been fascinated by them for a good 25 years now... A few weeks ago I attended a presentation at the local IEEE chapter. It didn't feature a lot of graphics, but instead it focused on practical applications of fractals to analyze lots of data. So I figured I'd bring them up at some point on this blog.

Today I'll mention some stuff just to whet your appetite.

Definition...


Or perhaps not. According to wikipedia:
"There is some disagreement amongst authorities about how the concept of a fractal should be formally defined. The general consensus is that theoretical fractals are infinitely self-similar, iterated and detailed mathematical constructs having fractal dimensions, of which many examples have been formulated and studied in great depth..."
Clear as mud, I'm sure. But still, fractals are quite interesting. Not just from a mathematical standpoint, but from a wide variety of angles.

Back when I was in school, one of my math teachers talked a good bit about fractals. The term had been around less than 10 years, but already it was quite popular in academic circles. I don't really remember anything he told us, but I will never forget the picture of the Mandelbrot set he showed us.

To him, fractals were fascinating equations. To us, they were fascinating graphics:

Actually... no, that is the Python code!
Yep, that's it! The Mandelbrot set
Regarding the source code, that's not how Python code looks usually. This is what is called obfuscated code. It is an art form in itself. The source was taken from the Preshing blog.

For a non obfuscated version of the code, and lots of explanations, check out: Python Patterns.

Sierpinski


Before you can run, you have to learn how to walk. Mandelbrot demanded a lot of horsepower back in the mid 80s. My Apple ][ was only 1MHz and my Mac, 8MHz. It would have taken days. So I played around with assembler and Pascal, doing this:



                               @                               
                              @ @                              
                             @   @                             
                            @ @ @ @                            
                           @       @                           
                          @ @     @ @                          
                         @   @   @   @                         
                        @ @ @ @ @ @ @ @                        
                       @               @                       
                      @ @             @ @                      
                     @   @           @   @                     
                    @ @ @ @         @ @ @ @                    
                   @       @       @       @                   
                  @ @     @ @     @ @     @ @                  
                 @   @   @   @   @   @   @   @                 
                @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @                
               @                               @               
              @ @                             @ @              
             @   @                           @   @             
            @ @ @ @                         @ @ @ @            
           @       @                       @       @           
          @ @     @ @                     @ @     @ @          
         @   @   @   @                   @   @   @   @         
        @ @ @ @ @ @ @ @                 @ @ @ @ @ @ @ @        
       @               @               @               @       
      @ @             @ @             @ @             @ @      
     @   @           @   @           @   @           @   @     
    @ @ @ @         @ @ @ @         @ @ @ @         @ @ @ @    
   @       @       @       @       @       @       @       @   
  @ @     @ @     @ @     @ @     @ @     @ @     @ @     @ @  
 @   @   @   @   @   @   @   @   @   @   @   @   @   @   @   @ 
@ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @



It is a text representation of a Sierpinski triangle or gasket. It is a Fractal that was discovered by the Polish mathematician Waclaw Sierpinski in 1915, before we even had a name for fractals (that was coined by Benoit Mandelbrot in 1975).

Perhaps not that impressive nowadays, but it was a lot of assembler code to do this. In Pascal too, I seem to remember it was at least 60 lines.

On Rosettacode, you can find the following Python program that does the equivalent:

def sierpinski(n):
    d = ["*"]
    for i in xrange(n):
        sp = " " * (2 ** i)
        d = [sp+x+sp for x in d] + [x+" "+x for x in d]
    return d
 
print "\n".join(sierpinski(4))

But dont be fooled by that short piece of code, it is a complex subject.

Other fractals that have been around for a long long time and dont require a lot of computing power, are the cantor set, the Heighway Dragon and the Koch snowflake. All of them are examples of iterated function systems (IFS). The Mandelbrot and Julia sets are of a different type of fractals: escape time fractals. Also, there have been some interesting links made between the Cantor set and Fibonacci's series, so it is a normal continuation from that theme, since I've had a few blog entries on Fibonacci: here, here and here.

Fractint


In 1988 appeared on BBSes and usenet the program Fract386, and renamed Fractint the following year. That was pretty exciting, we could render Mandelbrot without hardware floating point math. It was fast! Well... compared to what it was up to that point...

Mandelbrot set


Fractint is a DOS program. It is also available for Windows (old windows 3.1...) and Linux now, but let's stay with this concept for a minute. How can we run DOS programs on the Raspberry Pi?

Video mode selection

Dosbox

Dosbox is a dos on x86 emulator. It runs on non x86 platform, such as the Raspberry Pi (ARM processor) without problems. By comparison, WINE does not work on the Pi.

$ sudo apt-get install dosbox

Once installed, run it once so the configuration file gets written, then exit. If you get issues with the keyboard mapping:

$ cd .dosbox
$ vi dosbox.conf

usescancodes=false


That should take care of it. Now create a dos directory and download fractint there:
$ cd
$ cd dos
$ wget http://www.nahee.com/spanky/pub/fractals/programs/ibmpc/frain204.zip
$ unzip fain204.zip

Now, run dosbox and mount the dos folder:

mount c dos
 You can now type c:, change (cd) to the fracti~1.04p folder and run Fractint!

We'll continue on fractals at a later date.

No comments: