Reducing the time complexity of recursive Fibonacci like function in c++

Question

I have been trying to code a solution for a problem in c++.

This has to be solved using recursion only The modulo 10000000007 is not the issue the code takes longer with/without it

The problem: Davis likes to climb each staircase 1, 2, or 3 steps at a time.

Given the respective heights for each of the n staircases, find and print the number of ways he can climb each staircase , modulo 10^10 + 7

Example for n=5

The staircase has 5 steps. Davis can step on the following sequences of steps:

1 1 1 1 1

1 1 1 2

1 1 2 1

1 2 1 1

2 1 1 1

1 2 2

2 2 1

2 1 2

1 1 3

1 3 1

3 1 1

2 3

3 2

There are 13 possible ways he can take these 5 steps and 13 modulo 10000000007 = 13

My solution using recursion so far:

int ways(int n) {
    if(n==1) return 1;
    if(n==2) return 2;
    if(n==3) return 4;
    return (ways(n-3)+ways(n-2)+ways(n-1))%10000000007;
}

The code works perfectly but its taking way too long on big computation. If there is a way to optimize it do share . simpler the solution the better. Thanks.

have you considered `1 << (n - 1)` assuming non-zero values of `n`? — Mgetz, Sep 10 '21 at 15:37
Think [memoization](https://en.wikipedia.org/wiki/Memoization#:~:text=In%20computing%2C%20memoization%20or%20memoisation,the%20same%20inputs%20occur%20again.). Also, limit only comes into play when 3 to the `n`th power exceeds it. — 500 - Internal Server Error, Sep 10 '21 at 15:43
in some array keep track what `ways(x)` return for given `x`. — Marek R, Sep 10 '21 at 15:45
@YashYadav the binary value `0b010` is 2... e.g. one place shifted over... I'd suggest doing some research on how binary numbers work because your first three `if` statements disappear quickly — Mgetz, Sep 10 '21 at 15:46
Note also that `10000000007` is [not a prime number](https://www.wolframalpha.com/input/?i=factorize+10000000007+). So it would be nice to check for Pisano period if it is small it can be used as great leverage. — Marek R, Sep 10 '21 at 15:49
@Mgetz `ways(4)` is `7` not `8` and `ways(5) == 13` and doing this for `n<4` is pointless. — Marek R, Sep 10 '21 at 16:00
Note that 10000000007 is does not fit in 32 bits and so if `sizeof(int)` is 4 (with `CHAR_BITS` set to 8 like on almost all platforms) then there is an overflow issue. This is often the case (even on 64-bit platforms). Thus, this is probably better to use wider types of such a case (eg. `uint64_t`). — Jérôme Richard, Sep 10 '21 at 16:10
@JérômeRichard thanks but that part was not the issue however that info will help me a lot . — Yash Yadav, Sep 10 '21 at 16:15
@MarekR there is a reason it was a comment and not an answer — Mgetz, Sep 10 '21 at 16:46

Bob__ · Accepted Answer · 2021-09-10T16:38:16.060

4

You can start adding memoization, to avoid most of the recursive calls.

long long ways(long long n)
{
    // Memoization requires to store the previously calculated values.
    static std::map<long long, long long> mem{
        {1, 1}, {2, 2}, {3, 4}
    };

    // I'm using std::map, but I don't want to use operator[], nor find...
    // https://en.cppreference.com/w/cpp/container/map/operator_at
    // https://en.cppreference.com/w/cpp/container/map/find
    // https://en.cppreference.com/w/cpp/container/map/lower_bound
    auto it = mem.lower_bound(n);

    // If it has already been calculated, return the stored value.
    if ( it != mem.cend() and it->first == n )
        return it->second;

    // Otherwise evaluate the new value (recursively) and store it
    // Note that I can use the iterator as an hint for the insertion.
    // https://en.cppreference.com/w/cpp/container/map/emplace_hint
    return mem.emplace_hint(
        it, n,
        (ways(n-3) + ways(n-2) + ways(n-1)) % 10000000007
    )->second;
}

If it's not enough, you'll have to search for some mathematical trick or just avoid the recursion altogether and use a simple loop.

edited Sep 10 '21 at 16:38

answered Sep 10 '21 at 16:23

Bob__

12,361
3
28
42

That works !!! Thanks! can you please explain the logic of your code in short ? – Yash Yadav Sep 10 '21 at 16:28
1

@YashYadav Edited, I hope it's more clear now. – Bob__ Sep 10 '21 at 16:38
2

Using a `std::vector` should much more efficient. This is possible since values are always positive and all values between 0 and n will be memoized. – Jérôme Richard Sep 10 '21 at 16:41
1

@JérômeRichard Well, we don't know how this would be called. As I mentioned, a loop from 1 to n would be much easier and faster and wouldn't require any extra memory other than the last three values. – Bob__ Sep 10 '21 at 16:46
@Bob__ Yeah could not use loop as for where its needed . – Yash Yadav Sep 10 '21 at 16:53

Jérôme Richard · Answer 2 · 2021-09-10T19:38:31.353

The algorithm compute a custom Tribonacci sequence modulus 10000000007. This can be computed very efficiently in O(log n) time and O(1) space based on a matrix representation of the sequence like for Fibonacci. See this post and this answer for more information.

This method is very fast for big inputs (much faster than using memoization) and very memory efficient.

However, there is a catch: the implementation needs to computation the multiplication of two 64-bit integers modulo a 64-bit integer (unless the modulus can fit in a 32-bit integer). 128-bit integers are not supported on most platforms, but boost::multiprecision can be used. See this post for more information.

Here is an implementation:

int64_t int128_mulMod(int64_t a, int64_t b, int64_t mod)
{
    return int64_t((int128_t(a) * int128_t(b)) % int128_t(mod));
}

// Compute the matrix multiplication of a * b and put the result in a
void matMulMod(int64_t a[3][3], int64_t b[3][3], int64_t mod)
{
    int64_t res[3][3] = {};

    for(int i=0 ; i<3 ; ++i)
        for(int j=0 ; j<3 ; ++j)
            for(int k=0 ; k<3 ; ++k)
                res[i][j] += int128_mulMod(a[i][k], b[k][j], mod);

    for(int i=0 ; i<3 ; ++i)
        for(int j=0 ; j<3 ; ++j)
            a[i][j] = res[i][j];
}

// Compute the matrix exponentiation a^n and put the result in a
void matPowMod(int64_t a[3][3], int64_t n, int64_t mod)
{
    if(n == 0 || n == 1)
        return;

    int64_t m[3][3] = {{ 1, 1, 1 },
                       { 1, 0, 0 },
                       { 0, 1, 0 }};

    // Use recursion to square the matrix efficiently
    matPowMod(a, n / 2, mod);

    // Square the matrix
    matMulMod(a, a, mod);

    // Remainder case
    if(n % 2)
        matMulMod(a, m, mod);

    // Apply the modulus on each term to prevent overflows
    for(int i=0 ; i<3 ; ++i)
        for(int j=0 ; j<3 ; ++j)
            a[i][j] %= mod;
}

int64_t ways_fast(int64_t n)
{
    int64_t a[3][3] = {{ 1, 1, 1 },
                       { 1, 0, 0 },
                       { 0, 1, 0 }};

    if(n==1) return 1;
    if(n==2) return 2;
    if(n==3) return 4;

    matPowMod(a, n, 10000000007ll);
    return a[0][0]; // Result of the Tribonacci sequence
}

For example, on my machine, ways_fast(30'000) is 100 times faster than computing the memoization-based method provided by @Bob__. Moreover, the memoization algorithm crashes when computing ways(60'000) while ways_fast(200'000) works correctly.

For more information, please read:

Thanks man . I needed kind of different kind of solution for as to where I have to write it. But this is really cool. Just multiply by the matrix Saving both time and space . — Yash Yadav, Sep 10 '21 at 21:08

Reducing the time complexity of recursive Fibonacci like function in c++

2 Answers2

Linked