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-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: