Lorenz in Living Color: Part 3 - Differential Equations on the Arduino Uno

We left off last last time with my successful efforts to implement a fourth-order Runge-Kutta algorithm to solve the Lorenz system of differential equations in Microsoft Excel.  To make this project all I hoped it to be, though, I needed to do the same thing using an Arduino Uno.

The Arduino platform is great in many, many ways because it is largely able to hide a lot of the details that have made microcontrollers tricky to deal with for decades. But once you start moving beyond simple flashing LEDs, controlling DC motor speed, and reading analog temperature sensors, that messiness and mandatory attention to detail begins to reappear.  Very quickly, trouble with execution time, accuracy, data types, memory management and program space become pressing.  For this project I had a few specific concerns.

The first was accuracy.  Like all chaotic systems, the Lorenz system is sensitive to small deviations which, over time, cause a divergence between states that started out very near each other.  Approximations at any step of the process can lead to widely differing results in short order.  This is particularly a problem when using a numerical solver because numerical solutions always involve some degree of estimation; you always only get approximate solutions.

For the purposes of this project, I was not highly concerned with the accuracy of the specific solution, only that the system continues to behave in the characteristically chaotic fashion.  As long as the colors kept oscillating back and forth I was OK; if the system ever leveled out and settled into a single color or small spectrum of colors I had problems.  Not knowing enough about the system, I was not sure what degree of accuracy was needed to make this work.  As the programmer reference states, floating point variables (values with a decimal place) only have six or seven digits of accuracy.  It was not obvious to me if this would be enough accuracy for my needs.

My second concern was speed. The Arduino Uno runs at 16MHz by default and the Runge-Kutta algorithm uses floating point values every step of the way.  Floating point operations are the slow on the Uno because it has no dedicated floating point processor so I knew calculating the solutions could be time consuming.  I was also concerned with the time it would take to send out the new color state to all of the LEDs I was using.  As I could tell from the tutorial from the distributor, each LED would need 24 bits sent and I was planning on using 50 LEDs.  For the system to work as I wanted, both the calculations and the updates would have to be fast enough that I could update the system in real time.

There was only one way to address these concerns: try and see how it works. My first pass at implementing the Runge-Kutta code was a failure and unfortunately for me, I didn't realize I had made a critical mistake in translating my work in Excel to Arduino code.  When I ran this faulty code the system quickly settled out into a constant value, leading me to believe that the Uno lacked the precision for this application. These results lead me to desperation and I decided to take an entirely different tack: I was going to cheat.

Rather than calculating the solution to the Lorenz system I decided to take the red, green, and blue values I had already found when implementing the Runge-Kutta algorithm in Excel and store them in the Uno.  There wasn't a ton of room in the flash memory available for me to use but it was enough and I was able to demonstrate that this could work.  The Uno would just play back the pre-calculated solution and then and use it to drive the LEDs.  It worked but I wasn't happy that I would only ever be able to display a fairly limited set of values, those stored in flash memory.  This small setback and the normal busy-ness of life led me to sideline the project for several months.

A month or two ago I  picked the project up again with inspiration from an artist friend of mine and did the hard work of remembering where I left off and developing new strategies to solve the problem before me.  I ordered a dedicated floating point processor with hopes it would provide me the precision I thought I needed.  I ordered a 32-bit Arduino Due which has this precision built in the microprocessor architecture (and it runs much faster).  I even ordered extra off-chip flash memory to store an impossibly large amount of pre-calculated values (worst-case scenario). And while I waited for those to arrive in the mail, I relearned how to implement the Runge-Kutta algorithm and looked over the code I had written.  With a more systematic approach to checking my work I discovered errors in both my Excel and Arduino code and after correcting both was greeted with surprising results.

The Uno had enough calculating precision and speed to do what was needed. The solution to the Lorenz system that it finds appears to be accurate enough though I won't be sure until I get the system entirely assembled and can let it run for hours or days.  This result greatly encouraged me.  I was getting close but there was still more to do.

Lorezn in Living Color - Part 2: Solving the System

So where did we leave off....?  Oh yeah, the Lorenz system.

The Lorenz system is a three dimensional system that has this intriguing property in that as the system evolves over time, the solution never repeats yet tends to follow a semi-regular pattern.  My goal is to map the three co-ordinates of the solution onto a red, green, blue (RGB) color space so that I can see the system in another way.

The first challenge to overcome: since I was planning on implementing this project on an Arduino, I needed to solve the system of differential equations numerically.  I knew that solving differential equations this way was common (almost every computing device solves in this manner) but having never done it myself, I was a bit intimidated.  I knew from one of my recent math classes that the most common way of doing this was using an algorithm called Runge-Kutta, the fourth order variant being the most common:

(From Wikipedia)

(In the world of math and science, the most fame you can reasonably hope for is getting something you've done named after you.  This carries very little value outside the math and science circles, though.  Can you name more than ten famous mathematicians or scientists?  Come to think of it, if you're reading this blog you probably can. But I bet your next-door neighbor can't.)

Even though I working on my PhD in electrical engineering, I am not used to looking at numerical algorithms described in equations and  implementing them for, say, the Lorenz system.  I decided rather than start by writing code directly on the Arduino, I was going to use tool of every of every rookie to the field of numerical analysis: Microsoft Excel.  When you're just starting, Excel makes things easier by explicitly showing the  intermediate values for every step of the process.  Each intermediate value in the process has its own column with each step in time (n from the equations above) getting its own row.

After messing around in Excel for a while I had figured out how to interpret the equations for the algorithm and seemed to have produced results that were consistent with what I understood about the system.  I could see the x, y, and z values oscillating over time, never running away to infinite or getting stuck at any particular value and always circling back and forth.  Always moving, never repeating.

But these were just numbers and its hard to get a feel for how they would look if represented as RGB values. Engineering/Artistic epiphany: I could use Processing (a close cousin of the Arduino development system) to visualize the changing state of the system.  Processing was designed for real-time animation and visualization and I was sure there would be a way to take the values from my Excel spreadsheet and use it to draw a string of circles filled with the colors produced by the calculations.

And it was.

(The full animation has 50 circles; you're just seeing a portion of it here.)

I noticed that the colors that were being produced by these solutions were not that, uhmm, colorful.  I was already scaling the values from the Lorenz solutions to make them fit the way the RGB color definition used by processing (0-255 for each color channel); a little bit more tweaking probably wouldn't hurt anything. It took a few guess-and-check attempts but I eventually found a simple equation that changed numerical solutions from the Lorenz system into color values I liked.  

Using Processing to check my work was a great idea and it gave me confidence I was on the right track.I could see the results of the Runge-Kutta algorithm, see the progression of the colors, and verify that, for my purposes, the system was producing useful results.

Next up: moving all of this work I had done in Excel onto the Arduino.

Sedgwick County Zoo

A few weeks ago my wife and I spent the early evening at the Sedgwick County Zoo.  For being a smaller-ish city, the Zoo here in Wichita is great.  Ten points if you can name all the animals.