[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Chris Angelico <rosuav at gmail.com> writes: > On Mon, Oct 2, 2017 at 8:27 AM, Daniel Bastos <dbastos at toledo.com> 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 >> >> It crawls pretty soon. Please advise? Thank you. > > For a start, it should probably be implemented as a generator. Maybe something like this? def make_generator(N, last = 2, c = -1): while True: yield last last = (last**2 + c) % N I wish I had an argument that would give me the ith element of this sequence. Like this: def make_sequence(N, x0 = 2, c = -1): def sequence(i): if i == 0: return x0 return (sequence(i - 1)**2 + c) % N return sequence With this function, I can do: f = make_sequence(1032) [f(0), f(1), f(32), f(59)] But I can't ask for high values because eventually I hit the recursion limit. So I'd like a function that's (1) non recursive and hopefully (2) would somehow save what it has computed (during its life time) to avoid recomputing. So if called in series such as in f(0), f(1), ..., f(i), f(i + 1), ... It's then quick because to compute f(i), it needs f(0), f(1), ..., f(i - 1), which it has already computed and remembers it. I think I can look up efficient implementations of the Fibonacci sequence. IIRC, Paul Graham's ANSI Common Lisp shows how to do it for Fibonacci. Maybe it'll help me. I'll look it up. > I'm not sure what this is even trying to do. That function produces a function which yields the values of the sequence x^2 - 1 mod N One value per call. So f = make_sequence_non_recursive(55) [f() for i in range(3) ] == [2, 3, 8] >From this point on, f() produces 8 forever. These sequences are studied in pseudo-random number generation. See for example ``The Art of Computer Programming'', D.E. Knuth, volume 2, seminumerical algorithms, chapter 3, section 3.2.1, ``The Linear Congruential Method''. In such contexts, the choice of variable names is /usually/ clear. I apologize if not introducing the context made it hard to understand. It didn't occur to me until you mentioned. Thank you!

- Prev by Date:
**newb question about @property** - Next by Date:
**newb question about @property** - Previous by thread:
**on a very slow function** - Next by thread:
**on a very slow function** - Index(es):