Anonymous user
Talk:Lucas-Lehmer test: Difference between revisions
m
→Speeding things up: to keep indentation as is
(→Speeding things up: new section) |
m (→Speeding things up: to keep indentation as is) |
||
Line 332:
The main loop in Lucas-Lehmer is doing (n*n) mod M where M=2^p-1, and p > 1. '''But we can do it without division'''.
<lang>We compute the remainder of a division by M. Now, intuitively, dividing by 2^p-1 is almost like dividing by 2^p, except the latter is much faster since it's a shift.
Let's compute how much the two divisions differ.
Line 385:
How much faster ? For exponents between 1 and 2000, in Python, the job is done 2.87 times as fast. For exponents between 1 and 5000, it's 3.42 times as fast. And it gets better and better, since the comlexity is lower.
</lang>
[[User:Arbautjc|Arbautjc]] ([[User talk:Arbautjc|talk]]) 22:04, 15 November 2013 (UTC)
| |||