When I was studying for my Computer Science degree back in the early 1990s, I had the opportunity to take a module which would have involved Prolog. For whatever reason, I took an alternative. When I saw it was in Bruce Tate’s Seven Languages in Seven Weeks, Prolog was the language I was looking forward to trying after so many years.
After reading Day 1, I was anxious to have a crack at implementing the Fibonacci Sequence – just as I had already done for Io Language from the previous chapter. Remembering that for Io, this was an optional exercise, I looked ahead to see if it was also there after Prolog’s Day 2. While it is mentioned, it was merely suggesting that you search over the internet to examine other people’s solutions. I decided to read Day 2 of Prolog, then have a crack at it myself – I’d learn more after all.
It took me a while to get it working, but it did help me understand the language a bit better. I took the same approach as I had with Io – have a bash, evaluate, then consider a unit testing framework to let me TDD it afterwards. Why is it that no books on learning new languages start with showing you the unit testing framework? That’s how I want to learn languages and I don’t think I can be the only one!
So, here’s my first attempt at it. Like the book, I’m using GNU Prolog. And like my Io implementation of the Fibonacci Sequence, it is very fast. Unlike Io, it seems to go a bit haywire! What’s going on?
fib(87, What). => 679891637638612258 fib(88, What). => 1100087778366101931 fib(89, What). => -525863593208979763
Well, goodness me! First, for some implementations, these are pretty big numbers. My attempt with Io had already lost precision before this point (the 88th number in the sequence comes back with 1.100088e+18). However, the last time I checked, when you add together two large positive integers, the result is never negative.
So how does GNU Prolog represent the number? Could we be overwriting the bit that holds the sign? Well, the correct result is 1779979416004714189. If we look at this number in binary, we find that the leftmost bit set is the 61st. Not the 64th that might be more suspicious! However, it seems that any time this particular bit is set, then the number comes out negative.
Trying to understand what was going on, I stumbled across this link. Half way down the page, there’s an implementation of Fibonacci. I tried this out, and sure enough it has exactly the same issue. Just after the Fibonacci example, however, there’s another one on Factorials, with the following caveat:
But 12! is only 479001600. So, maybe that was run on a 32 bit machine? A likely theory perhaps? Well, looking at 479001600 in binary, we find that the leftmost bit set is bit 29. 61 – 32 = 29. So its looking highly probable thats the explanation! When I tried the same program for factorials on my mac (well, they’ve been 64 bit for some time now folks!), it had no trouble with 12!, coming to an incorrect result at 23!.
So, it seems my Fibonacci implementation reached the highest number that the GNU Prolog supports on 64 bit (that would be 1152921504606846975 in decimal). Can we get any higher?
As the above text suggests that SWI-Prolog “handles large numbers just fine”, it seemed like I had to get it running on my mac. I downloaded the latest Mac OSX binary for 10.6 (yikes – thats Snow Leopard… my first Mac in 2010 had that!) – although you need Lion for the “graphical application”. Apparently that needs “xquartz (X11)” – that turns out to be X-Windows (another flashback to University in the early 90’s!) which also happened to be shipped with my first mac! My first thought was that I wasn’t interested in the development tools – I wanted to see how big the numbers went! Once installed (and without xquartz), SWI-Prolog was somewhat flaky: almost anything I did at the prompt resulted in it crashing. I’m not yet adept enough to work out whats going on, and I wasn’t feeling like building the thing from source.
SWI Prolog looks to be a different beast to GNU Prolog, with development tools and someone has even made a plugin for IntelliJ. After some playing about, I found that I could give it an absolute path to my source file, and hey presto – it compiled ok.
Turns out that the 89th Fibonacci number is 1,779,979,416,004,714,189.
The 100th is: 354,224,848,179,261,915,075, and the 200th is 280,571,172,992,510,140,037,611,932,413,038,677,189,525!! I’m not sure how high it will go, but it seems it will only be constrained by the available memory, and how long you’re prepared to wait for the answer! While all the examples up to now give an instant response, I had to try the 100,000th before I noticed any delay between asking for the result and getting it. I tried my luck at the 1,000,000th number in the sequence, and after about 10 seconds it came back with the result. And by the looks of things, its accurate. Rather than paste a really big number here that would simply look ridiculous, suffice it to say that its approximately 1.95 x 10^208987. I don’t think I need to go further!
Well, I still haven’t TDDed the Fibonacci implementation. I couldn’t find anything to help with that using GNU Prolog, but there seems to be a unit testing framework for SWI-Prolog. Maybe I’ll take a look into that soon, but Day 3 of the Prolog chapter now beckons.