[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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.

- Prev by Date:
**on a very slow function** - Next by Date:
**on a very slow function** - Previous by thread:
**on a very slow function** - Next by thread:
**on a very slow function** - Index(es):