Finding Perrin Pseudo Primes_Part 2 


My latest posts can be found here: Previous blog posts:
Additionally, some earlier writings: 
Finding Perrin Pseudoprimes:

#!/usr/bin/python n = 2 t = 10 t_prime = 0.0 t_perrin = 0.0 while clock() < int(argv[1]): t_prime = clock() is_prime = is_prime_q(n) t_prime += clock() t_perrin = clock() is_perrin = is_perrin_q(n) t_perrin += clock() if is_prime != is_perrin: print n, is_prime, is_perrin if t < clock(): print 'Tested to %d in %d secs' % (n,t) t += 10 n += 1 print 'Time in prime :', t_prime print 'Time in Perrin:', t_perrin # ================ # Edited output: # # Tested to 42763 in 100 secs # # Time in prime : 0.11 # Time in Perrin: 99.72 # ===== # 99.83 
The output shows that when given 100 seconds to run it gets as far as n=42763, but more importantly, the timing shows that overwhelmingly it spends its time in the routine to test whether or not a number passes the "Perrin Test." So there are a few things we need to do:
There's a maxim in programming:
run faster, you can only make it do less. 
One way of making the program do less is to precompute things and then use the result multiple times. Another way is to do a quick test to avoid a longer one. We'll do both of those.
Here's the critical observation:
#!/usr/bin/python def compute_perrin_number(n): if n in [2, 3]: return 0 a0, a1, a2 = 3, 0, 2 i = n while i > 0: a0, a1, a2 = a1, a2, (a0+a1) % n i = 1 return a0 def make_pre_filter(m): rtn = [ 3 % m, 0, 2 % m ] while True: rtn.append( (rtn[3] + rtn[2]) % m ) if rtn[:3] == rtn[3:]: return rtn[:3] pre_filters = {} pre_filter_elements = range(2,104) for m in pre_filter_elements: pre_filters[m] = make_pre_filter(m) def is_perrin_q(n): for m in pre_filter_elements: if n % m == 0: pre_filter_to_use = pre_filters[m] ndx = n % len(pre_filter_to_use) if 0 != pre_filter_to_use[ndx]: return False return compute_perrin_number(n) == 0 
So here is the result.
But there's still a problem that we can see clearly when we look at the timing:
FindingPerrinPseudoPrimes Part1  :  Russian Peasant Multiplication 
You should follow me on twitter 
I'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 