Fast Perrin Test 


My latest posts can be found here: Previous blog posts:
Additionally, some earlier writings: 
Fast Perrin Test  2015/05/19For context you probably want to read these first: So we've got scaffolding to look for Perrin PseudoPrimes (PPPs), assuming any exist (which they do) but as we run the existing code we find that it's spending pretty much all its time in the test as to whether n divides k(n).
We have to make that faster.
As soon as we ask that question we think of matrices, because matrices represent transformations from vectors to vectors, so we want a matrix $T$ such that $K_1=T.K_0.$ Such a matrix is easy to construct. Here: $$ \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \\ \end{bmatrix} \begin{bmatrix} k_0 \\ k_1 \\ k_2 \\ \end{bmatrix} = \begin{bmatrix} k_1 \\ k_2 \\ k_0+k_1 \\ \end{bmatrix} = \begin{bmatrix} k_1 \\ k_2 \\ k_3 \\ \end{bmatrix} $$ Applying $T$ lots of times steps us through the vectors, so we get: $$ K_n = T^nK_0 $$
Then we can use Russian Peasant Multiplication to compute that quickly and efficiently. The code shown here does that for us. There are as yet a few microoptimisations we can make, but we'll leave that until after we've done the main algorithmic improvements, because time taken now could be wasted as the code changes. For similar reasons I'm not using any libraries such as sage, numpy, or scipy to do the sums. At this stage it's worth keeping it all "on the surface" and visible. So what about running this? Remember, it was taking about 60 seconds to get to $10^5$. How long does this version take?
Well that's not bad. (!) We have been running the code for 100 seconds to see how far it gets. Previously it got to about n=109159. What about now?
Yup, we get about 60 times as far. But what's more, we've got our first Perrin PseudoPrime. And in fact we've got two!
Interestingly, in both cases they are predicted to be prime by the Perrin test whereas they are in fact composite:
Next, we see if we can take advantage of the mathematical observation about the failures, and whether we can further reuse calculations we've already done.
CommentsI've decided no longer to include comments directly via the Disqus (or any other) system. Instead, I'd be more than delighted to get emails from people who wish to make comments or engage in discussion. Comments will then be integrated into the page as and when they are appropriate. If the number of emails/comments gets too large to handle then I might return to a semiautomated system. That's looking increasingly unlikely.

Quotation from Tim BernersLee 