on a very slow function
On Mon, 2 Oct 2017 12:00 pm, Ben Bacarisse wrote:
>> 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.
py> ((2**75) % 12 + (7 % 12)) % 12 # Correct.
py> (2**75) % 12 + (7 % 12) # Incorrect.
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?
> 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
(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.
?Cheer up,? they said, ?things could be worse.? So I cheered up, and sure
enough, things got worse.