on a very slow function
Ben Bacarisse
ben.usenet at bsb.me.uk
Sun Oct 1 21:00:49 EDT 2017
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.
More information about the Python-list
mailing list