mersenneforum.org > Math Clarification: Test VS Generator
 Register FAQ Search Today's Posts Mark Forums Read

 2004-10-14, 15:59 #1 synergy   Aug 2004 2·3·7 Posts Clarification: Test VS Generator Okay, a test is a function f: positive integers --> {0,1} such that it outputs a zero if the integer is composite and a one if the integer is prime. A generator is a function f: positive integers --> prime numbers such if x is the input then the xth prime is the output. It doesn't require checking a bunch of composites. How efficient would the second type of function have to be to be quicker than the first type, for a large range of primes of any size. Amateur, this is about my theory, not yours. Doesn't even apply to yours. Aaron
 2004-10-14, 18:21 #2 synergy   Aug 2004 4210 Posts say you input 10000 and it gives you the 10000th prime, which requires some time to compute then you input 10001 and it gives you 10001th prime then you input 10002 and it gives you 10002th prime then you input 10003 and it gives you 10003th prime each of which requires some time to compute. now this program is racing against a program that checks all odds after the 10001th prime to see if they are prime. after checking alot of composites, it finds the 10002th prime. then it checks more odds until it finds the 10003th prime. My question is, how efficient must the first program be to surpass the second program in efficiency?
 2004-10-14, 18:23 #3 synergy   Aug 2004 2·3·7 Posts I'm not saying my method does exactly that, but it's close to working like that, and I'm sure that it's not efficient enough, yet, but I have plans to "tweak" the method. Aaron
 2004-10-14, 22:07 #4 synergy   Aug 2004 2·3·7 Posts A bit more clarifying... I guess that exactly the question I have is, how fast must it run to find ALL OF the primes in a range at the same rate that the second program finds them, given that the second program checks every odd between the nth prime and the n+1th prime, and the first program just computes the nth prime and the n+1th prime directly from input values n and n+1, not needing to test anything at all - particularly not even considering values between the two primes. No test, just input and output. Input 42, output the fourty-second prime. Maybe next you input 100 and output the one hundredth prime, it can skip around that way. Put another way, given that you know 2,3,5...31, find primes through 53. The second program tests 33,35,37,39,41,43,45,47,49,51, and 53 for primality. The first program inputs 12 and gets out the 12th prime, 37, inputs 13 and gets out 41, inputs 14 and gets out 43, inputs 15 and gets out 47, inputs 16 and gets out 53, and is done. 5 inputs, 5 primes output. The second program input 11 odd numbers to test for primality, and output 5 primes. For higher ranges, the second program might have to test hundreds of consecutive odds to find 5 consecutive primes, while the first program will still only have 5 inputs to output the 5 primes.
 2004-10-15, 07:23 #5 biwema     Mar 2004 17D16 Posts Assuming you want to find the n'th prime: No proof here, but I would prefer this strategy: The function Pi(x) is more efficient than calculating all Primes up to a limit. According to http://numbers.computation.free.fr/C...ingPrimes.html Pi(x) has a Complexity of O(x^1/2). Li(x) and R(x) are Approximations which should be better than an error of sqrt(x). Say you want to find the 100000th prime So my Recipe: 1. Calculate Li(x) or R(x) and try to approximate Li(x) = 100000 (with Newton?) 2. Calculate Pi(x) of that x you have found. 3. Sieve forward or back until you have found your prime. In case you want to find all primes in some range, you can either sieve or test all for primalty. Which approach is faster depends on the size of the range and Primes, the algorithm and the architecture of the computer. In case you found the starting prime using the recipe above, you still have the sieved array (step 3) in your computer, where you just can pick your primes.
2004-10-15, 09:01   #6
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

2×17×313 Posts

Quote:
 Originally Posted by biwema Assuming you want to find the n'th prime: No proof here, but I would prefer this strategy: The function Pi(x) is more efficient than calculating all Primes up to a limit. According to http://numbers.computation.free.fr/C...ingPrimes.html Pi(x) has a Complexity of O(x^1/2). Li(x) and R(x) are Approximations which should be better than an error of sqrt(x). Say you want to find the 100000th prime So my Recipe: 1. Calculate Li(x) or R(x) and try to approximate Li(x) = 100000 (with Newton?) 2. Calculate Pi(x) of that x you have found. 3. Sieve forward or back until you have found your prime. In case you want to find all primes in some range, you can either sieve or test all for primalty. Which approach is faster depends on the size of the range and Primes, the algorithm and the architecture of the computer. In case you found the starting prime using the recipe above, you still have the sieved array (step 3) in your computer, where you just can pick your primes.
But sieving involves checking composites, unless I misunderstand your use of that term.

Binary search lets you avoid that particular problem. To find the i-th prime, find by some means two values of x such that pi(x1) <= i <= pi(x2). One such approach would be to start with x1 = 2, x2=3 and then repeatedly iterate x1=x2, x2=2*x2 until the inequality is satisfied. Then raise x1 or lower x2 as appropriate, always maintaining the inequality, until x1==x2.

Paul

 2004-10-15, 17:35 #7 synergy   Aug 2004 4210 Posts Nice to see some of you are seeing what I'm getting at... For anybody still not sure, I've simplified it somewhat: Let's pick a range, say all x between 10^9 and 10^10. Now, let e=the efficiency of standard programs in proving x is either prime or composite, in terms of the time it takes. Let E=the time it takes to find (and prove the primality of) a prime number Then E=e*(the number of integers you tested before finding the prime) So, if you can prove a number is prime in 100 hours, and it takes my program 1000 hours to generate a prime, then e=100 for you and 1000 for me, yours is ten times more efficient than mine at PROVING PRIMALITY. However, if you examined 100 integers before finding the prime, then it took you 10000 hours to find the prime, so E=10000 for you and still only 1000 for me, and mine is ten times more efficient than yours for FINDING A PRIME. Now, I think my question is more clear, i.e. how efficient must a program of the second type be, in order to be as fast as the first type? I welcome all coments, both positive and negative criticism, although really, how can you criticize a question, when I'm not making any claim? I've already stated my algorithm has a setback or two, such at duplicate prime outputs. I just want to know, in theory, if we had an "oracle" program, how fast would it have to be, in terms of the size of the primes, to top known techniques? Thanks for the comments, I'll study them. Aaron Last fiddled with by synergy on 2004-10-15 at 17:36
 2004-10-15, 18:16 #8 synergy   Aug 2004 2×3×7 Posts Here's a couple examples of my algorithm: Let's look at the absolute value of 15 plus or minus 2^x, for outputs less than 7^2=49. No such output can have a factor of 2,3, or 5. This is one of a sequence of equations which gets all primes less than 49. I write this as abs( 15 +/- 2^x ) = q(x), where q(x)<49. Actually, if you want the entire theory in a nutshell, look at abs( 3^y * 5^z +/- 2^x ) = q1(x,y,z) where q1(x,y,z)<49, then look at q2(x,y,z)= abs( 2^x*3^y +/- 5^z ) and q3(x,y,z) = abs( 2^x*5^z +/- 3^y), where qi<49. You can see that I've partitioned the set {2,3,5} into two disjoint sets, one on each side of the +/-. If you work this out, you will get every prime less than 49, depending on the integer exponents >0 that you input. When q1 gets "tired", move to q2, etc. For the next step in the algorithm, partition the set of primes {2,3,...43} into two disjoint subsets, one on each side of the +/-, with each prime independently exponentiated with positive integers, and the output will be prime when it is less than 47^2=2209. To get all primes in that range, repartition the sets as necessary. I haven't actually gotten that high so far, but I have found every single prime less than 37^2=1369 using this method. Now, my question wasn't exactly about this algorithm, since the primes it finds come in no linear order and my algorithm does have repeated outputs i.e. it might produce 29 six times (though I expect the repeats to dwindle at high prime values). Also notice that, like the sieve, you can get a set "enriched" with primes simply by ignoring the less-than test, for example, 15 +/- 2^x will eliminate all composites with 2,3, or 5 as factors, even if we look at outputs higher than 49. My question was about an "ideal" program that produces the 49th prime when we input the number 49, and how fast such a program would need to be, since, like mine, it doesn't eliminate composites one at a time but rather it eliminates them all from the start, which might make it more efficient in terms of finding a prime even if it is slower at proving primality. I think this is a useful question, as it might provide an "upper-bound" of sorts on how fast we could find primes. Aaron Last fiddled with by synergy on 2004-10-15 at 18:17 Reason: forgot something
 2004-10-15, 18:26 #9 ET_ Banned     "Luigi" Aug 2002 Team Italia 12CB16 Posts It takes less than one twentieth of second to BUILD ALL primes in the range 10^9-10^10. It takes (nearly) forever to prove for primality one number with one million digits. There are deterministic (APR-CL and ECPP) and probabilistic (Miller-Rabin) algorithms that use a time that is proportional to the length of the prime to test. I would not try to squash a mosquito with a cannonball, there are obviously more efficient instruments to do it. Conversely, you can't scare out an elephant with a toothpick. It's a matter of scale. If your algorithm has a resolution time that grows slower than (say) APR-CL, then I'd really be interested in it; however it should be tested on a range where its time is comparable to other known algorithms to be correctly valued. What I am trying to say is that I would never test for primality each odd in the range you proposed, because there are far faster methods to check or even create them. That said, I'm not deducing that your system won't work, I'm just asking for a fair comparison. Luigi Last fiddled with by ET_ on 2004-10-15 at 18:28
2004-10-15, 19:28   #10
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by synergy Nice to see some of you are seeing what I'm getting at... For anybody still not sure, I've simplified it somewhat: Let's pick a range, say all x between 10^9 and 10^10. Now, let e=the efficiency of standard programs in proving x is either prime or composite, in terms of the time it takes. Let E=the time it takes to find (and prove the primality of) a prime number Then E=e*(the number of integers you tested before finding the prime) So, if you can prove a number is prime in 100 hours, and it takes my program 1000 hours to generate a prime, then e=100 for you and 1000 for me, yours is ten times more efficient than mine at PROVING PRIMALITY. However, if you examined 100 integers before finding the prime, then it took you 10000 hours to find the prime, so E=10000 for you and still only 1000 for me, and mine is ten times more efficient than yours for FINDING A PRIME. Now, I think my question is more clear, i.e. how efficient must a program of the second type be, in order to be as fast as the first type? I welcome all coments, both positive and negative criticism, although really, how can you criticize a question, when I'm not making any claim? I've already stated my algorithm has a setback or two, such at duplicate prime outputs. I just want to know, in theory, if we had an "oracle" program, how fast would it have to be, in terms of the size of the primes, to top known techniques? Thanks for the comments, I'll study them. Aaron
"So, if you can prove a number is prime in 100 hours, and it takes my program 1000 hours to generate a prime, then e=100 for you and 1000 for me, yours is ten times more efficient than mine at PROVING PRIMALITY."

This is meaningless gibberish. You are comparing TWO DIFFERENT THINGS.
One is an algorithm that GENERATES primes, another is one that TESTS
CANDIDATES FOR PRIMALITY.

They are two different things. Your "questions" are devoid of any
is gibberish because you are assigning constants to things that should
be functions of the PROBLEM SIZE.

Asking in vague general terms for the "best algorithm" is meaningless
because different algorithms have different crossover points, and different
algorithms behave different on varying computer architectures. You also
have to consider differences in programming technique.

I have said this before and you have ignored the advice.

Learn about different types of algorithms. Learn what a Turing machine is.
Learn that there are different models of computation. Learn some number
theory.

 Similar Threads Thread Thread Starter Forum Replies Last Post bhelmes Miscellaneous Math 2 2016-03-17 17:50 JuanTutors Software 6 2012-11-15 05:00 synergy Miscellaneous Math 13 2004-10-14 18:14 synergy Miscellaneous Math 39 2004-09-21 17:10 Unregistered Programming 6 2004-03-21 01:00

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

Tue Apr 13 01:09:55 UTC 2021 up 4 days, 19:50, 1 user, load averages: 2.90, 2.85, 2.63