# on a very slow function

```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.

```