Generating large Fibonacci numbers with C++

EDIT: This is a really, really stupid way of handling large numbers in C++. It is a nice proof of concept in terms of how you can do the ‘unit addition’ that you might have learnt in school pragmatically, but if you really want to be handling large numbers you need to be using something like GMP.

This morning I set myself the challenge of writing a Python program to generate large Fibonacci numbers, however I later rewrote it in C++ and it worked a lot better, so I’ve stuck with the C++ version. In fact, execution times were up to 60 times faster in C++.

The main problem I had is the limitations of standard integer types in C++. A 32bit, unsigned long will limit you to just over 4 billion. A 64bit, unsigned long will limit you to roughly 1.844 x 10^19, which gives you about 20 digits. The problem is that the 48th and 93rd numbers in the Fibonacci sequence will exceed these limits respectively. Therefore I created an alternative solution.

I basically ended up storing numbers in strings and then splitting them into a single character array before adding them, effectively doing column addition digitally. Whilst this is ridiculously inefficient for the smaller Fibonacci numbers (i.e. less than 2^64), it will happily allow you to calculate numbers significantly higher than the limits of your CPU.

Annoyingly the executable is quite large (on Windows) and I have to include the vector library so I can have variable length arrays but other than that minor issue the program will run ridiculously quickly – I can calculate the first 50,000 in a matter of seconds although anything exceeding this takes significantly longer.

If you’re using GCC then you could probably adapt this and reduce executable size by replacing the vector stuff with VLAs but I was using the VC++ compiler so I couldn’t and I wanted this to work cross platform. Here is the full source code (I’m going for Apache license even though there isn’t much of it):

/*
 Copyright 2012 Programming Thomas
Licensed under the Apache License, Version 2.0 (the "License");
 you may not use this file except in compliance with the License.
 You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
 distributed under the License is distributed on an "AS IS" BASIS,
 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 See the License for the specific language governing permissions and
 limitations under the License.

 To compile with VC++ use the VS command line and cl /Ox fibonacci.cpp
 To compile with G++ use g++ -o fibonacci fibonacci.cpp
*/
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
std::string intToString(int s)
{
 std::string toReturn = "";
 while (s > 0)
 {
 char v = s % 10 + 48;
 toReturn = v + toReturn;
 s = (s - (s % 10)) / 10;
 }
 return toReturn;
}
int stringToInt(std::string s)
{
 int v = 0;
 for (int n = 0; n < s.length(); n++)
 {
 if (s[n] >= 48 && s[n] < 58) v = (v * 10) + s[n] - 48;
 else break;
 }
 return v;
}
std::string add(std::string a, std::string b)
{
 std::vector<char> aList;
 int n;
 for (n = 0; n < b.length(); n++) aList.push_back(b[n] - 48);
 int offset = b.length() - a.length();
 for (n = 0; n < a.length(); n++) aList[n + offset] += a[n] - 48;
 for (n = aList.size() - 1; n > 0; n--)
 {
 aList[n - 1] += (aList[n] - aList[n] % 10) / 10;
 aList[n] = aList[n] % 10;
 }
 std::string toReturn = intToString(aList[n]);
 for (n = 1; n < aList.size(); n++) toReturn += 48 + aList[n];
 return toReturn;
}
int main(int argc, char* argv[])
{
 if (argc > 1)
 {
 int SIZE = stringToInt(argv[1]);
 std::cout << "Going to calculate the first " << SIZE << " terms." << std::endl;

 std::string a = "1", b = "1", c;
 std::ofstream file;
 file.open(("fib" + intToString(SIZE) + ".txt").c_str());
 file << "1";
 for (int i = 2; i <= SIZE; i++)
 {
 file << std::endl << b;
 c = add(a,b);
 a = b;
 b = c;
 }

 std::cout << "Calculated values and written to file";
 file.close();

 return 0;
 }
 else
 {
 std::cout << "You should supply a number of items (fibonacci 100 for example)" << std::endl;
 return 1;
 }
}

Please click here for the raw source file and here for the EXE. To use the program, open up a command line and execute fibonacci followed by the total number of numbers you wish to generate. It will then output this to an appropriately named text file.

Note that because a rather large amount of text gets written to a file whilst the program is running (it isn’t possible to cache it before writing because generating anything above 100,000 items is going to use a lot of RAM) it is probably worthwhile running this on a reasonably fast hard disk or SSD rather than a USB drive.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s