How to print really large numbers within a tribonacci sequence

Question

So i recently did a university exam and one of the questions asked us to create a program that would print out the nth number in the tribonacci sequence (1,1,1,3,5,9,17,31...). These numbers were said to go as large as 1500 digits long. I created a recursive function that worked for the first 37 tribonacci numbers. But a stack overflow occurred at the 38th number. The question had warned us about this and said that we would somehow need to overcome this, but i have no idea how. Were we meant to create our own data type?

double tribonacci(int n){
    if(n < 4){
        return 1;
    }else{
        return tribonacci(n-3) + tribonacci(n-2) + tribonacci(n-1);
    }
}

int main(int argc, char *argv[]){
    double value = tribonacci(atoi(argv[1]));
    printf("%lf\n", value);
}

This is the solution i wrote under exam conditions, which was within 15 minutes.

The program took the value of n from an input in the command line. We were not allowed to use any libraries except for stdlib.h and stdio.h. So with all that said, how might one create a data type large enough to print out numbers with 1500 digits (since the double data type only holds enough for up until the 37th tribonacci number)? Or is there another method to this question?

Answer 1

You should use some arbitrary-precision arithmetic library (a.k.a. Bigints or bignums) if your teacher allows them. I recommend GMPlib, but there are others.

See also this answer (notably if your teacher wants you to write some crude arbitrary precision addition).

Answer 2

You require a different algorithm. The code posted cannot suffer from an integer overflow, as it does all its calculations in doubles. So you are probably getting a stack overflow instead. The posted code uses exponential time and space, and at N=38 that exponential space is probably overflowing the stack. Some alternatives, in increasing order of efficiency and complexity:

1. Use the "memoization" technique to optimize the algorithm you have.
2. Build up the answer starting by calculating N=4, and iterating upwards. No recursion is then needed.
3. Do the mathematics (or find someone who can) to get the "closed form solution" that allows direct calculation of the answer. See https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression for how this works for regular fibonacci numbers.

You will also need a "big number" data structure - see other answers.

Answer 3

For a development time limited exam solution, I'd definitely go for the quick & dirty approach, but I wouldn't exactly complete it within 15 minutes.

The problem size is restricted to 1500 characters, computing tribonacci indicates that you will always need to carry subresult N-3, N-2 and N-1 in order to compute subresult N. So lets define a suitable static data structure with the right starting values (its 1;1;1 in your question, but I think it should be 0;1;1):

char characterLines[4][1501] = { { '0', 0 }, { '1', 0 }, { '1', 0 } };

Then define an add function that operates on character arrays, expecting '\0' as end of array and the character numbers '0' to '9' as digits in a way that the least significant digit comes first.

void addBigIntegerCharacters(const char* i1, const char* i2, char* outArray)
{
    int carry = 0;
    while(*i1 && *i2)
    {
        int partResult = carry + (*i1 - '0') + (*i2 - '0');
        carry = partResult / 10;
        *outArray = (partResult % 10) + '0';
        ++i1; ++i2; ++outArray;
    }
    while(*i1)
    {
        int partResult = carry + (*i1 - '0');
        carry = partResult / 10;
        *outArray = (partResult % 10) + '0';
        ++i1; ++outArray;
    }
    while(*i2)
    {
        int partResult = carry + (*i2 - '0');
        carry = partResult / 10;
        *outArray = (partResult % 10) + '0';
        ++i2; ++outArray;
    }
    if (carry > 0)
    {
        *outArray = carry + '0';
        ++outArray;
    }
    *outArray = 0;
}

Compute the tribonacci with the necessary number of additions:

// n as 1-based tribonacci index.
char* computeTribonacci(int n)
{
    // initialize at index - 1 since it will be updated before first computation
    int srcIndex1 = -1;
    int srcIndex2 = 0;
    int srcIndex3 = 1;
    int targetIndex = 2;

    if (n < 4)
    {
        return characterLines[n - 1];
    }
    n -= 3;
    while (n > 0)
    {
        // update source and target indices
        srcIndex1 = (srcIndex1 + 1) % 4;
        srcIndex2 = (srcIndex2 + 1) % 4;
        srcIndex3 = (srcIndex3 + 1) % 4;
        targetIndex = (targetIndex + 1) % 4;
        addBigIntegerCharacters(characterLines[srcIndex1], characterLines[srcIndex2], characterLines[targetIndex]);
        addBigIntegerCharacters(characterLines[targetIndex], characterLines[srcIndex3], characterLines[targetIndex]);
        --n;
    }

    return characterLines[targetIndex];
}

And remember that your least significant digit comes first when printing the result

void printReverse(const char* start)
{
    const char* printIterator = start;
    while (*printIterator)
    {
        ++printIterator;
    }
    do
    {
        putchar(*(--printIterator));
    } while (printIterator != start);
}


int main()
{
    char* c = computeTribonacci(50); // the real result is the array right-to-left

    printReverse(c);
}

As said, this is kindof quick & dirty coded, but still not within 15 minutes.

The reason why I use a separate char per decimal digit is mainly readability and conformity to the way how decimal math works on pen&paper, which is an important factor when development time is limited. With focus on runtime constraints rather than development time, I'd probably group the numbers in an array of unsigned long long, each representing 18 decimal digits. I would still focus on decimal digit groupings, because this is a lot easier to print as characters using the standard library functions. 18 because I need one digit for math overflow and 19 is the limit of fully available decimal digits for unsigned long long. This would result in a few more changes... 0 couldn't be used as termination character anymore, so it would probably be worth saving the valid length of each array. The principle of add and computeTribonacci would stay the same with some minor technical changes, printing would need some tweaks to ensure a length 18 output for each group of numbers other than the most significant one.

Answer 4

You need to replace the + operation with an operator ADD made by yourself and encode BigIntegers as you wish -- there are lots of ways to encode BigIntegers.

So you need to define yourself a datatype BigInteger and the following operations

ADD : BigInteger, BigInteger -> BigInteger 
1+  : BigInteger -> BigInteger
2-  : BigInteger -> BigInteger
<4  : BigInteger -> boolean
The constants 1,2,4 as BigInteger

and after having replaced these things write a standard function to compute fibb in linear time and space.