[Mandelbrot] Code Samples/Comparisons

Bill Marriott wjm at wjm.org
Sun Dec 6 19:09:00 EST 2009


Hi Mark,

>>> what about using task/code examples from
>>> http://shootout.alioth.debian.org/. Revcoders (us, runrev ltd?..)  will
>> I think that's a great idea.
> Sorry, Kevin, I think it's a Very Bad Idea.

Thanks so much for taking the time to do this! But I think it's a *great*
example, and I am going to show you why.

Let's start out with a few observations:

- How "practical" is this? I took a closer look at the site.

http://shootout.alioth.debian.org/u64/benchmark.php?test=mandelbrot&lang=all&box=1

The goal of the routine is to generate a mandelbrot image in the .PBM
format. Now, this has some relevance I suppose in testing CPU performance,
but not exactly in the real world. How many programs read PBM, for one? None
on my Mac, but Photoshop and Paint Shop Pro could read it on my Windows PC.
How fun is it to run this program, then load the result up in a graphics
editor? About as much fun as punch-card, batch programming.

- The original Pascal program (or at least your transliteration of it) *has
a bug!* Give the output file an extension of .pbm and load it into a program
that can read that format. You'll find that the image is skewed more and
more as the dimensions increase.

http://revuser.com/mandel/orig-600.png

In either Pascal or revTalk, as coded, it's going to be a challenge to find
out where that bug lies.

- It doesn't seem like it was that hard to "transliterate" the original
Pascal code. I was impressed by the similarities, actually. Even then, there
are portions of your revTalk version that are a little more readable. Since
the vast majority of this is mathematics, and we're not out to reinvent
algebraic notation, you're right that it's not the best showcase. Math is
going to be math in any programming language. It's certainly not *less*
readable. What makes it hard is the Mandelbrot formulas and especially the
encoding into .pbm format (which is what requires all those bit operations.
(Maybe all of the examples from that site are like this?)

- Pascal is considered a pretty "easy" language. Did you check out what the
"solution" looks like in Java?

http://shootout.alioth.debian.org/u64/benchmark.php?test=mandelbrot&lang=javaxint&id=3

In C++?

http://shootout.alioth.debian.org/u64/benchmark.php?test=mandelbrot&lang=gpp&id=5

Woah! :)

- Well our performance is a is a bit disappointing relative to the "command
line" Pascal version, we *do* beat out variants of PHP, Python, Ruby, and
Perl, depending on what your processor was versus the one used for the
benchmarks.

- You were able to add a nice GUI file selector dialog trivially. Now,
imagine that your goal isn't to produce a .pbm image, but rather to show
something on-0screen the user could interact with in some way. Things
get more interesting. This is where Rev starts to shine. The
further away you get from "pure" math and have to get into user interface,
interaction with local and remote file systems, manipulating data sets, and
business logic issues, the better we look. Our language abstracts the
operating system, so developers don't need to be concerned with the proper
API to call for common tasks.

- Most (but not all) of us are not using Rev to generate Mandelbrot data.
We're creating usable applications for business tasks, entertainment and
educational software, database front-ends, etc. It might well be that this
site/link is all about these kinds of math-intensive routines. I didn't look
too closely at them, admittedly. What I did like about Viktoras' suggestion
was that he found a site with some sample code in a variety of languages. I
think it's healthy for us to look for such examples and discover the
strengths and weaknesses that emerge when we try to express them in revTalk.

My take on the "productivity" equation is that it's not merely the number of
lines of code produced, and it's ultimately not even how fast the code
executes. In most situations, it's how long it takes to express the
algorithm, and debug it later on. To encapsulate algorithms in flexible user
interfaces. To take things to an extreme: a routine
built with machine code or assembly will always execute faster than one
built in a high-level language. But how many of us could sit down and write
a database front-end in assembly? How long would it take? How usable and
adaptable would it be?

Another way to look at things is from the artist's viewpoint. There are
people who will never touch digital photography because they are expert at
the analog process. There are illustrators who will never give up their
charcoals. There are Lego builders who spurn the non-rectangular bricks! And
thank heaven for them, because I respect the desire for control and
attention to nuance. In a similar vein, other languages can indeed reward
sweating details like what kind of number you're trying to store, manually
allocating and releasing memory, etc.

We're not promising to be the tool that lets you rewrite OpenGL or even
build a competitor to Excel. Instead, we're a tool that complements these
other technologies, and opens up the idea that -- for example --  instead of
spending hours "steering" Excel you might automate your workflow such that
data acquisition, processing, and presentation might all be handled with a
single click.

Enough pontificating eh? Let's get to coding. I'm going to deliver on my
promise to show you why this actually shows off why Rev is so fantastic.

I was intrigued by this example, because Mandelbrots are beautiful things. I
knew they had something to do with imaginary numbers, that they are
infinitely variable -- you can zoom in on them forever and not find a
repeated pattern. But I didn't understand the math, so of course I couldn't
really analyze the original Pascal code effectively.

I had to become a "mini" content expert. So I read up on Mandelbrots. I
found some useful pages:

http://www.wikihow.com/Plot-the-Mandelbrot-Set-By-Hand

http://www.olympus.net/personal/dewey/mandelbrot.html

and especially

http://steve.hollasch.net/cgindex/misc/mandelbrot.html

Now I was getting somewhere. I learned that a Mandelbrot is a graph where
the x axis represents a "real" number, and the y axis represents an
imaginary number (a number involving the element "i" -- which is the square
root of -1). The unique thing about a Mandelbrot set is that you don't know
for sure whether a given coordinate is within the set until you test it
iteratively. Some coordinates reveal themselves to be part of the set
quickly, and some not so quickly. The "depth" you have to go in this
iterative calculation varies for each coordinate. It also involves a kind of
"digital sampling" phenomenon, where things look different depending on the
"resolution" at which you're charting. That hardly covers the whole topic,
but it was enough to give me a handle on what the routines were trying to
do.

I found George Taylor's page to be much more useful than the Pascal code as
a launch point for understanding how to chart a Mandelbrot in revTalk. For
one thing, he didn't break it up into multiple nested functions, which made
it easier for me to understand. Second, I'm much more familiar with BASIC
from my early days with the Sinclair ZX81 than I am with Pascal. I took his
code example:

INPUT "Initial Real value of C",CRL
INPUT "Final Real value of C",CRH
INPUT "Initial Imaginary value of C",CIL
INPUT "Final Imaginary value of C",CIH
INPUT "Iteration limit",MAXITER
WIDTH=320
HEIGHT=200
XSIZE=(CRH-CRL)/(WIDTH-1)
YSIZE=(CIH-CIL)/(HEIGHT-1)
FOR Y=0 TO 199
  CI=CIH-Y*YSIZE
  FOR X=0 TO 319
    CR=X*XSIZE+CRL
    REM Now CR, CI are scaled
    REM Do Z<-Z^2+C iteration
    MEMBER=TRUE
    ZR=0
    ZI=0
    FOR I=1 TO MAXITER
      NEWZR=ZR*ZR-ZI*ZI+CR
      NEWZI=2*ZR*ZI+CI
      ZR=NEWZR
      ZI=NEWZI
      Z=SQR(ZR*ZR+ZI*ZI)
      IF Z>2 THEN
        MEMBER=FALSE
        EXIT  (exits the FOR loop)
      ENDIF
    NEXT I
    IF MEMBER=TRUE THEN
      PLOT X,Y
    ELSEIF ((MAXITER-I) AND 1)=0 THEN
      PLOT X,Y
    ENDIF
  NEXT X
NEXT Y
END

And I did my own revTalk translation, this time making generous use of long
variable names that made more sense to me:

on mouseUp
  put fld "cRstart" into cRstart
  put fld "cRend" into cRend
  put fld "cIstart" into cIstart
  put fld "cIend" into cIend
  put fld "maxIterations" into maxIterations
  put fld "myWidth" into myWidth
  put fld "myHeight" into myHeight

  put (cRend-cRstart)/(myWidth-1) into plotWidth
  put (cIend-cIstart)/(myHeight-1) into plotHeight

  -- for each y-axis value (scaled)
  repeat with y=0 to myHeight-1
    put cIend-y*plotHeight into cImaginary

    -- for each x-axis value (scaled)
    repeat with x=0 to myWidth-1
      put x*plotWidth+cRstart into cReal

      -- test the coordinate iteratively
      put true into itBelongs
      put 0 into zReal; put 0 into zImaginary

      repeat with i = 1 to maxIterations

        put zReal * zReal - zImaginary * zImaginary + cReal into newZreal
        put 2*zReal*zImaginary+cImaginary into newZimaginary

        put newZreal into zReal; put newZimaginary into zImaginary
        put sqrt(zReal*zReal+zImaginary*zImaginary) into z

        if z>2 then
          put false into itBelongs
          exit repeat
        end if

        if z> 2 then exit repeat

      end repeat

      if itBelongs then
        put i into myPlot[x][y]
      else
        if maxIterations-i > 0 then
          put i into myPlot[x][y]
        end if
      end if

    end repeat
  end repeat
end mouseUp

Now you'll notice that even now I'm able to do something a little different
from Taylor's original algorithm. Where he says, "plot x,y" -- which marks
the pixel at x,y black -- I store i within a multi-dimensional array. This
stores the number of generations it took to determine whether x,y was part
of
the Mandelbrot set. It will enable me to produce a prettier graph, and also
separates the output code (whether I'm going to create a .pbm file or
display
on-screen or do something else from it) from the code used to generate the
Mandelbrot itself.

Showing the image on-screen in Rev was a piece of cake, relative to creating
a .pbm file.

  repeat with y=0 to myHeight-1
    repeat with x=0 to myWidth-1
      -- more iterations yields a lighter color
      put numToChar(trunc(myPlot[x][y]/maxIterations*256)) into c
      -- create a shade of grey
      put numToChar(0) & c & c & c after bitmapData
    end repeat
  end repeat
  set the width of image "mandelPlot" to myWidth
  set the height of image "mandelPlot" to myHeight
  set the imageData of image "mandelPlot" to bitmapData

That's because the imageData is simply four whole bytes representing 0 and
the R, G, B values of the pixel. Inefficient perhaps, but really simple. No
bitwise
operations unless I really need to (and I won't need to, since Rev can
export
snapshots to a variety of common formats).

It didn't take me much work to display a beautiful, greyscale image of a
real Mandelbrot on-screen. Plus I had a nice UI that would let me set all
the parameters of the equation visually. I had one final thing I wanted to
do, and that was to make it so I could "zoom in" on the Mandelbrot to
explore its infinitely variable nature.

All I did was overlay a graphic on top of the "mandelPlot" image I created,
then attach a script which would make note of where I clicked on it, set
that as the new origin, and set a new scale around that point.

My "finished" stack is at:

http://revuser.com/mandel/MyMandelbrot.zip

I would say that I got much further along exploring and understanding the
magic of fractals. In the end, I'm looking at a 300x300 or maybe a 900x900
screen image; I'm not generating 16,000x16,000 bitmaps. So it doesn't really
matter if it takes 3 or 30 seconds to generate. I have a solution that has a
nice user interface so I can tweak various settings and interactively see
their effect on the graph. I already added niceties like a progress bar, and
zooming.

I could add more customizations like the ability to set the colors I want to
use. The code I have written to generate the Mandelbrot is about as clear as
it could be. (And I'd like to see what the Pascal or C++ code would be to
replicate my little stack's UI/functionality!)

By analogy, when constructing business applications, the "hard part" -- the
part you have to get right -- should be understanding your business. It
shouldn't be expressing that business logic/mechanics within code. Rev
enabled me to focus on the science of Mandelbrots, not the mechanics of
creating a bitmap. It allowed me to create a program that I could use to
explore what Mandelbrots are in a beautiful, fun, engaging way. And if I
ultimately decided that I needed blistering performance in rendering the
graphs, I could always crack open my Pascal or C++ compiler and make an
external that did the "heavy lifting" down the road.

Look at it this way -- would an organization prefer a piece of code that
runs in 3 seconds but does only one thing, and can't be modified except
by the original coder? To change the parameters of the graph in Pascal,
one must load up the compiler, edit the right bits of the code, do a "build"
and all that stuff. Or, would you like an application like my stack, which
might
take 10 times longer to execute, but gives the end user a lot of control
and flexibility to understand what's going on?

Productivity isn't about processor cycles, and it's not always about lines
of code. It's about how much one can accomplish with the knowledge
they have.
 





More information about the Use-livecode mailing list