on a very slow function

[Chris Angelico]

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