on a very slow function

[Chris Angelico]

On Mon, Oct 2, 2017 at 10:24 PM, bartc <bc at freeuk.com> 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.

Yes, but when you're working with a number with that many limbs, it's
bound to take some time. Squaring arbitrary numbers is a big job -
it's more efficient than O(n²) but still a lot worse than linear time,
so on huge numbers it's going to take hugely huge time.

*handwave furiously*

ChrisA