CODEWITHSUNDEEP
c++fibonacciperiodstack-dump
Soham Parate
Soham Parate

Reputation: 75

Need help in writing a function for Pisano Period in C++

int PisanoLength(int m){
    std::vector<int> v;
    v.push_back(0);
    v.push_back(1);

    int i;

    for(i = 2; ; i++){
        v[i] = v[i - 1] + v[i - 2];
        int a = v[i - 1] % m;
        int b = v[i] % m;
        if( a == 0 && b == 1)
            break;
    }

    return (i - 2);
}

Hello, I am new to C++ and I have been trying to write a function to calculate the length of the Pisano Period. I have used the fact that once you hit 0 and 1 again, the sequence starts repeating itself so the index number before that 0 is the Pisano period length. But this one (the one which I wrote above) shows 'Dumping stack trace to pisano2.exe.stackdump' error (pisano2.cpp is the file name)

Upvotes: 0

Views: 78

Answers (2)

Bob__
Bob__

Reputation: 12779

There are a couple of errors.

One, as already noted, is the access out of bounds of the vector v inside the loop.

The other, sneakier, is that the module is applied after the elements are inserted, while applying it before storing the values avoids integer overflows.

#include <vector>
#include <cassert>

int PisanoLength(int m)
{
    if ( m <= 1 )
        return 1;

    std::vector<int> v{0, 1};

    for( int i = 2; ; ++i )
    {
        v.push_back((v[i - 1] + v[i - 2]) % m);
     //   ^^^^^^^^^                       ^^^

        if( v[i - 1] == 0  &&  v[i] == 1 )
            break;
    }

    return v.size() - 2;
}

int main()
{
    // See e.g. https://en.wikipedia.org/wiki/Pisano_period
    assert(PisanoLength(1) == 1);
    assert(PisanoLength(2) == 3);
    assert(PisanoLength(3) == 8);
    assert(PisanoLength(5) == 20);
    assert(PisanoLength(6) == 24);
    assert(PisanoLength(10) == 60);
    assert(PisanoLength(12) == 24);
}

Demo vs Failing demo

Upvotes: 0

MikeCAT
MikeCAT

Reputation: 75062

Your vector v has only 2 elements, so it is illegal to access v[i] with i >= 2 without adding elements. You should use push_back() to add elements.

int PisanoLength(int m){
    std::vector<int> v;
    v.push_back(0);
    v.push_back(1);

    int i;

    for(i = 2; ; i++){
        v.push_back(v[i - 1] + v[i - 2]); // add elements
        int a = v[i - 1] % m;
        int b = v[i] % m;
        if( a == 0 && b == 1)
        break;
    }

    return (i - 2);
}

Upvotes: 1

Related Questions