mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-09-23, 17:53   #1
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009

198310 Posts
Default 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.


storm5510 is offline   Reply With Quote
Old 2009-09-23, 18:17   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by storm5510 View Post
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.


Start by reading:

D.E. Knuth, The Art of Computer Programming, Vol 2.

This will teach you about multi-precise 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.
R.D. Silverman is offline   Reply With Quote
Old 2009-09-23, 18:20   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×1,789 Posts
Default

Quote:
Originally Posted by storm5510 View Post
... an application that could find prime numbers, in general. No specific types. ...
Well, this isn't really my specialty, but I think I know this much: it really depends a lot on how big of prime numbers you want to find.

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 2009-09-23 at 18:44 Reason: elaborate a bit on general purpose tests...
bsquared is offline   Reply With Quote
Old 2009-09-23, 19:51   #4
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009

3×661 Posts
Default

Quote:
Originally Posted by bsquared View Post
...Even with these tests, you'd be doing great to be able to prove primes up to a couple thousand digits...
No, nothing near that size. A 64-bit unsigned integer as defined in Visual C#, (just above 10^18), would be the max. In reality, I would never get anywhere near that.

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 2009-09-23 at 19:52
storm5510 is offline   Reply With Quote
Old 2009-09-23, 19:57   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by storm5510 View Post
No, nothing near that size. A 64-bit unsigned integer as defined in Visual C#, (just above 10^18), would be the max. In reality, I would never get anywhere near that.

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.

Read Crandall & Pomerance. 64 bits are easy. Just factor p+1 and
p-1 up to N^1/3, then use the combined Theorem of Selfridge, Lehmer,
Brillhart, etc. See the Cunningham book.
R.D. Silverman is offline   Reply With Quote
Old 2009-09-23, 20:24   #6
Orgasmic Troll
Cranksta Rap Ayatollah
 
Orgasmic Troll's Avatar
 
Jul 2003

641 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Read. Read. Read. Do the exercizes. There is no shortcut.
Orgasmic Troll is offline   Reply With Quote
Old 2009-09-23, 20:40   #7
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009

7BF16 Posts
Default

I agree, it is a good suggestion. I'll see what I can find.
storm5510 is offline   Reply With Quote
Old 2009-09-23, 22:30   #8
Harvey563
 
Harvey563's Avatar
 
Apr 2004

2738 Posts
Thumbs up

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 0-8176-3743-5.

It is clear. There are lots of examples in Pascal. And it is all about prime proving and factoring.

Harvey563 is offline   Reply With Quote
Old 2009-09-24, 01:15   #9
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009

3×661 Posts
Post

Quote:
Originally Posted by Harvey563 View Post
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 0-8176-3743-5.

It is clear. There are lots of examples in Pascal. And it is all about prime proving and factoring.

I will check that out. Thanks.

I decided to start reading here, under "Trial Factoring".

http://www.mersenne.org/various/math.php

Quote:
The next step is to eliminate exponents by finding a small factor. There are very efficient algorithms for determining if a number divides 2P-1. For example, let's see if 47 divides 223-1. Convert the exponent 23 to binary, you get 10111. Starting with 1, repeatedly square, remove the top bit of the exponent and if 1 multiply squared value by 2, then compute the remainder upon division by 47.
Remove Optional
Square top bit mul by 2 mod 47
------------ ------- ------------- ------
1*1 = 1 1 0111 1*2 = 2 2
2*2 = 4 0 111 no 4
4*4 = 16 1 11 16*2 = 32 32
32*32 = 1024 1 1 1024*2 = 2048 27
27*27 = 729 1 729*2 = 1458 1
Thus, 223 = 1 mod 47. Subtract 1 from both sides. 223-1 = 0 mod 47. Since we've shown that 47 is a factor, 223-1 is not prime.
In the example above, the author tests 223 - 1 to see if it will divide by 47. Taking 1 away from both sides, he ends up with zero, meaning not prime.

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 multiply-by-2 is not done. The last number of each row is the Modulo.

Quote:
479 111011111 Mod

1 - 1 2 2
1 - 4 8 8
1 - 64 128 128
0 - 16384 x 98
1 - 9604 19208 48
1 - 2304 4608 297
1 - 88209 176418 146
1 - 21316 42632 1


893 1101111101 Mod

1 - 1 2 2
1 - 4 8 8
0 - 64 x 64
1 - 4096 8192 155
1 - 24025 48050 721
1 - 519841 1039682 230
1 - 52900 105800 426
1 - 181476 362952 394
0 - 155236 x 747
1 - 558009 1116018 661


1087 10000111111 Mod

1 - 1 2 2
0 - 4 x 4
0 - 16 x 16
0 - 256 x 256
0 - 65536 x 316
1 - 99856 199712 791
1 - 625681 1251362 225
1 - 50625 101250 159
1 - 25281 50562 560
1 - 313600 627200 1
1 - - -
In the first and third test, on known primes, I ended up with one. Remove that from the right, as in the left, and I have zero. The center example ends at 661. The GCD of 893 and 661 is 1.

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.

storm5510 is offline   Reply With Quote
Old 2009-09-24, 02:43   #10
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009

198310 Posts
Default

This is the exception; result is two with prime number 101.

Quote:
101 1100101 Mod

1 1 2 2
1 4 8 8
0 64 x 64
0 4096 x 56
1 3136 6272 10
0 100 x 100
1 10000 20000 2
storm5510 is offline   Reply With Quote
Old 2009-09-24, 04:40   #11
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default

Try reading your "Quick and Dirty" thread again.

Last fiddled with by davieddy on 2009-09-24 at 04:47
davieddy is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Blast from the past Dubslow GPU Computing 0 2012-05-25 03:50
Interesting to Read Past Threads 9021951 Information & Answers 0 2011-11-02 18:47
different double checking protocol in the past? ixfd64 PrimeNet 0 2008-10-19 02:27
Blasts from the Past davieddy Lounge 0 2008-06-09 19:49
Memorable GIMPS Quotes from the Past Old man PrimeNet Lounge 2 2003-12-03 18:25

All times are UTC. The time now is 04:39.


Thu Oct 21 04:39:01 UTC 2021 up 89 days, 23:08, 1 user, load averages: 1.13, 1.19, 1.60

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.