20090923, 17:53  #1 
Random Account
Aug 2009
3626_{8} Posts 
Getting Past My Naivety
I will admit it. When it comes to mathematical theory and advanced subjects, I am naive as one can be. I am not too proud to admit it. At the same time, I am fascinated by it. I am afraid this fascination came too late. I had no interest in it when I was younger, beyond what I needed in everyday life. Then the computer age came into being and I knew I had messed up, badly.
I like to think of myself as being a decent programmer. I took to it right off in college. Languages like Pascal, Basic, and COBOL were all easy. C+ and Assembly were a lot harder but I managed. The problem then, and still now, is my lack of mathematical understanding. This inability puts a cap on what I can do in programming. I would like to get past my naivety to some small degree if possible. In the past when I have asked questions here, I have been given links to pages on Wikipedia, mostly. That is fine. There is no need to write something out that already exists. I found a lot of those pages using mathematical notation to varying degrees. Some of it I can understand; those being the things I saw when studying industrial and digital electronics in college. The rest, not so well. So, here is the lay of it. In 2005, I wrote an application that could find prime numbers, in general. No specific types. It was the GIMPS project which peaked, and still holds, my interest. I knew that prime numbers were only divisible by themselves, and one. So, that is what I based my application on. Wikipedia calls what I used the "naive" way. It is the longest way; taking a number and dividing it by every odd value above two to the value of the number, minus two, and skipping units of five. I would like to learn a better way to do this, and I am asking for assistance. If someone would lend a hand, that would be wonderful. If not, then that will be alright too. I understand. 
20090923, 18:17  #2  
Nov 2003
2^{2}×5×373 Posts 
Quote:
D.E. Knuth, The Art of Computer Programming, Vol 2. This will teach you about multiprecise arithmetic and a lot of other things. Aho, Hopcroft & Ullman also wrote an excellent book on Algorithms. add a decent book on number theory. Hardy & Wright, Introduction to the Theory of Numbers is a good text and quite broad; it covers a lot of topics. Try also: D. Shanks, Solved & Unsolved Problems in Number Theory. Then add a good general book about modern algebra. There are a lot of good ones. Stay away from S. Lang's effort. I would recomment Hungerford's book, but it is likely too difficult. Birkhoff & MacLane is excellent. Then you can try reading Crandall & Pomerance's book. Read. Read. Read. Do the exercizes. There is no shortcut. 

20090923, 18:20  #3  
"Ben"
Feb 2007
2·3^{2}·191 Posts 
Quote:
You can use a sieve to find ALL prime numbers up to several billion in a few seconds. You can use these primes to test numbers up to about 20 digits long in a few more seconds, using the naive approach. Anything much more than that and you have to start using quite a bit more math involved in general purpose primalty proving algorithms, because the number of divisions to perform grows to quickly to continue using the naive approach. General purpose primalty proving algorithm include the APRCL test and ECPP (probably others). Even with these tests, you'd be doing great to be able to prove primes up to a couple thousand digits. Any bigger than that, and you're only hope is that the number has a special form and corresponding prime proving algorithm (Mersenne's, Fermat's). That's where my usefullness (such as it is) stops. Last fiddled with by bsquared on 20090923 at 18:44 Reason: elaborate a bit on general purpose tests... 

20090923, 19:51  #4  
Random Account
Aug 2009
2·971 Posts 
Quote:
I want this to be a learning process. If someone just hands me a solution, I won't get much from it. I would rather be led to it. Last fiddled with by storm5510 on 20090923 at 19:52 

20090923, 19:57  #5  
Nov 2003
2^{2}·5·373 Posts 
Quote:
p1 up to N^1/3, then use the combined Theorem of Selfridge, Lehmer, Brillhart, etc. See the Cunningham book. 

20090923, 20:24  #6 
Cranksta Rap Ayatollah
Jul 2003
641 Posts 

20090923, 20:40  #7 
Random Account
Aug 2009
2×971 Posts 
I agree, it is a good suggestion. I'll see what I can find.

20090923, 22:30  #8 
Apr 2004
3·61 Posts 
I my opinion the very best reference for what you want to do is:
H. Riesel, Prime numbers and computer methods for factorization, Progress in Mathematics Vol, 126, BirkhĂ¤user Boston, Boston, MA, 1994. ISBN 0817637435. It is clear. There are lots of examples in Pascal. And it is all about prime proving and factoring. 
20090924, 01:15  #9  
Random Account
Aug 2009
11110010110_{2} Posts 
Quote:
I decided to start reading here, under "Trial Factoring". http://www.mersenne.org/various/math.php Quote:
Below is a variation of that same procedure I tried in Excel. What I did was to take the same value and place it on both sides. 479 and 1087 are prime numbers. Not Mersenne. 893 is not prime. The spacing went to crap! Down the left side is the binary string as shown across the top. An "x" appears on the same rows as a binary "0" to indicate the multiplyby2 is not done. The last number of each row is the Modulo. Quote:
I wasn't expecting this type of result. I assumed anything on the GIMPS site would be exclusive to multiples of two. The strange part is, I can make this work in Excel, but not in code. 

20090924, 02:43  #10  
Random Account
Aug 2009
2×971 Posts 
This is the exception; result is two with prime number 101.
Quote:


20090924, 04:40  #11 
"Lucan"
Dec 2006
England
2×3×13×83 Posts 
Try reading your "Quick and Dirty" thread again.
Last fiddled with by davieddy on 20090924 at 04:47 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Blast from the past  Dubslow  GPU Computing  0  20120525 03:50 
Interesting to Read Past Threads  9021951  Information & Answers  0  20111102 18:47 
different double checking protocol in the past?  ixfd64  PrimeNet  0  20081019 02:27 
Blasts from the Past  davieddy  Lounge  0  20080609 19:49 
Memorable GIMPS Quotes from the Past  Old man PrimeNet  Lounge  2  20031203 18:25 