Calculating numbers that require greater than 16 byte data type in C++

I'm working on a function to calculate Fibonacci numbers and return the lowest value digit of that number in C++. I've found that in C++, the largest data type is __uint128_t, which gives me 16 bytes to work with. I wrote an overload to handle streaming __uint128_t. This will calculate up to the 186th Fibonacci number and then overflow at 187. I need to go much higher than 186. This is my function:

__uint128_t get_fibonacci_last_digit_fast (int n)
{
    __uint128_t f[n];

    f[0] = 0;
    f[1] = 1;

    for (int i = 2; i < n + 1; i++)
    {
        f[i] = f[i - 1] + f[i -2];
    }

    return f[n] % 10;
}

I am aware of boost library and other libraries that assist with handling large data in C++, but this function is for an assignment that has to be submitted to an auto grader which doesn't have these libraries installed. There is only the standard C++ libraries, so my code doesn't compile when submitted with these libraries. I'm considering possibly building a data type to handling this issue. Any direction and assistance with proceeding forward will be greatly appreciated.

Solution

If you only need the last digit, you can use the Pisano period:

#include <iostream>

int get_last_digit(unsigned long long n)
{
    n %= 60;

    if (n <= 1)
        return n;

    int prev = 0;
    int curr = 1;

    for (int i = 2; i <= n; ++i)
    {
        int next = (prev + curr) % 10;
        prev = curr;
        curr = next;
    }

    return curr;
}

int main()
{
    unsigned long long n = 10000000000008989ULL;
    std::cout << get_last_digit(n) << "\n";
}

Prints

Notes:

The Pisano period for % 10 is 60. We can manually list the Fibonacci sequence modulo 10 until we see a repeat of the initial 0, 1 pattern:

0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1, ..., 0, 1

The sequence 0, 1 repeats after 60 numbers. Therefore, we can use a precomputed array to efficiently get the last digit for n modulo 60 in O(1) time complexity:

#include <iostream>

int get_last_digit(unsigned long long n)
{
    const int pisano[60] = {
        0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1,
        5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6,
        5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1};

    return pisano[n % 60];
}

int main()
{
    unsigned long long n = 10000000000008989ULL;
    std::cout << get_last_digit(n) << "\n";
    return 0;
}