## Sunday, June 04, 2006

### A Dare

I have a simple dare. In fact, it's a triple dog dare to all developers. Are your ready? Here it is:

Stop using the same examples to show how great your favorite technology is.

Programming in general has "Hello, World" and every beginning programming book uses it. Even worse is the heavy use of "foo bar" in all its forms. Used to be cute, but not any more.

But, the worse by far is the fibonacci sequence used by every beginning functional programming article to prove the elegance of recursion or functional pattern matching. Come on. There are examples that prove it much better (pick anything in the real world). And that leads me to the final one...

ATMs are used as the example in almost every book in OO design. It's played to death and no longer interesting. Certainly, there's better examples than that out there now, right? And no, don't continue with the bowling example. It's already a cliche in all of the agile books.

Computer science is an exciting field filled with untapped potential and great ideas. But, cliched examples, while good for comparisons, fall flat in their simplicity. Fibonacci doesn't show the elegance obtained from functional programming. Much like showing that you can create a function to add one to prove the elegance of closures. I think a meatier example grounded in the real world will excite the reader much more. This is my dare. Dare to write an original example that makes me realize how clever you are and not @#\$%^& ANOTHER FIBONACCI EXAMPLE?!

Andrés said...

Interestingly, mathematics suffers from the same disease. Typically, books will describe all this beautiful theory and finish it off with the next to simplest possible example or application. No good.

Andrés said...

Also, it would be much more interesting to show how some of the properties of the Fibonacci sequence could be used to calculate very large F numbers quite efficiently. For example, it is well known that

F(a+b) = F(a+1) F(b) + F(a) F(b-1)

This may say nothing at first, until you want to calculate F(n) and break n in halves. Assuming n = 2k, then

F(n) = F(k+k) = F(k+1) F(k) + F(k) F(k-1)

or

F(n) = F(k) (F(k+1) + F(k-1))

So if you break n in "good" values of k, you can cache those triplets around say powers of two, and then you're cooking with gas.

A long time ago, I had implemented fibonacci as the naive sum of terms, and F16525 took so long I had to stop it. With this new algorithm, it took only 10 seconds the first time, and 1.5 seconds the next time. Simple examples also hide this kind of stuff away.

Think, Luke... use the force but do not be brute!

Andrés said...

And if memory serves right, this is how I found that

F(p^n) ? p (100)

Some friends extended the full precision calculator into a mod calculator, applied the mu and lamdba algorithm as shown in Knuth's books, and found that there were MANY OTHER SUCH CONGRUENCES...

brody2 said...

There's an online book "http://users.impulse.net.au/dragoncity/smalltalk_for_mere_mortals.pdf" that has a decent example of recusion. The example on recursion is to print a check amount as text. i.e: \$10.00 prints as Ten Dollars and zero cents.

I haven't looked closely at the code, but there ya go. A non-Fibonacci example.

brody2 said...

http://users.impulse.net.au/dragoncity/smalltalk_for_mere_mortals.pdf

Contains a reasonable example of recursion in the chapter titled PROGRAMMING WITH RECURSION.