on a very slow function

[Daniel Bastos]

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!