Heathens Heathens - 29 days ago 8
Python Question

Deal with extremely large numbers with Python Programming

When we are talking about complexity of our codes most of time we consider about the number of inputs. Usually we don't much consider about under laying hardware implementation. To get a connectivity between complexity of code and number of input which we compose to our algorithm(Code) we use Big_O notation commonly . loop are essential thing to implement algorithm but it has O(n) complexity which means time will grow linearly with number of input so large number of inputs it inefficient. but we can replace loop by recursion cause recursion always has O(log n) time complexity .And i am not going to clarify it on here . From all of these above But i want to say recursion is more efficient than loop

and also any thing which can do loop we can do that same thing by recursion more efficiently.

so i found a Question from Project Euler.net call self powers

follow is my Question

The series, 11 + 22 + 33 + ... + 1010 = 10405071317.
Find the last ten digits of the series, 11 + 22 + 33 + ... + 10001000.


this Question seems easy so i implement my code from Python and its work smoothly for small number of number ranges but getting power of 1000 to 1000 and sum of all above python usually show a error (cause that numbers are extremely larger which enough to occur in memory flow in python) so how do i get the answer. follow is my code

def f(n):
if n==1:
return 1
else:
return n**n+f(n-1)


So my Question is How do i solve this problem,and how to i deal with those extremely large number , how do i manage those exception which will occur on large number of integers please mention good motivative algorithm?

Answer

There's nothing that makes recursion inherently more efficient. Moreover, the same algorithm implemented with recursion is likely to be less efficient due to function call overhead. Worse than that, and this is exactly your case, using recursions of large depth is likely to cause stack overflow (no pun intended). Unless tail-recursion optimization is in use, which is not in Python.

Python does not have any limits (within reasonable ranges) of integer number size, and this is not the problem. Re-implement the function using a loop, and you'll do fine. Except that n ** n does not do what you seem to think it does.