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

Steve D'Aprano <steve+python at pearwood.info> writes: > 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. <snip maths> I meant for the program. It makes no difference to the result if last is left entirely un-reduced (that was the original problem) so there is no need (as far as the program is concerned) to ensure that last is fully reduced. Another naive timing tests suggests that last = (pow(last, 2, N) + (c % N)) % N is measurably slower than last = (pow(last, 2, N) + c) % N and last = pow(last, 2, N) + c is a little faster still. None of these allow last to grow uncontrollably. Obviously we need to know more about the potential range of N and c to do any realistic measurements. >>> 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. Ah, again I meant for the program. Any large value of last will exist for one call only. Obviously there will be /some/ point at which a single call to the the three arg version of pow is better than ** and %, but for that to sustained (in the program), N must be huge too. Another simple test suggests that last * last is faster than last**2 so the best so far (for the N and c originally posted) is the simpler: last = (last * last + c) % N Again I mean in the program as posted, not as a line on its own with arbitrary values of 'last'. -- Ben.

- Prev by Date:
**newb question about @property** - 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):