3 ms·
The obvious and naive method described above is O(sqrt(N)). For N ~= 2 ^ 127, that is about 2 ^ 64. / The Lucas-Lehmer method described in the article is better
by xpe 11mo ago
The obvious and naive method described above is O(sqrt(N)). For N ~= 2 ^ 127, that is about 2 ^ 64. / The Lucas-Lehmer method described in the article is better (how much better is an exercise for the reader).
- gsliepen 11mo agoYou are assuming division itself is an O(1) operation. However, it also scales with the size of the number. So more correct would be to say that this naive method is O(sqrt(N) log(N) log(log(N))).
- xpe 11mo agoI was both hoping and fearing that someone would correct my simplification. (That is more nested logs than I would’ve guessed however.)