on a very slow function

[Ben Bacarisse]

Steve D'Aprano <steve+python at pearwood.info> 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 necessary.
<snip maths>

I meant for the program.  It makes no difference to the result if last is
left entirely un-reduced (that was the original problem) so there is no
need (as far as the program is concerned) to ensure that last is fully
reduced.

Another naive timing tests suggests that 

  last = (pow(last, 2, N) + (c % N)) % N

is measurably slower than

  last = (pow(last, 2, N) + c) % N

and

  last = pow(last, 2, N) + c

is a little faster still.  None of these allow last to grow
uncontrollably.  Obviously we need to know more about the
potential range of N and c to do any realistic measurements. 

>>> will almost certainly be faster for large values of last.
>> 
>> Do you mean for large values of N?  If the calculations are mod N, it
>> seems like N will the number that matters.
>
> No, I meant "last". Although on testing, I think you might need so really big
> values before you'll see a difference. Like hundreds of digits or
> more.

Ah, again I meant for the program.  Any large value of last will exist
for one call only.  Obviously there will be /some/ point at which a
single call to the the three arg version of pow is better than ** and %,
but for that to sustained (in the program), N must be huge too.

Another simple test suggests that last * last is faster than last**2 so
the best so far (for the N and c originally posted) is the simpler:

    last = (last * last + c) % N

Again I mean in the program as posted, not as a line on its own with
arbitrary values of 'last'.

-- 
Ben.