Why can't I store all Fibonacci numbers up to the 1000000th in a Python list?

Question

This code gives out a fibonacci number. With larger number it produces memory error. Can i allocate more ram or resources to the compiler or is there a more efficient code that i can use?

list1 = [0, 1]
x = 0
while x < 1000000:
    list1.append(list1[-1] + list1[-2])
    x+=1
print(list1[-1])

https://cboard.cprogramming.com/c-programming/67989-highest-fibonacci-number-ever-calculated.html — Joe, Aug 08 '19 at 12:28
Not sure what you are trying to achieve, but you will need a lot of memory for it... — Joe, Aug 08 '19 at 12:28
https://stackoverflow.com/questions/14689390/nth-term-for-fibonacci-series-for-enormous-data-inputwithout-recursion-or-loop — Joe, Aug 08 '19 at 12:31
https://web2.0calc.com/questions/1-000-000th-fibonacci-number — Joe, Aug 08 '19 at 12:31

Joe · Accepted Answer · 2019-08-09T05:49:31.417

4

If you are interested in the last number, don't store the intermediate results.

I just tried it (using sys.getsizeof()) and the sum of all integer values in the list would be 46308778320 bytes. Which is 46 GByte.

Even though the 1000000th Fibobacci number only has 92592 bytes

There is no limit to how big an integer can be in Python.

This is how the size of the integers grows:

A small integer in Python has already has 28 bytes, which is quite large compared to a C int.

More info on this can be found at "sys.getsizeof(int)" returns an unreasonably large value?

How to calculate the total size?

import sys
fib = None
size_fib = 0

for _ in range(1000000):
    fib = ... # calculation here
    size_fib += sys.getsizeof(fib)

print(size_fib)

edited Aug 09 '19 at 05:49

answered Aug 08 '19 at 12:46

Joe

6,758
2
26
47

thanks, can you suggest a better way of doing this? – soap Aug 08 '19 at 15:05
1

What are you really up to? – Joe Aug 08 '19 at 15:07
i want to find a particular fibonacci number. – soap Aug 08 '19 at 15:11
how can i find the size of all the integers without appending all the integers to the list? – soap Aug 08 '19 at 15:25
I just added them up in a loop, like you did with `x`. – Joe Aug 08 '19 at 15:39
wouldn't that require the same amount of memory though? – soap Aug 08 '19 at 16:33
Nope, it's just one variable. – Joe Aug 08 '19 at 20:16

score 0 · Answer 2 · answered Aug 09 '19 at 16:03

I found the 1000000th Fibobacci number using the following code, it took a minute or so to calculate the result.

cache = {}
for x in range(1, 1000001):
    if x > 4:
        cache.pop(x-3, x-4)

    if x <= 2:
        value = 1
        cache[x] = value
    else:
        value = cache[x - 1] + cache[x - 2]
        cache[x] = value
print(value)

Why can't I store all Fibonacci numbers up to the 1000000th in a Python list?

2 Answers2