Output a huge number with 200,000 digits

Question

I am trying to output a number with 200,000 digits and not sure how I can store it? The task is to compute the 1 millionth fibonnacci number, so it would be a formula outputting 200,000+ digits. In other words, saving the output somehow of the calculation so that I can then output.

size_t longnumber; // number with 200,000 digits
cout << longnumber;

Answer 1

Your problem seems to include both calculation of this number and the storing and printing it.

I will suggest using vector to store the number and to grow it as you keep on adding your fibonacci list

for e.g 1 1 2 3 5 8 13

std::vector<int> res;

std::vector<int> prev;

res[0]=1         prev[0]=0
res[0]=1         prev[0]=1 
res[0]=2
res[0]=3
res[0]=5
res[0]=8
res[0]=1 res[1]=3    prev[0]=8

Code : it's just minimum example for POC

std:vector<int> prev{0};
std:vector<int> res{1}

add(){
       for(auto a=res.size();a>=0;--a){
          for(auto b=prev.size();b>=0;--b){
              temp=res[a]+prev[b];
               if(temp > 9){
               // take carry and redo the add 
 } 

}
}

Answer 2

You could use the standard approach for calculating Fibonacci numbers like in the following simple algorithm.

constexpr unsigned long long getFibonacciNumber(size_t index) noexcept {
    unsigned long long f1{ 0ull }, f2{ 1ull }, f3{};
    while (index--) { f3 = f2 + f1; f1 = f2; f2 = f3; }
    return f2;
}

But, even using the 64 bit data type unsigned long long it will overflow after the 93rd Fibonacci number.

So, what we need is some "very big" data type. And here I propose a std::vector of digits. And as digit we will use an unsigned char.

For the following we will talk about "Digit" and "Digits" meaning an unsigned char and a std::vector<unsigned char>.

For adding 2 Digits, we will use the method that we learned in school, when we were 7 years old. We add all single digits, and if there is an overflow over 10, we use it as "carry over" and add it the next time. That is rather simple.

Then we build an operator + for 2 "Digits", taking a little bit care about different number of elements in Digits and employ the simple "add" algorithm.

The code will then look like this:

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <fstream>

using Digit = unsigned char;
using Digits = std::vector<Digit>;

// Unoptimzed adder for vector of Digits
Digits operator + (const Digits& d1, const Digits& d2) {

    // This will produce many not needed leading 0's
    const size_t ResultSize = std::max(d1.size(), d2.size()) + 1;

    // The result of the additions
    Digits result(ResultSize, 0);

    // The carry over from a addition of 2 digits
    unsigned char carry = 0;

    // Size of vecors is different. Prevent overflows. Calculate from right to left
    int indexD1 = static_cast<int>(d1.size()) - 1;
    int indexD2 = static_cast<int>(d2.size()) - 1;
    int indexResult = static_cast<int>(result.size()) - 1;

    // Now add each digit in the vector of digits
    for (size_t index{}; index < ResultSize; ++index) {
        const unsigned char sum = carry + (indexD1 >= 0 ? d1[indexD1] : '\0') + (indexD2 >= 0 ? d2[indexD2] : '\0');
        result[indexResult--] = sum % 10;
        carry = sum / 10;
        --indexD1;
        --indexD2;
    }
    return result;
}

// Basically standard approach for calculating Fibonacci Numbers
Digits getFibonacciNumber(size_t index)  {
    Digits f1{ 0 }, f2{ 1 }, f3{ 0 };
    while (index--) { 
        f3 = f2 + f1; 
        f1 = std::move(f2); 
        f2 = std::move(f3); 
    }
    return f2;
}

int main() {
    if (std::ofstream oss("r:\\fibo.txt"); oss) {

        // Calculate Fibonacci number for 1000000
        Digits result = getFibonacciNumber(1000000);

        // Show output. Suppress leading zeroes
        bool showZeros{ false };
        for (const unsigned int i : result) {
            if ((i != 0) || showZeros) {
                oss << i;
                showZeros = true;
            }
        }
        oss << '\n';
    }
    return 0;
}

Resulting in a Fibonacci number with 208980 digits.

Since I used a 0-optimized version, the runtime for the calculation will be really long.

So, happy calculating . . .

I will later create an optimized version.

---

EDIT

I tried to optimize as much as I could. But still for the 1'000'000th Fibonacci Number I still need 403s to calculate the 208980 digit result.

Please see the code below

#include <iostream>
#include <array>
#include <algorithm>
#include <chrono>

constexpr size_t MaxDigits = 250'000u;

using Big = std::array<unsigned char, MaxDigits>;
std::array< Big, 3> f{};

int main() {

    size_t index = 100000u;

    auto start = std::chrono::system_clock::now();
    std::array<size_t, 3> sf{};
    std::array<size_t, 3> indexF{ 0,1,2 };

    f[indexF[1]][0] = 1;
    sf[indexF[1]] = 1;
    size_t i{};

    unsigned char carry{};
    while (index--) {

        const size_t indexF0 = indexF[0];
        const size_t indexF1 = indexF[1];
        const size_t indexF2 = indexF[2];

        const size_t sf0 = sf[indexF0];
        const size_t sf1 = sf[indexF1];
        const size_t maxSize = std::max(sf0, sf1);

        for (i = 0; i < maxSize; ++i) {

            const unsigned char f0 = f[indexF0][i];
            const unsigned char f1 = f[indexF1][i];

            const unsigned char sum = carry + f0 + f1;

            (f[indexF2])[i] = sum % 10;
            carry = sum / 10;
        }
        if (carry) {
            f[indexF2][i] = carry--;
            ++sf[indexF2];
        }
        else
            sf[indexF2] = maxSize;

        std::rotate(indexF.begin(), indexF.begin() + 1, indexF.end());
    }

    auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - start);
    std::cout << "Time: " << elapsed.count() << " ms\n\nNumber of digits: " << sf[indexF[0]] << "\n\n";

    //for (int k{ static_cast<int>(sf[indexF[0]])-1 }; k >= 0; --k) std::cout << static_cast<int>((f[indexF[0]])[k]);
    std::cout << "\n\n";
    return 0;
}

I am wondering, what else I could do to improve further . . .