on a very slow function

[bartc]

On 02/10/2017 14:54, Peter Otten wrote:
> 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.

On my machine, the iterations whizzed up the screen until I noticed it 
pausing on the 21st iteration, when the memory size of last was 0.5MB.

When I started last as "A", and multiplied by 2 at each step, it started 
to pause at the 27th iteration when the size of last was 268MB.

I would estimate then another 9 steps of the original (30th iteration) 
before memory usage has the same effect. Although it would probably 
already have ground to a halt long before then.

-- 
bartc