on a very slow function

[Peter Otten]

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.