Steve D'Aprano <steve+pyt...@pearwood.info> writes: > On Mon, 2 Oct 2017 09:49 am, Ben Bacarisse wrote: > >> Daniel Bastos <dbas...@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. -- https://mail.python.org/mailman/listinfo/python-list
