mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Getting Past My Naivety (https://www.mersenneforum.org/showthread.php?t=12494)

 storm5510 2009-09-23 17:53

Getting Past My Naivety

[FONT=Tahoma]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.[/FONT]

[FONT=Tahoma]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.[/FONT]

[FONT=Tahoma]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.[/FONT]

[FONT=Tahoma]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.[/FONT]

[FONT=Tahoma]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.

:smile:
[/FONT]

 R.D. Silverman 2009-09-23 18:17

[QUOTE=storm5510;190850][FONT=Tahoma]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.[/FONT]

[FONT=Tahoma]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.[/FONT]

[FONT=Tahoma]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.[/FONT]

[FONT=Tahoma]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.[/FONT]

[FONT=Tahoma]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.

:smile:
[/FONT][/QUOTE]

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.

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.

 bsquared 2009-09-23 18:20

[quote=storm5510;190850][FONT=Tahoma]...[/FONT][FONT=Tahoma] an application that could find prime numbers, in general. No specific types. ...[/FONT][/quote]

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.

 storm5510 2009-09-23 19:51

[quote=bsquared;190852]...Even with these tests, you'd be doing great to be able to prove primes up to a couple thousand digits...[/quote]

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.

:smile:

 R.D. Silverman 2009-09-23 19:57

[QUOTE=storm5510;190855]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.

:smile:[/QUOTE]

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.

 Orgasmic Troll 2009-09-23 20:24

:goodposting::goodposting::goodposting:

 storm5510 2009-09-23 20:40

I agree, it is a good suggestion. I'll see what I can find.

 Harvey563 2009-09-23 22:30

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.

:toot:

 storm5510 2009-09-24 01:15

[quote=Harvey563;190869]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.

:toot:[/quote]

I will check that out. Thanks. :smile:

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

[URL]http://www.mersenne.org/various/math.php[/URL]

[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.[INDENT][INDENT] 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
[/INDENT][/INDENT]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.
[/quote]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 - - -
[/quote]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.

:smile:

 storm5510 2009-09-24 02:43

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[/quote]:redface:

 davieddy 2009-09-24 04:40

 storm5510 2009-09-24 05:29

I found this interesting:

[quote]An ancient method which appeared about 200 BC in Pingala's Hindu classic [I]Chandah-sutra[/I] (and now called [B]left-to-right binary exponentiation[/B]) can be described as follows. First write the exponent 25 in binary: 11001. Remove the first binary digit leaving 1001 and then replace each remaining '1' with the pair of letters 'sx' and each '0' with the letter 's' to get: sx s s sx. Now interpret 's' to mean square, and 'x' to mean multiply by [I]x[/I], so we have:[INDENT] square, multiply by [I]x[/I], square, square, square, multiply by [I]x[/I]. [/INDENT]These are our instructions to follow; so if we start with [I]x[/I], we then calculate in turn [I]x[/I]2, [I]x[/I]3, [I]x[/I]6, [I]x[/I]12, [I]x[/I]24, and [I]x[/I]25. This took 6, not 24, multiplications. For large exponents the savings is dramatic! For example, using this method to calculate: [I]x[/I]1000000 takes 25 multiplications; [I]x[/I]12345678901234567890 takes 94 multiplications; and if [I]n[/I]=101000, then calculating [I]xn[/I] takes just 4483 multiplications. In general, binary exponentiation will always take less than 2log([I]n[/I])/[URL="http://primes.utm.edu/glossary/xpage/Log.html"]log[/URL](2) multiplications. [/quote]The author make it too fuzzy to program. He uses "x" but does not describe what "x" is. On to other pages...

[quote=storm5510;190880]I decided to start reading here, under "Trial Factoring".

[URL]http://www.mersenne.org/various/math.php[/URL]

In the example above, the author tests 223 - 1 to see if it will divide by 47.[/quote]When you copied the text, you may not have noticed that the superscript formatting of the exponent in 2[sup]23[/sup]-1 wasn't copied over.

So, it's not testing 223 - 1. It's testing 2[sup]23[/sup] - 1. Another notation, not requiring superscripts, is 2^23 - 1.

[quote]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.[/quote]But what you tried was not the proper algorithm, due to your misunderstanding of the example on page [URL]http://www.mersenne.org/various/math.php[/URL]

So, you didn't get correct results.

[quote]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.[/quote]But since the algorithm on page [URL]http://www.mersenne.org/various/math.php[/URL] works only for Mersenne numbers, what you did, [I]sort of[/I], was to use a copy of the example format to test 2[sup]479[/sup]-1 for divisibility by something, 2[sup]893[/sup]-1 for divisibility by something, and 2[sup]1087[/sup]-1 for divisibility by something. (I don't know the "something"s.)

What's really needed is to go back farther to where you made the first mistake, correct that, then proceed from that corrected situation. Don't try to repair anything after your incorrect copy-and-paste until that first step is corrected, or else it'll just remain a mess.

[quote]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.

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.
[/quote]... but these details are all meaningless, because the mistake was earlier.

Start by going back and getting the formatting straight in your copy-and-paste from [URL]http://www.mersenne.org/various/math.php[/URL], so that you know which numbers are exponents and which are not. In most browsers, a simple copy-and-paste won't preserve the superscripting, so you'll need to reinsert it manually.

[quote=storm5510;190897]I found this interesting:

The author make it too fuzzy to program. He uses "x" but does not describe what "x" is. On to other pages...[/quote]But, once again, you did not properly reinsert the superscript formatting after your copy-and-paste, so what you quote as
[quote][I]x[/I]2, [I]x[/I]3, [I]x[/I]6, [I]x[/I]12, [I]x[/I]24, and [I]x[/I]25[/quote]should have been
[quote][I]x[/I][sup]2[/sup], [I]x[/I][sup]3[/sup], [I]x[/I][sup]6[/sup], [I]x[/I][sup]12[/sup], [I]x[/I][sup]24[/sup], and [I]x[/I][sup]25[/sup][/quote]or, alternatively,[quote][I]x[/I]^2, [I]x[/I]^3, [I]x[/I]^6, [I]x[/I]^12, [I]x[/I]^24, and [I]x[/I]^25[/quote]Once you redo the copy-and-paste and have all those exponents straight, we can proceed from there. (I'll bet that after you have all the exponents correctly indicated, other parts will become clearer to you.)

 schickel 2009-09-24 07:35

[QUOTE=storm5510;190880]The spacing went to crap! [/QUOTE]One help is to use [ CODE] tags rather than [ QUOTE] tags around your quoted text. The CODE tag keeps the spacing exactly as typed, the QUOTE tag collapses multiple spaces to a single space and wraps as needed on long lines, which depends on the screen resolution of the readers' browser windows....

 xilman 2009-09-24 07:42

[QUOTE=Harvey563;190869]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.

:toot:[/QUOTE]Seconded. I like this book too.

Beware, though, it is badly out of date now. It's good for learning the basic algorithms, but don't expect to find anything about the bleeding edge.

Actually, much the same can be said about Bob's recommendation of Knuth Vol 2. It's a superb book and is required reading, IMAO, but substantial progress has been made since it was written. The programs may be difficult to read, being written in the assembly language for a non-existent 1960's computer. However, it is certainly worth the effort to learn that language, even though it is bizarre to modern eyes.

Paul

 storm5510 2009-09-24 07:54

[quote=cheesehead;190900]...But since the algorithm on page [URL]http://www.mersenne.org/various/math.php[/URL] works only for Mersenne numbers...[/quote]

This is all I needed to know. Yes, I did mess up the copy-past process. I knew better.

[quote="cheesehead"]Once you redo the copy-and-paste and have all those exponents straight, we can proceed from there. (I'll bet that after you have all the exponents correctly indicated, other parts will become clearer to you.)[/quote]

I managed to code it. It gives the same results as Excel. As you said, for Mersenne numbers only.

[quote="schickel"] One help is to use [ CODE] tags rather than [ QUOTE] tags around your quoted text... [/quote]

Good point.

 Xyzzy 2009-09-25 05:50

Possibly not relevant, but fun to read: