3

How to find the n-th term in a sequence with following recurrence relation for a given n?

F(n) = 2 * b * F(n – 1) – F(n – 2), F(0) = a, F(1) = b

where a and b are constants.

The value of N is quite large (1 ≤ n ≤ 1012) and so matrix exponentiation is required.

Here is my code for it; ll is a typedef for long long int, and value is to be taken modulo r.

void multiply(ll F[2][2], ll M[2][2])
{
    ll x = ((F[0][0] * M[0][0]) % r + (F[0][1] * M[1][0]) % r) % r;
    ll y = ((F[0][0] * M[0][1]) % r + (F[0][1] * M[1][1]) % r) % r;
    ll z = ((F[1][0] * M[0][0]) % r + (F[1][1] * M[1][0]) % r) % r;
    ll w = ((F[1][0] * M[0][1]) % r + (F[1][1] * M[1][1]) % r) % r;
    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}
void power(ll F[2][2], ll n, ll b)
{
    if (n == 0 || n == 1)
        return;
    ll M[2][2] = {{2 * b, -1}, {1, 0}};
    power(F, n / 2,b);
    multiply(F, F);
    if (n % 2 != 0)
        multiply(F, M);
}
ll rec(ll n, ll b, ll a)
{
    ll F[2][2] = {{2 * b, -1}, {1, 0}};
    if (n == 0)
        return a;
    if (n == 1)
        return b;
    power(F, n - 1,b);
    return F[0][0] % r;
}

However I am facing problems getting required value in all cases, that is I am getting Wrong Answer (WA) verdict for some cases.

Could anyone help me with this question and point out the mistake in this code so I can tackle these kind of problems myself afterward?

P.S. First timer here. Apologies if I did something incorrectly and missed out on anything.

Gassa
  • 8,546
  • 3
  • 29
  • 49
hajas
  • 113
  • 1
  • 6
  • Could you tell us one of the "some cases" that gets you a "Wrong Answer"? Without that your question is not complete, though it is good otherwise as far as I can see. – Rory Daulton Feb 10 '18 at 16:25
  • I'm not sure why you say matrix exponentiation is required. This recurrence could be solved by the same techniques used for the Fibonacci recurrence. – JWWalker Feb 10 '18 at 16:32
  • Am I missing something in saying that I don't get why a matrix multiplication is required here when you have a one dimensional recurrence? – SomeDude Feb 10 '18 at 16:33
  • 1
    @RoryDaulton the test cases are not available until question is solved , otherwise i would have debugged it myself . – hajas Feb 10 '18 at 16:44
  • 1
    @JWWalker by saying matrix exponentiation is required i meant that O(log N) complexity is desirable . I have calculated fibonacci numbers using this algorithm before so naturally i thought of this . If you have a more suitable technique or algorithm please do share . Appreciate it – hajas Feb 10 '18 at 16:47
  • @svasa I hope your query is also answered by the comment before this . – hajas Feb 10 '18 at 16:48
  • @JWWalker Matrix exponentiation *is* one of the techniques used for Fibonacci recurrence, and one of the best. You can get O(n) performance with caching or forward induction, but you can get O(log n) with matrix multiplication. That makes a difference on problems as big as 10**12. – pjs Feb 10 '18 at 16:49
  • The formula also looks wrong, I've updated my answer with an explanation. – Gassa Feb 10 '18 at 17:11

2 Answers2

2
  1. Technical: Perhaps you are asked to find the value res modulo r so that 0 <= res < r. However, by using -1 in the matrix, you can actually get negative intermediate and final values. The reason is that, in most programming languages, the modulo operation actually uses division rounded towards zero, and so produces a result in the range -r < res < r (example link).

Try either of the following:

  • Change that -1 to r - 1, so that all intermediate values remain non-negative.

  • Fix the final result by returning (F[0][0] + r) % r instead of just F[0][0] % r.

  1. Formula: Your formula looks wrong. Logically, your rec function says that nothing except F(0) depends on a, which is obviously wrong.

Recall why and how we use the matrix in the first place:

( F(n)   )  =  ( 2b   -1 )   *  ( F(n-1) )
( F(n-1) )     (  1    0 )      ( F(n-2) )

Here, we get a 2x1 vector by multiplying a 2x2 matrix and a 2x1 vector. We then look at its top element and have, by multiplication rules,

F(n) = 2b * F(n-1) + (-1) * F(n-2)

The point is, we can take the power of the matrix to get the following:

( F(n)   )  =  ( 2b   -1 ) ^{n-1}   *  ( F(1) )
( F(n-1) )     (  1    0 )             ( F(0) )

By the same argument, we have

F(n) = X * F(1) + Y * F(0)

where X and Y are the top row of the matrix:

( 2b   -1 ) ^{n-1}  =  ( X   Y )
(  1    0 )            ( Z   T )

So F[0][0] % r is not the answer, really. The real answer looks like

(F[0][0] * b + F[0][1] * a) % r

If we can have negative intermediate values (see point 1 above), the result is still from -r to r instead of from 0 to r. To fix it, we can add one more r and take the modulo once again:

((F[0][0] * b + F[0][1] * a) % r + r) % r
Gassa
  • 8,546
  • 3
  • 29
  • 49
  • I was already applying the second tip . I tried the first one but it still gives some right and some wrong . Nice idea though . – hajas Feb 10 '18 at 17:12
  • This answer is essentially correct, but still leaves room for messing up negative numbers. I suggest to reduce *everything* except N mod `r` first, including `a`, `b`, and `-1`, so that all the numbers in the problem are positive and less than `r` from the outset. Again, take care to deal with negatives properly in these initial reductions. – Matt Timmermans Feb 10 '18 at 19:53
  • 1
    Finally made it work . I got confused between your formula and the relation and applied it as F[0][0] * b - F[0][1] * a . I just noticed it now . I got it to work as F[0][0] * b - F[1][0] * a ( another expression for the result ) . – hajas Feb 12 '18 at 10:39
0

Possible reason for WA is, you return a or b without doing any mod. Try it.

if (n == 0)
    return a%r;
if (n == 1)
    return b%r;

If you are still getting WA, please give some test cases or problem link.

Md. Mostafizur Rahman
  • 461
  • 1
  • 6
  • 16
  • Not at all . This is the final step of the problem and a and b have to be calculated beforehand . I have applied modulus there . – hajas Feb 10 '18 at 16:43
  • @jahas If you wait to the end for the modulus you'll have already overflowed a `long long int` for many cases. – pjs Feb 10 '18 at 16:45
  • @pjs I am applying it when initializing it . Also it is failing with values around 10 so that would not be the case . – hajas Feb 10 '18 at 17:06