Computing the 1 millionth fibonacci number

Question

I am trying to compute the 1 millionth fibonacci number using the Big Int Library since the number is more than 200,000 digits. I can't seem to fix this problem I am having when taking the sqrt or pow, Big Int can't be assigned to pow or sqrt.

BigInteger Phi = (sqrt(5) + 1) / 2;

BigInteger phi = (sqrt(5) - 1) / 2;

BigInteger PhiSquared = pow(Phi, n);
BigInteger phiSquared = pow(phi, n);

Nevermind `pow`, but why would you think that `Phi` is an integer? — dxiv, Mar 09 '21 at 05:07
I assigned Phi as a BigInteger, so I just want to take the pow of Phi to the n power. — Silvia Ramirez, Mar 09 '21 at 05:08
1) There is no `BigInteger` in standard C++, so you'll need to tell what library you are using. 2) If that's an integer type with standard arithmetic conversions then `Phi` will be truncated to `1` and `phi` to `0`. — dxiv, Mar 09 '21 at 05:10
I am using the "Big Integer Library", and BigInteger is a data type, so I am assigned Phi as the computation of the right side sqrt. Phi is just a name of the variable, its like int Phi, but instead its BigInteger Phi. — Silvia Ramirez, Mar 09 '21 at 05:11
It might be because I am using math.pow instead of the biginteger.pow, so there's a conversion error from double precision float to a big integer. — Silvia Ramirez, Mar 09 '21 at 05:14
You do realize that `int Phi = (sqrt(5) + 1) / 2;` is the same as `int Phi = 1;`. — dxiv, Mar 09 '21 at 05:15
There's no such thing as **the** "Big Integer Library". You'll have to be more specific. — Mark Ransom, Mar 09 '21 at 05:20
I think I may have to use another library because this one is for big integers and I need to do math with decimals to calculate the 1 millionth fibonacci number. — Silvia Ramirez, Mar 09 '21 at 05:24
I've heard of the GMP library but I haven't found a good source on how to install it and use it. All the instruction manuals I've found want me to install several packages and modify paths in my directory, why can't I just download the files like I did for this Big Int library — Silvia Ramirez, Mar 09 '21 at 05:26
This question has [already been addressed](https://stackoverflow.com/questions/66471121/output-a-huge-number-with-200-000-digits#comment117525754_66471121), with one of the comments showing an implementation using the boost library's [cpp_int](http://coliru.stacked-crooked.com/a/80cf9baccf137719) — PaulMcKenzie, Mar 09 '21 at 05:27
@SilviaRamirez Also, the formula you're trying to use (Binet's formula) gives an approximation. It does not exactly calculate what the digits are of the one millionth Fibonacci number. For that, you must actually calculate it in a simple loop using 3 variables. — PaulMcKenzie, Mar 09 '21 at 05:39
@SilviaRamirez The Fibonacci numbers are integers. You can't add two integers and get a non-integer as a result. (If this is school work, it's likely that the entire point of this exercise is that you implement arbitrarily large integers and their addition yourself. Or possibly that you shouldn't actually produce all the digits.) — molbdnilo, Mar 09 '21 at 08:32
There is a closed-form solution. See https://en.wikipedia.org/wiki/Fibonacci_number. Floating point considerations need thought though. — Bathsheba, Aug 11 '22 at 12:53

score 3 · Answer 1 · edited Aug 11 '22 at 12:51

3

If you want to use a library that can handle big integers, the simplest thing is to get the boost library and use the cpp_int type in the multiprecision library.

Since the multiprecision library is header-file only, this would be one of the simplest ones to use right out-of-box with minimal setup.

Here is a simple, straightforward implementation that computes the 1 millionth Fibonacci number without using floating point (which could yield inexact results):

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
 
int main() {
    using Int = boost::multiprecision::cpp_int;
    Int n1 = 0, n2 = 1;
    Int n3;
    for (long i = 1; i <= 1000000; ++i)
    {
        n3 = n1 + n2;
        n1 = n2;
        n2 = n3;
    }
    std::cout << n3;
}

This took around 40 seconds to complete on an Intel I7 laptop, using Visual Studio 2019 in release mode.

The resulting number is a 208988 digit number.

edited Aug 11 '22 at 12:51

Bathsheba

231,907
34
361
483

answered Mar 09 '21 at 05:49

PaulMcKenzie

34,698
4
24
45

Paul this looks promising, let me try this, I'll let you know if I can get it to work on my side. – Silvia Ramirez Mar 09 '21 at 06:00
Since `cpp_int` doesn't require any building of the boost library, all you have to do is download boost, make sure your `include` path is setup correctly to point to the boost headers, and that should be it. Should work under any platform and compiler that supports boost. – PaulMcKenzie Mar 09 '21 at 06:03
There's a lot of files inside of the boost zip file, and not sure which ones to include in my project? Do I just dump all the files into my project? – Silvia Ramirez Mar 09 '21 at 06:04
Would you have an issue with the standard library? Do you try and pick out what you need if you were to use ``, for example? The issue is that your project would have a dependency on boost, no different than it has a dependency on the standard library. You should simply copy the package to a directory, and ensure your include path is set up correctly. Note that the code I linked to actually compiles on many on-line compilers, indicating that boost is available there. The goal is to have the same library locally on your machine. – PaulMcKenzie Mar 09 '21 at 06:07
I get it but I don't know how to do that, the copying to a directory and include path – Silvia Ramirez Mar 09 '21 at 06:14
Unzip the boost file. Look at your directory that is created. Depending on the IDE that you're using (or command line), set up the include path to the base path of the `boost` include directory. This is basic stuff you must be familiar with if you attempt to use any third-party library, boost or no boost (even your original "BigInt" you were talking about). If you want to see what happens if you didn't set anything up, what compiler error would you get if you attempted to compile the code? OK, so work from there in fixing the compiler error. – PaulMcKenzie Mar 09 '21 at 06:15
I unfortunately run into the same problem, I can't do math with floats. The problem involves doing division of non integers and then finally rounding the last calculation to an int. I also have to be able to calculate any (n)th fibonacci number, up to 1 million. – Silvia Ramirez Mar 09 '21 at 07:09
Did you run the code that I posted? If you did, what are the issues? There is no floating point in the code I posted. And note, the loop is set to loop one million times. If you want the nth number, you loop `n` times. – PaulMcKenzie Mar 09 '21 at 07:10
Let me update my code so you can see what I have – Silvia Ramirez Mar 09 '21 at 07:11
I ran your code, but I get fatal error, boost/cstdint.hpp' file not found – Silvia Ramirez Mar 09 '21 at 07:13
So you are now making progress. Set your include path to point to the base include directory for boost. You do see the `cstdint.hpp` file there, don't you? That's the file the compiler is looking for. Also, you did not mention what compiler and/or IDE you're using. – PaulMcKenzie Mar 09 '21 at 07:15
you mean like move the file cstdint.hpp to the same path? so drag it to boost/multiprecision/ ? – Silvia Ramirez Mar 09 '21 at 07:19
I am using Visual Studio Mac version – Silvia Ramirez Mar 09 '21 at 07:20
1

Don't touch any of the boost files. Simply go to the project settings of Visual Studio and set the include path to also find files in the `boost` directory. `Project properties -> C/C++ -> Additional Include Directories` (at least this is how it's done in the Windows version of Visual Studio). – PaulMcKenzie Mar 09 '21 at 07:21
Does it matter if I use " " or < > to add paths? – Silvia Ramirez Mar 09 '21 at 07:32
In the project properties, simply put the entire path, without quotes or brackets. See [this link](https://learn.microsoft.com/en-us/cpp/build/reference/vcpp-directories-property-page?view=msvc-160) – PaulMcKenzie Mar 09 '21 at 07:34
[Here](https://learn.microsoft.com/en-us/cpp/build/reference/vcpp-directories-property-page?view=msvc-160). Do you see the `C / C++` item in that picture? That is the item you should be navigating to and setting the include path. – PaulMcKenzie Mar 09 '21 at 07:40
1

`for (long i = 1; i <= 500000; ++i) n1 += n2, n2 += n1;` seems about [40% faster](http://coliru.stacked-crooked.com/a/5fe038a3aeffae79) – Mooing Duck Feb 21 '23 at 22:28

Computing the 1 millionth fibonacci number

1 Answers1

Linked