bstorage.com home     keywords: William Storage, Visual Basic, C#, Microsoft.Net, Lyapunov, Bill Storage space, multithreaded, backgroundworker, asynchronous processing, threads, programming, software development

Lyapunov Space
            - A Software Developer's Odyssey

William Storage - Feb. 2007

The Program and Its History

About 15 years ago I stumbled on a short piece in Scientific American about Lyapunov space, showing fascinating graphs resulting from plotting the Lyapunov exponent under periodic forcing of the fecundity value, r, in the classic logistics equation,  x ← rx(1-x). A friend, John Ganter, had recently introduced me to an exciting new programming language called Visual Basic (VB, version 1), which allowed building Windows applications with no knowledge of the CreateWindow functions or anything else in Windows API. I told John that Borland C++ was my new tool of choice. He said go ahead if I wanted to spend my time messing with window handles and device contexts instead of my real objective. Good point. I decided that I would put VB to the test and build a graphical program to generate plots of Lyapunov space.

I found the Basic part of the VB language frustrating. Basic is highly idiomatic and downright ugly. VB’s object-based window management syntax was excellent, but the graphics syntax, true to its Basic roots, was a miserable attempt to allow programmers to avoid learning programming. Basic’s math capability was good, but I had to add a lot of code to simulate the IEEE 754 Floating-Point ±Infinity behavior found in Java and .Net. Despite this, VB was very cool; and I whipped out a program that let users control a few aspects of plotting, and even allowed them to save the plots as bitmaps. 

I modified my calculator to construct the plot in stripes. This progressive rendering allowed me to more quickly find the region that I wanted to zoom on. VB2’s Timer class let me allocate time slices to allow zooming in between periods of calculating pixel colors. This worked well (with significant added complexity), but, being an engineer, I was nagged by the fact this approach wasted a lot of time yielding to the user, who rarely used his time slices – zooming is infrequent.

A few years later, VB had grown up a bit, and Microsoft released Windows 95, a new 32-bit operating system with preemptive multitasking. That meant two programs could run at the same time. Furthermore, VB now had OLE (Object Linking and Embedding), a broad collection of good and bad ideas that included the ability to have two running programs communicate with each other. Wow. That meant I could split my Lyapunov zoomer into two programs – one to peddle and one to steer. The calculator program (OLE Automation server) did nothing but math, returning results periodically (say one line of pixel colors) to the user interface, which then painted a one-pixel-wide stripe of the plot. In July 1996, I published an article in Visual Basic Programmer’s Journal using Lyapunov space as a vehicle to demonstrate OLE Automation with VB4. At the end of this article I acknowledged that there was a huge amount of overhead in spinning up a separate process, and then marshaling data across process boundaries. I suggested that using an in-process server (dll – dynamic link library) that spawned a worker thread would be really slick. But VB4, sadly, could not do that. Nor could VB5 or VB6, unless you opened it up and performed some really serious surgery.

I actually did some of that type of surgery, and even wrote articles and gave talks about it in the late 90s. This fare was extremely popular, and got me good ratings on the speaking circuit for a while. But the popularity of showing ways to trick VB into being a real programming language really just emphasized VB’s severe limitations. This pissed off Microsoft enough that they officially condemned my material, which, thankfully, made it even more popular. Matt Curland and I jointly shared the distinction of being the only people ever named in a Microsoft Knowledge Base article that stated that techniques we used were officially “not supported” (KB166215, Modifying VTables Is Not Supported). In late 1997, Drew Fletcher, a sharp young Program Manager for VB poked me in the chest at a conference and said, “Storage, we’re going to put you out of business by inventing a new version of VB that won’t give anyone a reason to hack it.” And they did. It was called C#.Net, and Drew became a C# Program Manager.

When C# and the radically re-engineered VB.Net that shared 99% of C#’s capabilities were released in 2001, I wrote another article (Draw Asynchronously With .NET, Visual Studio Magazine, Aug. 2002) using the Lyapunov space calculator as a means of demonstrating .Net’s features. I noted that in 1996 I had stated that a second thread would be ideal for this situation; and I enthusiastically showed that in fact it was. The graphics part of the code was vastly more readable than the equivalent VB4 code. .Net’s gdi+ library was - and still is - intuitive and powerful. .Net’s threading model, very similar to that of Java, is good, but when I look back at the 2001 C# version (I also published a line-by-line equivalent VB.Net version) of the calculator, I see a lot of threading code that doesn’t really directly contribute to the task of calculating Lyapunov exponents. Or at least a mathematician wouldn’t think so. The problem stems from the fact that windows (Windows Forms in .Net) are not thread-safe. When the calculation thread draws on the Windows Form, locking is required. Those not familiar with the details of threading tend to see such case as a tangled mess of Monitors, WaitHandles and ManualResetEvents. In 1996 I received a lot of email about the Lyapunov calculator from programmers, but very little regarding the 2001 version. I suspect thread management confusion may have been a factor. My 2001 code had a bug in it (related to coordinate transformations, not threading) that resulted in its zooming in on a different region than the one the user selected; and no one even reported it to me.

I recently (Jan. 2007) took a look at the latest .Net offerings from Microsoft to see if it provided any tools to further simplify the problems encoured in building an asynchronous Lyapunov zoomer. The latest version of .Net (2005) introduced the BackgroundWorker class, an encapsulation of multi-threading. As long as you obey a few simple but important rules, you can perform a task asynchronously on a second thread with no knowledge of the details of thread synchronization. Surprisingly, the code to do this looks very much like my original VB2 timer-based Lyapunov calculator, without the ugly Basic graphics methods. The BackgroundWorker provides DoWork and ReportProgress events. DoWork is where I do the calculations on the background thread. As long as I don’t reach outside of the thread, i.e., access any variable not received through the event’s DoWorkEventArgs parameter, I’m safe. I then raise an event on the calling code’s thread by passing my work payload – a one pixel wide bitmap in this case – to the worker’s ReportProgress method, which raises the ReportProgress event, in which I can update the Windows Form.

You might be wondering why I actually build a bitmap that needs to be marshaled, instead of an array of color values. This would require that the form do the actual bitmap creation – which, of course, it can do. But when the user-specified iteration count is small, it can actually take longer to paint a row of pixels on the main plot than it does to calculate the color values of those points. In this case, the user cannot interrupt the process to zoom because the main thread (the Windows Form thread) is continuously busy drawing, thus defeating the whole purpose of multi-threading.

So 15 years after my initial interest in the topic, I’m finally happy with my Lyapunov Space plotter. I'd write up another article, but the publisher still hasn't paid me for the last one. No hard feelings - 2002 was a rotten time for IT publishing. If  you would have read such an article, just download the code and examine the BackgroundWorker events; I think the C# code is self-explanatory and a testimony to the advances in development of object-oriented programming languages. The only complaint I can think of stems from the lack of a “static Include” for the .Net Math class. I’m aware of the academic objections to static includes, but these objections are downright silly when applied to the Math class. Perhaps another way of looking at this is to acknowledge how far computer programming has drifted from mathematics for common math operations to be off in there own library, not having an implicit inclusion. Oddly, Java and even VB.Net, which is generally seen as protecting coders from themselves more than other languages, do allow static includes. But I’m nit-picking.

Processor speeds and virtual machines have changed more than my code has since I first built a Lyapunov zoomer with VB2. A 600 x 600 plot at 2000 iterations per pixel now takes two minutes on my $700 HP computer as opposed to overnight with the VB2 version.

If you’d like to experiment with the program, you can download the source code and tweak as desired. Please let me know if you find a bug.

The Math

The logistic equation, or logistic growth curve, gets its name from analysis of the self-limiting growth of an animal population. Roughly speaking, the more food a population has, and the more rapid their reproduction, the more the population climbs. Assuming a fixed food supply, the larger the population, the smaller the food intake becomes for each member. As per-capita food drops, mortality rises and the population falls, thereby increasing per-capita food intake. The value of r in the equation represents fecundity, a measurement of the potential reproductive capacity of the population, x. Rabbits in verdant areas have a high fecundity. High fecundity can lead to population instability, where, given an infinite amount of time, the population never settles down to a constant value.

In the logistic equation, when r is less than 2, iterating the function quickly results in convergence of the value, x. Fans of chaos math would refer to this system as a single-point attractor. For r values between 2 and about 3.57, x alternates repeatedly between an even number (actually 2ⁿ) of values. From 3.57 to about 4, chaos reigns.

The Lyapunov exponent is a measure of the stability (or predictability) of the system. Lyapunov space is a term given to plots of the Lyapunov exponent in systems where the fecundity, r, is periodically forced in some pattern, such as aabaa. For each coordinate (a,b), the values periodically given to r in the logistic equation, the Lyapunov exponent is represented by a color value. Black represents instability, where the exponent equals negative infinity. Finite negative values are given progressive darker shades of yellow as instability increases. Positive exponents, indicating stability, are painted blue. The shading rules are rather arbitrary – chosen for visual impact. You can adjust them to produce different effects. I also added a means of controlling the fade rate, or contrast, for values between zero and negative infinity.

Traditionally, Lyapunov space is calculated with an initial x value of 0.5. My program allows users to vary this value between 0 and 1. Doing so reveals that the system is somewhat dependent on initial conditions, as certain branches of the fractal are uncovered or covered by others.

A Google search on Lyapunov space, Lyapunov fractal or Lyapunov exponent will provide more detailed discussions of the subject.

Below are some sample images generated by specifying a plot size of 2000 x 2000 pixels with 5000 iterations.

             Large images