bartc wrote: > On 02/10/2017 08:41, Peter Otten wrote: >> Daniel Bastos wrote: >> >>> def make_sequence_non_recursive(N, x0 = 2, c = -1): >>> "What's wrong with this function? It's very slow." >>> last = x0 >>> def sequence(): >>> nonlocal last >>> next = last >>> last = last**2 + c >>> return next % N >>> return sequence > >>>>> x.bit_length() >> 12534884 >> >> So at this point it alreay would take 1.5 MB to store the number in >> binary. The actual format requires even a bit more memory: >> >>>>> import sys >>>>> sys.getsizeof(x) >> 1671344 >> >> So for every operation you have to touch a lot of memory -- and that >> takes time. > > If it recalculates 'last' once for each of those couple of dozen printed > lines, that I doubt accessing a few MB of memory is the issue. More > doing such a big calculation.
You are probably right that the calculation requires a significant amount of the total time here, but it's not just "a few MB". If you look at >>> last = last**2 + c the required memory doubles on every iteration. You will soon run into the problem even under the (overly optimistic) assumption that the calculation requires time proportional to memory. -- https://mail.python.org/mailman/listinfo/python-list
