Tuesday, November 6, 2007

Weird Obsession With Fibonacci Numbers - Brute Force Scripting!

Every once in a while, I cruise shell, perl and other unix/linux forums and try to help people out by answering questions and, inevitably, learning more than I impart.

The reason I mention this is the reason for today's post and it's strange title. For some reason, lately, lots of folks have been looking for code to list out Fibonacci numbers up to the highest number equal to or lesser than the one given on the command line as an argument. Of course, I smell a homework assignment here, but, why not just do it anyway?

Of course, even though I'd heard of the numbering sequence and formula, I looked at Wikipedia's Definition to make sure I remembered the sequencing correctly.

Then I thought I'd write a script as fast as I could to complete this task. It reminded me again of another very interesting principle. You can get a lot done in a very short period of time by being totally inefficient. It's especially o.k. if it's not your homework that you're doing ;)

For example, take this script that I whipped up in a few minutes. It takes an argument of one number (the outer delimiter) and it will print out all the Fibonacci numbers up to that argument value, unless that number value isn't a Fibonacci number, in which case it will print up to the last Fibonacci number less than that argument.

The incredibly lame script:

#!/bin/ksh

#
# 2007 - Mike Golvach - eggi@comcast.net
#
#

final_number=\$1
if [ -z \$final_number ]
then
echo "No delimiter given. Exiting"
exit 1
fi
if [ \$final_number -eq 0 ]
then
print "0"
exit 0
elif [ \$final_number -eq 1 ]
then
print "0 1 1"
exit 0
else
print -n "0 "
first_number=1
fib=1
fi
start=1
while [ \$fib -lt \$final_number ]
do
if [ \$start -eq 1 ]
then
print -n "1 "
last_number=0
next_number=1
start=0
fi
let fib=\$last_number+\$next_number
last_number=\$next_number
next_number=\$fib
if [ \$fib -le \$final_number ]
then
print -n "\$fib "
fi
done
echo
exit 0

sample output:

\$ ./fibo.sh 100000
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025

Less than a page of code and not much thought put into making an efficient script. I decided to call it "Brute Force Scripting." Hey; sometimes your time is better spent not worrying about making things look pretty. If you get the job done and it's your job to get the job done, getting the job done is job number one ;)

, Mike