on a very slow function

[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 value.
3
py> ((2**75) % 12 + (7 % 12)) % 12  # Correct.
3
py> (2**75) % 12 + (7 % 12)  # Incorrect.
15


This follows from the rules of modulo arithmetic:

if a ≡ x (mod N)
and b ≡ y (mod N)

then a + b ≡ x + y (mod N)




> Will typical implementations spot that c does not 
> change and calculate c % N only once?

No.


> Also, a very naive test (I don't 
> know much about how to profile Python) suggests that my line is faster
> for the specific N being used in the OP's example.
> 
>> 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.

I just tried it with:

    last = 123456789012345**85

which has over 1000 digits, comparing:

    (last**2 + 17) % 95

versus:

    (pow(last, 2, 95) + (17 % 95)) % 95


and the second form is about ten times faster.

But for smaller values of last, I agree, the first form will be faster.



-- 
Steve
“Cheer up,” they said, “things could be worse.” So I cheered up, and sure
enough, things got worse.