Stuart Hacking

Just some stuff I thought about today. Here’s a fibonacci function expressed in Lisp:

It can be used to compute the fibonacci sequence:

It’s simplicity is elegant, but, frightfully inefficient. In fact, the recursive definition of fibonacci is often used as an example of an inefficient method. Let’s look at why it’s poor. When fibonacci is called for a value of n there are two possible paths the program can take:

1. If n <= 1 give back the value of n
2. otherwise return the sum of the previous two numbers in the sequence

So, if n is 0 or 1 then the value is simply 0 or 1 respectively. This is the base case of the function. In other words, from this piece of concrete knowledge, we can derive the remaining values. If n is any value higher than 1, then we need to actually compute what it is. Notice that this case requires fibonacci to be called another two times.

This imposes significant overhead on the machine. In addition to this, the results of these two function calls must be added together. That means we need to hold onto some space in memory to store the results. Simplistically, we refer to the number of significant function calls as the time complexity of the program, and the amount of memory required as the space complexity. Fibonacci sure is expensive.

Anyway, this got me to thinking. What is the main problem with fibonacci? It’s the fact that it must repeat a lot of its calculations. If we want to find the value of Fib(5), we must call Fib(4) and Fib(3). But wait: To find the value of Fib(4) we must call Fib(3). Hence, we do the same operation twice. What if we could tell the program to remember a value once it had been found? Wouldn’t this speed things up? Can this be done without sacrificing the simplicity of a recursive method?

Here’s a modified, partial fibonacci function:

This one is a little more involved, but don’t panic: It still does the same thing, in much the same way. It has an extra trick though: Before it attempts to compute the value of n, it check to see if it already has a value. It looks in a structure called a hash table (any type of lookup table should do). Think of this like a telephone directory. If you know someone’s name, you can look it up in a phone directory and it will tell you their number. In our hash table, if you know a value of n, you can look it up and find its fibonacci value. Of course, some fibonacci values won’t be listed just yet. If there is no value in the table, we continue with our normal process: If n <= 2 then return 1. If n is greater than 2 then we find it’s value by adding the previous 2 fibonacci numbers. Now we have one more change to make: Having just found this new value of Fib(n) we store it in the hashtable. This means we won’t have to do the hard work of finding it again later – It’s already there!

Now, this act of remembering our previous work means that we must use a bit more memory, but the gain is a remarkable improvement in speed. Today, memory is pretty cheap, so this is not a bad thing. Look at the method we used. We start with a function that must call itself with a smaller value in order to discover a new value. When we discover a new value, we store it in a table so that we can quickly find it later.

This could most likely be generalised for any function that follows this pattern. There’s another blog post for when I get time to look into that aspect of it. If this post was about the optimisation, the next will be about abstracting that into a common pattern.

I hope this was of some interest. It was just a little thing I thought about this afternoon then decided to try it out. After I tried it I thought it might make a quick, informal blog entry.

Update: It seems that I have inadvertently stumbled across the definition of memoization which was conceived in 1968! It’s fun to try something out and then learn about a formal definition of the same principle. The act of developing an example gives it more meaning. (Further reading: http://en.wikipedia.org/wiki/Memoization).

Programming Computers, Emacs, hack, lisp, memoization, Programming

Here are a couple of Project templates I made for XCode 3.2. One for a WxWidgets based project (wxMac 2.8), and one for a GLUT project. Hope they work.

• GLUT C++ Project – Initializes GLUT and creates a scene containing a cube which can be rotated using the keyboard arrow keys. toggle an axis widget using ‘w’, toggle fullscreen using ‘o’ and exit using ESC. The FPS is displayed in the titlebar.
• WxWidgets C++ Project – Initializes a WxWidgets based app with an empty frame.

Programming Computers, mac, Programming, Software

Hurray! Apple fanboys should be pleased with the release of OS X, version 10.6. Snow Leopard panders to their desire for an all Apple platform. For the rest of us sensible users, Apple have screwed the pooch.

Okay, we have new shiny toys like Quicktime X and – well, that’s about the height of noticeable changes. I’m all for enhancing the user experience, but in this case, in my opinion, it has come at the expense of developer comfort.

What I’m referring to here is the lack of Java support in the new XCode 3.2. I’ve always felt that XCode was a fairly elegant environment for writing all C/C++, Java and Objective-C projects. So- why, Apple, would you arbitrarily drop support for a language? Out of spite? You didn’t even drop support – you just made it frigging irritating to use. Do you enjoy kicking your users in the nuts with each new release?

I’m not even surprised at this stage. I guess I could add the XCode templates back in manually but I’m more in favour of adopting a more portable command line build process… It seems the best way to get away from Apple’s user abuse.

Programming Computers, error, mac, Programming, Rant

I am forced to use a Windows based laptop in work and one of the more frustrating features is the updates that get pushed out by the IT ‘services’ group. Of course, updates are a good thing, but we do them during downtime when it won’t disrupt actual work. Here are the things I most hate about these Windows updates:

Do it now, or else.

There are updates available for your computer. You can install them now or they will automatically be installed in 15 minutes. After installation your computer will be restarted.

I’m sorry, were you busy?

As if point 1 didn’t irritate me enough (which is most certainly does), updates frequently occur right in the middle of a large task. Copying a large file or set of files is doomed to failure. In other cases the updates will simply interrupt anything you happened to be doing, forcing you to break your concentration.

Update Dependencies

OK, I’ll install your updates already! Tick, tick, tick… *reboot*
Your updates have been installed. There are new updates to install.

Yes, some updates rely on the presence of previous updates so it takes a couple of runs to get them all installed. which also means a couple of reboots; a couple more minutes of your precious day.

And one of my personal favourites: The “Your computer must be restarted dialog” which always stays on top of other windows. In case you forget.

Software Computers, error, Windows

I just ordered one of these kits

Fuzebox Starter Pack

The mainboard is supplied unassembled.

The fact that computers contain hardware is something I can normally overlook. Hardware can spasm out of control, fizzle and burn in impressive colours or simply die slowly, bit-by-bit (if you’ll excuse the pun). I’d be happy to own a computer that operated by magic: no parts – just an abstract concept.

Nevertheless, I’m still fascinated by hardware and have always wanted to try a little project. Having read most of “Hackers: Heroes of the Computer Revolution” now, I’m aware that among the first home computers was the Altair 8800. A kit machine where you would, typcally, buy the components and build it yourself. This was the norm, and, Hackers is full of little accounts of people hacking together hardware into a semblance of what we know as Personal Computers. Steve Wozniak is a notable example: Inventor of the Apple. The next generation Apple II would becomes one of the most popular computers for games hackers in the early 80s.

It’s always struck me as a time now past – today, infinitely more complex machines are fabricated in computer controlled environments. Even if you try to gather parts from vintage hardware, for a novice enthusiast it would be difficult to put together and perhaps more difficult to find connectors to make it usable.

Then I came across the link to this kit.  It’s an 8-bit console kit that seems fairly simple for a starter project and has good instructions. It seems just right for getting into some hardware work. The console itself (although only 8bit) uses S-Video or AV connectors and flash memory (instead of archaic co-ax cables and cartridges)

I’m excited to get started into a new (different) project!

Self Computers, Console, Hardware, Project

This is an automated message from corporate I.T.

We shut down your computer last night.  Oh, we installed some updates first.  You are too dumb to manually install updates, so we force them upon you at inconvenient times.

Sorry for any inconvenience, loss of data, waste of time, closing all your browser pages, etc.

Enjoy getting back to that state in the morning.

Self, Software Computers, incompetence, inconvenience

I almost missed this.  Here’s a video of a very smart chap (Stephen Fry) celebrating 25 years of Free Software.  In doing so he provides a clear and simple insight into the meaning and importance of freedom.

http://www.gnu.org/fry/

Self, Software Computers, Freedom, GNU, Software

I finally did something I should have done a long time ago and bought a macBook. It’s wonderful – like Linux only hardware works; like Windows only it doesn’t look like crap…and hardware works.A lot of thing on Windows I had started to take for granted: “If I want to do this, I must first do that” or “This works when that is already running” but OSX seems to take care of a lot of this stuff under the bonnet, so to speak.

The Mac came with a plethora of software for it’s internal peripherals and features – web browsing, photo software, iTunes, quicktime – pretty much what you’d expect. Further to this the apple development tools is a free package adding a good gigabyte of extra tools, SDKs, documentation and utilities. Add to that Mactex and Emacs and you’ve pretty much got a complete development station.Package management is dead easy – in most cases simply dragging the application into the ‘applications’ directory.

The User Interface is very smooth without being obnoxious. I for one am very fond of seeing windows slide off the screen and back in… my brain seems to comprehend window management when bits and pieces move around for it.If I have but one complaint, it’s that I seem to require almost an entire installation of Gnome just to get Gimp up and running: It may be time to explore the image editing market again.

[edit] It turns out there is now a rather nice Gimp package for OS X.

Computers, Development, Geek, fun, life Computers, fun, Geek, mac, unix