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>This can be solved with brute force but it is still an interesting problem since it uses two different "slow" operations and there are trade-offs in choosing the correct approach.</p>

<p>There are two places where the native Python implementation of algorithm is slow: the multiplication of large numbers and the conversion of large numbers to a string. </p>

<p>Python uses the Karatsuba algorithm for multiplication. It has a running time of O(n^1.585) where n is the length of the numbers. It does get slower as the numbers get larger but you can compute Q(29). </p>

<p>The algorithm for converting a Python integer to its decimal representation is much slower. It has running time of O(n^2). For large numbers, it is much slower than multiplication.</p>

<p><strong><em>Note: the times for conversion to a string also include the actual calculation time.</em></strong></p>

<p>On my computer, computing Q(25) requires ~2.5 seconds but conversion to a string requires ~3 minutes 9 seconds. Computing Q(26) requires ~7.5 seconds but conversion to a string requires ~12 minutes 36 seconds. As the size of the number doubles, multiplication time increases by a factor of 3 and the running time of string conversion increases by a factor of 4. The running time of the conversion to string dominates. Computing Q(29) takes about 3 minutes and 20 seconds but conversion to a string will take more than 12 hours (I didn't actually wait that long).</p>

<p>One option is the <a href="https://pypi.python.org/pypi/gmpy2" rel="nofollow">gmpy2</a> module that provides access the very fast <a href="https://gmplib.org/" rel="nofollow">GMP</a> library. With <code>gmpy2</code>, Q(26) can be calculated in ~0.2 seconds and converted into a string in ~1.2 seconds. Q(29) can be calculated in ~1.7 seconds and converted into a string in ~15 seconds. Multiplication in GMP is O(n*ln(n)). Conversion to decimal is faster that Python's O(n^2) algorithm but still slower than multiplication.</p>

<p>The fastest option is Python's <code>decimal</code> module. Instead of using a radix-2, or binary, internal representation, it uses a radix-10 (actually of power of 10) internal representation. Calculations are slightly slower but conversion to a string is very fast; it is just O(n). Calculating Q(29) requires ~9.2 seconds but calculating and conversion together only requires ~9.5 seconds. The time for conversion to string is only ~0.3 seconds.</p>

<p>Here is an example program using <code>decimal</code>. It also sums the individual digits of the final value.</p>

<pre><code>import decimal

decimal.getcontext().prec = 200000000
decimal.getcontext().Emax = 200000000
decimal.getcontext().Emin = -200000000

def sum_of_digits(x):
    return sum(map(int, (t for t in str(x))))

a = decimal.Decimal(0)
b = decimal.Decimal(1)
for i in range(28):
    c = (a + b) * (a + b)
    a = b
    b = c


temp = str(b)
print(i, len(temp), sum_of_digits(temp))
</code></pre>

<p>I didn't include the time for converting the millions of digits into strings and adding them in the discussion above. That time should be the same for each version.</p>

python loops recurrence