Talk:Lucas-Lehmer test: Difference between revisions
Content added Content deleted
(→Speeding things up: new section) |
m (→Speeding things up: to keep indentation as is) |
||
Line 332: | 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'''. |
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'''. |
||
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. |
<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. |
Let's compute how much the two divisions differ. |
||
Line 385: | 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. |
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) |
[[User:Arbautjc|Arbautjc]] ([[User talk:Arbautjc|talk]]) 22:04, 15 November 2013 (UTC) |