on a very slow function

[Steve D'Aprano]

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

will almost certainly be faster for large values of last.



-- 
Steve
“Cheer up,” they said, “things could be worse.” So I cheered up, and sure
enough, things got worse.