-1

There is a problem which is "Last Digit of the Sum of Fibonacci Numbers". I have already optimised the naive approach but this code is not working for higher values. Example: 613455

Everytime I run this program, the os crashes (memory limit exceeds).

My code is:

def SumFib(n):
    result = []
    for i in range(0, n+1):
        if i <= 1:
            result.append(i)
        else:
            result.append(result[i-1] + result[i-2])
    return (sum(result) % 10)

print(SumFib(int(input())))

Need some help to get over this problem.

wjandrea
  • 28,235
  • 9
  • 60
  • 81
Pratyaksh Gupta
  • 11
  • 1
  • Profiling will not make the application consume less memory space, profiling will give you information/knowledge on where the memory is consumed. Just at a glance, one can see that just before the return you are storing the full Fibonacci series (with its 613455 elements). That will break. Do you want to know how to profile, or you just want to understand why your fibonacci code is a Bad Idea(TM)? – MariusSiuram Jul 21 '20 at 13:35
  • @MariusSiuram I am surely willing to know about the profiling. Another thing is I want to know how I can optimize this code for run on larger values. – Pratyaksh Gupta Jul 21 '20 at 13:39
  • StackOverflow try to focus on single topic questions, so focusing is important. If you want to know how to profile in Python look at other questions like [those](https://stackoverflow.com/questions/582336/how-can-you-profile-a-python-script) [ones](https://stackoverflow.com/questions/110259/which-python-memory-profiler-is-recommended). – MariusSiuram Jul 21 '20 at 13:42

2 Answers2

0

In order to consume less memory, store less values. For example:

def sum_fib(n): 
    if n == 0:
        return 0
    elif n == 1: 
        return 1 
    elif n == 2: 
        return 2 
    res_sum = 2 
    a, b = 1, 1 
    for _ in range(n-2): 
        a, b = b, a+b
        res_sum += b 
    return res_sum % 10

The memory requirements (at a glance) are constant. Your original snippet has lineal memory requirements (when n grows, the memory requirements grow).

(More intelligent things can be done regarding the modulo operation if n is really huge, but that is off topic to the original question)

Edit:

I was curious and ended up doing some homework.

Lemma 1: The last digit of the fibonacci follows a 60-length cycle.

Demonstration: One can check that, starting by (0,1), element 60 has last digit 0 and element 61 has last digit 1 (this can be checked empirically). From this follows that fib(n) equals fib(n % 60).

Lemma 2: The last digit of the sum of the first 60 digits is 0.

Demonstration: Can be checked empirically too.

Conclusion: sum_fib(n) == sum_fib(n % 60). So the algorithm to solve "last digit of the sum of the n-th first fibonacci numbers can be solved in O(1) by taking n % 60 and evaluating sum_fib of that number, i.e., sum_fib(n % 60). Or one can precreate the digit list of 60 elements and do a simple-lookup.

MariusSiuram
  • 3,380
  • 1
  • 21
  • 40
  • I have earlier approached this kind of algorithm too but time limit get exceeds through this approach . My main purpose is to execute this program in specific time limit and in specific memory limit. – Pratyaksh Gupta Jul 21 '20 at 14:07
  • @PratyakshGupta the problem you are proposing can be solved by a O(1) algorithm (constant both in memory requirements and computation time, regardless of its input). But that answer is for the Math SE, it seems off topic here at SO (and it feels like doing your homework!). Feel free to ask the question there for more mathematical background or google it in order to find the solution to your problem. – MariusSiuram Aug 04 '20 at 07:52
  • I have searched almost everything in order to find its solution both in terms of optimized space and time complexity but not found anything useful that could satisfy the higher constraint values. It will be very helpful for me if you provide any link even for the Math SE. – Pratyaksh Gupta Aug 05 '20 at 10:55
  • https://www.geeksforgeeks.org/program-find-last-digit-nth-fibonnaci-number/ – MariusSiuram Aug 05 '20 at 15:39
  • Yes, I know that you want the last digit of the sum, not the last digit of the nth fibonacci number, but it is trivial to build from there to there. – MariusSiuram Aug 05 '20 at 15:42
-1

Instead of using range you can try a custom function that works as generator.

Generators calculate values on the fly instead of loading all at once like iterators.

Replace the below function with range

def generate_value(start, end, step):
    count =start
    while True:
        if count <=end:
            yield count
            count+=step
        break
Anmol Batra
  • 159
  • 1
  • 8
  • You are thinking in Python 2, where range was allocating everything. This is not the case (the tag is Python 3, look how range behaves in Python 3). This answer is confusing, as you don't address the elefant in the room: the `result` list. – MariusSiuram Jul 21 '20 at 13:44
  • And even in Python 2, it would be better to recommend `xrange`, which is a built-in with the same idea you are proposing, no need to reinvent the wheel ;) – MariusSiuram Jul 21 '20 at 13:51
  • @MariusSiuram do you have some suggestions in order to improve this code? It will be apreciated. Thanks. – Pratyaksh Gupta Jul 21 '20 at 13:52
  • Iterators return the value that are stored in memory (in short it just fetches it) .So the object on which the iterator is iterating will be present in memory, hence memory consumption will be more with iterators, And range return iterator. – Anmol Batra Jul 21 '20 at 14:03
  • `range return iterator`: mmm not relevant for Python 3. If you are curious, check documentation. But `range` does not return a list and thus it won't hold that in memory. It has a dynamic behaviour that resembles what you were proposing --which, I insist, already existed in Python2 as `xrange`. – MariusSiuram Jul 29 '20 at 06:44