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.
--
https://mail.python.org/mailman/listinfo/python-list
