on a very slow function

[Peter Otten]

Daniel Bastos 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.

Let's change your code a bit to get a feel for the size of the numbers you 
are dealing with:

>>> 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
...   def get_last(): return last
...   return sequence, get_last
... 
>>> f, get_last = make_sequence_non_recursive(1032)
>>> for i in range(100): print(i, f())
... 
0 2
1 3
2 8
3 63
4 872
5 831
6 152
7 399
8 272
9 711
10 872
11 831
12 152
13 399
14 272
15 711
16 872
17 831
18 152
19 399
20 272
21 711
22 872
23 831
^CTraceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 7, in sequence
KeyboardInterrupt
>>> x = get_last()

I'd rather not show the actual number, but

>>> x.bit_length()
12534884

So at this point it alreay would take 1.5 MB to store the number in binary. 
The actual format requires even a bit more memory:

>>> import sys
>>> sys.getsizeof(x)
1671344

So for every operation you have to touch a lot of memory -- and that takes 
time. 

Now let's apply Ben's modification:

>>> f, get_last = make_sequence_non_recursive(1032)
>>> for i in range(24): f()
... 
2
8
872
152
272
872
152
272
872
152
272
872
152
272
872
152
272
872
152
272
872
152
272
872
>>> get_last().bit_length()
8

OK. I dare to have that one printed:

>>> get_last()
152

I did not time it, but in general less memory touched will translate into 
faster execution. Expect a huge speed-up...