Re: on a very slow function

2017-10-03 Thread Steve D'Aprano
On Tue, 3 Oct 2017 04:23 am, Ian Kelly wrote: >> py> (2**75 + 7) % 12 # Expected value. >> 3 >> py> ((2**75) % 12 + (7 % 12)) % 12 # Correct. >> 3 >> py> (2**75) % 12 + (7 % 12) # Incorrect. >> 15 > > No, only the final one is necessary. Modding the result of the > exponentiation might be usef

Re: on a very slow function

2017-10-02 Thread Daniel Bastos
Ben Bacarisse writes: > Daniel Bastos writes: > >> 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

Re: on a very slow function

2017-10-02 Thread Daniel Bastos
Chris Angelico writes: [...] > Maybe "linear_congruential" would be a good name for the function? I > don't know. Sounds good to me --- in absence of a smaller name. > Anyhow, the basic memoization technique should help you some. It did! Thanks so much to you and to everyone who contributed

Re: on a very slow function

2017-10-02 Thread Daniel Bastos
r...@zedat.fu-berlin.de (Stefan Ram) writes: > Daniel Bastos writes: >> That function produces a function which yields the values of the >> sequence x^2 - 1 mod N > > Thats a term with two free variables. > I am not sure what the sequence is. > > And if that's > > ( x^2 - 1 )mod N That's c

Re: on a very slow function

2017-10-02 Thread Ian Kelly
On Sun, Oct 1, 2017 at 8:14 PM, Steve D'Aprano wrote: > > On Mon, 2 Oct 2017 12:00 pm, Ben Bacarisse wrote: > > > >> Better: > >> > >> last = (pow(last, 2, N) + (2 % N)) % N > > > > You meant c rather than 2, I think. > > Oops, yes, that was a typo. > > > > And I'm not convinced all the %Ns > > ar

Re: on a very slow function

2017-10-02 Thread bartc
On 02/10/2017 14:54, Peter Otten wrote: bartc wrote: On 02/10/2017 08:41, Peter Otten wrote: 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 = las

Re: on a very slow function

2017-10-02 Thread Peter Otten
bartc wrote: > On 02/10/2017 08:41, Peter Otten wrote: >> 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 =

Re: on a very slow function

2017-10-02 Thread Chris Angelico
On Mon, Oct 2, 2017 at 10:24 PM, bartc wrote: > On 02/10/2017 08:41, Peter Otten wrote: >> >> 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 >>

Re: on a very slow function

2017-10-02 Thread bartc
On 02/10/2017 08:41, Peter Otten wrote: 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 sequ

Re: on a very slow function

2017-10-02 Thread Ben Bacarisse
Steve D'Aprano writes: > On Mon, 2 Oct 2017 12:00 pm, Ben Bacarisse wrote: > > >>> Better: >>> >>> last = (pow(last, 2, N) + (2 % N)) % N >> >> You meant c rather than 2, I think. > > Oops, yes, that was a typo. > > >> And I'm not convinced all the %Ns >> are worth while. > > They are all neces

Re: on a very slow function

2017-10-02 Thread Steve D'Aprano
On Mon, 2 Oct 2017 06:41 pm, Peter Otten wrote: x = get_last() > > I'd rather not show the actual number, but > x.bit_length() > 12534884 Which is approximately 3773408 decimal digits. Using the American system of large numbers, that's approximately a duotrigintillion-duotrigintilli

Re: on a very slow function

2017-10-02 Thread 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.

Re: on a very slow function

2017-10-01 Thread Christian Gollwitzer
Am 01.10.17 um 23:27 schrieb Daniel Bastos: 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 pre

Re: on a very slow function

2017-10-01 Thread Steve D'Aprano
On Mon, 2 Oct 2017 12:00 pm, Ben Bacarisse wrote: >> Better: >> >> last = (pow(last, 2, N) + (2 % N)) % N > > You meant c rather than 2, I think. Oops, yes, that was a typo. > And I'm not convinced all the %Ns > are worth while. They are all necessary. py> (2**75 + 7) % 12 # Expected val

Re: on a very slow function

2017-10-01 Thread Ben Bacarisse
Steve D'Aprano writes: > On Mon, 2 Oct 2017 09:49 am, Ben Bacarisse wrote: > >> Daniel Bastos writes: >> >>> 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 = l

Re: on a very slow function

2017-10-01 Thread Chris Angelico
On Mon, Oct 2, 2017 at 11:34 AM, Steve D'Aprano wrote: >> change it to >> >> last = (last**2 + c) % N >> return next > > Better: > > last = (pow(last, 2, N) + (2 % N)) % N > > will almost certainly be faster for large values of last. I think possibly you mean (c % N) in the middle the

Re: on a very slow function

2017-10-01 Thread Steve D'Aprano
On Mon, 2 Oct 2017 09:49 am, Ben Bacarisse wrote: > Daniel Bastos writes: > >> 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 >>

Re: on a very slow function

2017-10-01 Thread Chris Angelico
On Mon, Oct 2, 2017 at 9:22 AM, Daniel Bastos wrote: > Chris Angelico 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

Re: on a very slow function

2017-10-01 Thread Ben Bacarisse
Daniel Bastos writes: > 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.

Re: on a very slow function

2017-10-01 Thread Daniel Bastos
Chris Angelico writes: > On Mon, Oct 2, 2017 at 8:27 AM, 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 >>

Re: on a very slow function

2017-10-01 Thread Chris Angelico
On Mon, Oct 2, 2017 at 8:27 AM, 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 seque

on a very slow function

2017-10-01 Thread Daniel Bastos
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. >>> f = make_se