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

On Mon, Oct 2, 2017 at 9:22 AM, Daniel Bastos <dbastos at toledo.com> wrote: > Chris Angelico <rosuav at gmail.com> writes: > >> 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 Yeah, that's a lot less guff, and it clearly shows that you're generating a series of values. Will you ever provide 'last' or 'c' as actual arguments? If not, they shouldn't be there in the function signature. There are all sorts of crazy shenanigans done by people who think recursion is the only way to do things, and we who use generator functions don't have to do them. One last thing: can you name the function something more useful? def flurble(n): value = 2 c = -1 while True: yield value value = (value**2 + c) % n But if you would be providing the initial value and the constant, then they do belong in the parameters, so ignore this. > 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. Sounds like what you want is "memoization". Here's the easiest way to do it: def flurble(n, start=2, c=-1): # still wants a better name than flurble cache = [start] def sequence(i): while i >= len(cache): cache.append((cache[-1]**2 + c) % n) return cache[i] return sequence > 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. Yep, exactly. In this case, since the sole argument is a counting number, a list can be used to great efficiency; in the more general case, a dictionary is more appropriate. Check out functools.lru_cache for a general memoization decorator. >> I'm not sure what this is even trying to do. > > That function produces a function which yields the values of theof > 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. Yeah, and I do know plenty of situations where you're directly transforming a mathematical equation into code, so all those one-letter names make good sense. But it would be helpful to include a link or reference in your original post :) Maybe "linear_congruential" would be a good name for the function? I don't know. Anyhow, the basic memoization technique should help you some. ChrisA

- 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):