For loop computing recurrence relation takes very long
<pre><code>Q(x)=[Q(xâ1)+Q(xâ2)]^2
Q(0)=0, Q(1)=1
</code></pre>

<p>I need to find Q(29). I wrote a code in python but it is taking too long. How to get the output (any language would be fine)?</p>

<p>Here is the code I wrote:</p>

<pre><code>a=0
b=1
for i in range(28):
    c=(a+b)*(a+b)
    a=b
    b=c
print(b)
</code></pre>

<p>You can check if c%10==0 and then divide it, and in the end multiplyit number of times you divided it but in the end it'll be the same large number. If you really need to do this calculation try using C++ it should run it faster than Python.</p>

<hr>

<p>Here's your code written in C++</p>

<pre><code>#include &lt;cstdlib&gt;
#include &lt;iostream&gt;

using namespace std;

int main(int argc, char *argv[])
{
    long long int a=0;
    long long int b=1;
    long long int c=0;
    for(int i=0;i&lt;28;i++){
            c=(a+b)*(a+b);
            a=b;
            b=c;
    }

    cout &lt;&lt; c;
    return 0;
}
</code></pre>

python loops recurrence