The Billionth Fibonacci Number

[pixelherder]

A few weeks ago, rockstarling wrote a post about calculating large Fibonacci numbers. Never one to resist a program challenge, I really wanted to try my hand at it and see if I could write an even faster program for calculating Fibonacci numbers. At the time, I was rather busy working on a paper but that's done now, so I gave it a shot today.

Comments

[lindseykuper]

*whistles*

Awesome! And screamingly fast. I like the bitwise successive squaring thing, and I'm...trying to understand the rest.

I still like the fact that you can do it in Scheme without any special libraries.

[jes5199]

the GMP library is really, really nice. And if you use the C++ bindings, it's almost invisible.
It's so good that I just assumed that most GNU languages with Bignum/Bigint types would be using it be using GMP internally. Not true! This seems to be a bizarre application of Greenspun's Tenth Rule of Programming, where even Scheme has re-invented the wheel.

[lindseykuper]

I just realized that it's what oniugnip has been talking about all this time when he's been talking about "the bignum library".

[pixelherder]

Yep, mzscheme actually uses GMP under the hood.