on a very slow function

[Ben Bacarisse]

Steve D'Aprano <steve+python at pearwood.info> writes:

> On Mon, 2 Oct 2017 09:49 am, Ben Bacarisse wrote:
>
>> Daniel Bastos <dbastos at toledo.com> writes:
>> 
>>> 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
>>>
>>> It crawls pretty soon.  Please advise?
>> 
>> A mathematical rather than Python answer... 
>
> Which is the best sort of answer. When possible, simplifying your algorithm is
> better than speeding up your code.
>
>> change it to 
>> 
>>       last = (last**2 + c) % N
>>       return next
>
> Better:
>
> last = (pow(last, 2, N) + (2 % N)) % N

You meant c rather than 2, I think.  And I'm not convinced all the %Ns
are worth while.  Will typical implementations spot that c does not
change and calculate c % N only once?  Also, a very naive test (I don't
know much about how to profile Python) suggests that my line is faster
for the specific N being used in the OP's example.

> will almost certainly be faster for large values of last.

Do you mean for large values of N?  If the calculations are mod N, it
seems like N will the number that matters.

-- 
Ben.