mersenneforum.org > Math Small prime test divisor efficiency strategy
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2007-07-18, 05:59 #1 fenderbender     Jul 2007 17 Posts Small prime test divisor efficiency strategy I'm coding my own c++ library of number theory routines (because it's the best way to learn!). I am now working on a general "is this number prime?" routine. My basic strategy is trial division for the first (few hundred?) primes, then a-pseudoprime tests for a=2,3,5, etc. If I get really ambitous I'll implement the Ballie-PSW test. My question is a general efficiency one. For testing the list of the first few hundred primes, is it generally faster to do trial divisions of each divisor sequentially, or to do a GCD with the product of many primes at once? I am sure the exact balance depends on implementation efficiency of divides and GCD, but I would expect that for testing hundreds of divisors, you'd end up using the GCD to do many in parallel. But online code (for example the clean presentation by Thomas Nicely) uses explicit division for each of the the first 6000+ primes, not GCD. I have only penciled in the rough guess of computational efficiency but surely a GCD of many primes at once will take far fewer operations (admittedly using larger numbers) than explicit divides. Or maybe the "early abort" of individual tests is efficient.. once you find a divisor, you don't really care about any others, you know it's not prime. Thanks for any advice!
2007-07-18, 13:10   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·1,889 Posts

Quote:
 Originally Posted by fenderbender I'm coding my own c++ library of number theory routines (because it's the best way to learn!). I am now working on a general "is this number prime?" routine. My basic strategy is trial division for the first (few hundred?) primes, then a-pseudoprime tests for a=2,3,5, etc. If I get really ambitous I'll implement the Ballie-PSW test. My question is a general efficiency one. For testing the list of the first few hundred primes, is it generally faster to do trial divisions of each divisor sequentially, or to do a GCD with the product of many primes at once? I am sure the exact balance depends on implementation efficiency of divides and GCD, but I would expect that for testing hundreds of divisors, you'd end up using the GCD to do many in parallel. But online code (for example the clean presentation by Thomas Nicely) uses explicit division for each of the the first 6000+ primes, not GCD. I have only penciled in the rough guess of computational efficiency but surely a GCD of many primes at once will take far fewer operations (admittedly using larger numbers) than explicit divides. Or maybe the "early abort" of individual tests is efficient.. once you find a divisor, you don't really care about any others, you know it's not prime. Thanks for any advice!

A GCD of (N, Prod p_i, i < k) should be faster than trial dividing the
primes up to p_k, but (as you point out), whether it is faster in practice depends on HOW LIKELY it is that N is prime. Trial division aborts after
a divisor is found, so you may not do most of the divisions. If N is drawn
truly uniformly at random from some interval, then trial division should be
faster on average. If you have some prior expectation that N might be prime
(for whatever reason), the GCD's will probably be faster.

However, you are optimizing something that only takes microseconds
anyway.

2007-07-18, 16:36   #3
fenderbender

Jul 2007

17 Posts

Quote:
 Originally Posted by R.D. Silverman If N is drawn truly uniformly at random from some interval, then trial division should be faster on average. If you have some prior expectation that N might be prime (for whatever reason), the GCD's will probably be faster. However, you are optimizing something that only takes microseconds anyway.
That's a good point, context really matters, since depending on application, you may truly expect a prime with only rare exceptions, or have random numbers which will likely be composite. It's almost worth making two routines.

You're also right that actual evaluation is microseconds, but in my mind this may be something that could be repeated bilions or trillions of times, so it's elegant to get it efficient. [That kind of elegant optimization is the bane, and the joy, of perfectionist programmers.]

Thanks!

2007-07-18, 17:03   #4
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

1D8416 Posts

Quote:
 Originally Posted by fenderbender That's a good point, context really matters, since depending on application, you may truly expect a prime with only rare exceptions, or have random numbers which will likely be composite. It's almost worth making two routines. You're also right that actual evaluation is microseconds, but in my mind this may be something that could be repeated bilions or trillions of times, so it's elegant to get it efficient. [That kind of elegant optimization is the bane, and the joy, of perfectionist programmers.] Thanks!
What application might try to test primality of "billions" or "trillions" of numbers
by trial division?

2007-07-18, 18:18   #5
fenderbender

Jul 2007

17 Posts

Quote:
 Originally Posted by R.D. Silverman What application might try to test primality of "billions" or "trillions" of numbers by trial division?

That.... is a very very good question... and one that I hadn't clearly thought about! I am so "new" to the game I am just building up some fundamental routines and hadn't thought how they might be used.

The only answer to a billions-of-isPrime tests is probably some naive algorithm such as doing trial divisions for (lots) of small primes, and the routine would use the prime test to come up with those trial divisors. But that's a pretty inelegant algorithm.. it'd be fine for hundreds or even a million imes, but a billion.. ?

Heh, thanks for making me think about the importance of what routines need speed and which don't. Your simple reply made me think about that more.

 2007-07-18, 18:39 #6 bsquared     "Ben" Feb 2007 1110101101002 Posts If you are new, and looking for routines/algorithms to learn about and implement, one that is relevant to finding primes in a (possibly very large) list of numbers is a sieve. The sieve of Eratosthenes is simple, and quite well known. However, really efficient versions involve some sophisticated coding, knowledge of the computer architecture, and some number theory to boot. It is a great algorithm for people that like to tinker/optimize. Here are a couple good sites that descibe efficient versions of the algorithm. http://www.ieeta.pt/~tos/software/prime_sieve.html http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html - ben.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 6 2017-09-01 13:59 mickfrancis Factoring 2 2016-05-06 08:13 lukasz Linux 1 2007-01-09 16:16 synergy Miscellaneous Math 13 2004-10-14 18:14 juergen Math 2 2004-07-10 23:01

All times are UTC. The time now is 05:09.

Thu Jun 1 05:09:16 UTC 2023 up 287 days, 2:37, 0 users, load averages: 1.16, 1.07, 1.00

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔