I found the perl module Math::Fibonacci which uses this relationship to calculate the n-th Fibonacci number using the fast algorithm:

F(n) = ~ g^n/sqrt(5)

where g is the golden ratio and ~ means “take the nearest integer.”

I experimented a bit with that algorithm and it is quite useful for Fibonacci values that can be expressed within the precision of native floats. To get beyond the limitations of native floats, I used Math::BigFloat. Unfortunately, it took much longer to get results than just using the trivial expansion with Math::BigInt, and those results were not exact.

Then I found Math::Big which has a fibonacci function. In scalar mode, it uses a very fast divide-and-conquer algorithm based on the formula:

F(n+m) = Fm * Fn+1 + Fm-1 * Fn

Using Math::Big::fibonacci, I can calculate the 10,000-th Fibonacci number in 0.37 seconds with this command line:

perl -MMath::Big -e 'print 0+Math::Big::fibonacci($ARGV[0]),"\n"' 10000

It takes about 2.5 seconds to get the same result with the trivial expansion using the code I posted yesterday.

[/programming] [link]

Sat, 27 Mar 2004

Counting Fibonacci numbers

I need to stop this silliness. Couldn’t sleep, so I got up early and played with perl and Fibonacci numbers some more.

The latest incarnation prints the n-th Fibonacci number where n is passed as an argument. Here, n is 1000:

perl -MMath::BigInt -e '$b=new Math::BigInt 1;($a,$b)=($b,$a+$b)while--$ARGV[0];print"$b\n"' 1000

That’s assuming Fibonacci numbers begin with one instead of zero. I’ve seen them described both ways. Is zero a Fibonacci number?

[/programming] [link]

Sat, 20 Mar 2004

Fibonacci numbers

I’ve been reading GEB. Hofstadter loves Fibonacci numbers.

This morning I got up early and read a section in GEB while the house was quiet and the sun was coming up. To test understanding, Hofstadter listed several items, some well formed, some not. As an answer key, he wrote, “Those whose numbers are Fibonacci numbers are not well formed.”

On a sheet of paper I wrote the Fibonacci sequence far enough to check the answers. Then, just to exercise tired brain cells, I started adding as fast as I could to extend the sequence.

I had about 80 numbers written when I grew weary of the exercise. But staring at the page of digits, I couldn’t rest without knowing if and where I had made any errors.

So, I headed down to the computer and wrote a couple of perl one-liners.

I love Perl, and I especially enjoy writing little one-liners I can execute from the command line without having to create a source file. My first attempt looked like this:

perl -e '@f=(1,1);print$f[@f]=$f[-1]+$f[-2],"\n"while@f<80'

That resulted in the last few terms printing in scientific notation, e.g., 2.34167283484677e+16. I wanted the full integer representation. The final version prints the term number and the full integer representation using the the Math::BigInt module. It also takes the number of terms as an argument and the command line shown pipes the output to less for easy viewing.

perl -MMath::BigInt -e '$one=Math::BigInt->new(1);
@f=($one,$one); print@f+1,": ",$f[@f]=$f[-1]+$f[-2],
"\n"while@f<$ARGV[0]' 80|less

[/programming] [link]

Thu, 18 Mar 2004

Bob Somrak’s photos

Bob Somrak has started a website featuring his photography. Bob and my father graduated from the Colorado School of Mines together. Dad had gone back to school when I was in grade school and graduated when I was about 10 years old. After he graduated, we moved to Paonia, Colorado, Bob's home town.

Bob is partly responsible for my interest in mathematics and computers. He stopped by the house often during my junior high and high school years. He and Dad included me in some fascinating discussions that motivated me to learn more.

Dad was a very private person and chose his friends carefully. Bob was at the top of a short list of people Dad truly loved and considered close friends.

Enjoy Bob's pictures. He lives in some truly beautiful country I sorely miss.

[/general] [link]

Tue, 16 Mar 2004

Hofstadter’s Law

I’ve been reading Gödel, Escher, Bach (GEB). It is a book I’ve owned for many years. At least once before, I made an attempt to read it. It is not, however, a quick, easy read. There’s a certain amount of determination required. After having GEB on my bedside reading table for many months, occasionally thumbing through it reading random sections and admiring the Escher drawings, I’ve begun a front-to-back read in earnest.

One of the many gems I’ve discovered so far is Hofstadter’s Law:

It always takes longer than you expect, even when you take into account Hofstadter’s Law.

Anyone in software development is intimately familiar with Hofstadter’s Law whether they know it by that name or not.

Jonathan Lundquist and I coined our own version of Hofstadter’s Law in an even tighter loop than Hofstadter’s. In fact, it addresses why things take longer. Let’s call it Marc and Jon’s Law:

Everything is harder than it is.

[/general] [link]

Mon, 15 Mar 2004

CV Spring Craft Show

Jenny had a booth at the CV Spring Craft Show this weekend. It was a real disappointment for her. Worked 14 hour days for a couple of weeks making some really cute items for the show, but nothing sold.

If you’re interested in a cute, meticulously painted, hand crafted Easter-egg holder, e-mail me. She’s selling them for $35, each. Click the image above for a better view.

[/personal] [link]

Sat, 06 Mar 2004

Mom’s music preservation project

Mom sent me about 35 stereo cassette tapes of her favorite music. The tapes are aging. She asked me to transfer the music to CDs so she can listen to her music on her new CD player.

I bought a decent stereo cassette deck on eBay for about $15. At my local Radio Shack, I picked up a cable to connect the RCA output to my sound card. I've been using a snd to record each tape to a WAV file. Then I use snd to extract each song into a separate file. I use cdrecord to burn CDs with a track for each song.

Her new CD player is supposed to play MP3 files. So, I've been using lame to encode MP3 files for each track. When I've finished creating normal, audio CDs, I'll create a couple of CDs for her with the MP3s files. They may prove to be more manageable.

[/general] [link]

Jenny has a new bike

Looks like a nice sunny day. We had snow yesterday. If it warms up into the 40s, we'll go for a bike ride today.

Jenny got a new bike last weekend—something we've been planning since last summer. We took the bike, a Specialized Dolce Elite, out for a test ride last weekend. The ride was great, the fit was great, and Jenny came home with a new bike.

Now, she'll get to do her turns up front—no excuses.<g>

[/cycling] [link]