Getting Past My Naivety

[storm5510]

I found this interesting:

An ancient method which appeared about 200 BC in Pingala's Hindu classic Chandah-sutra (and now called left-to-right binary exponentiation) 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 x, so we have:

square, multiply by x, square, square, square, multiply by x.

These are our instructions to follow; so if we start with x, we then calculate in turn x2, x3, x6, x12, x24, and x25. This took 6, not 24, multiplications. For large exponents the savings is dramatic! For example, using this method to calculate: x1000000 takes 25 multiplications; x12345678901234567890 takes 94 multiplications; and if n=101000, then calculating xn takes just 4483 multiplications. In general, binary exponentiation will always take less than 2log(n)/log(2) multiplications.

The author make it too fuzzy to program. He uses "x" but does not describe what "x" is. On to other pages...

[cheesehead]

Originally Posted by storm5510

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

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

In the example above, the author tests 223 - 1 to see if it will divide by 47.

When you copied the text, you may not have noticed that the superscript formatting of the exponent in 2²³-1 wasn't copied over.

So, it's not testing 223 - 1. It's testing 2²³ - 1. Another notation, not requiring superscripts, is 2^23 - 1.

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.

But what you tried was not the proper algorithm, due to your misunderstanding of the example on page http://www.mersenne.org/various/math.php

So, you didn't get correct results.

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.

But since the algorithm on page http://www.mersenne.org/various/math.php works only for Mersenne numbers, what you did, sort of, was to use a copy of the example format to test 2⁴⁷⁹-1 for divisibility by something, 2⁸⁹³-1 for divisibility by something, and 2¹⁰⁸⁷-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.

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.

... 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 http://www.mersenne.org/various/math.php, 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.

[cheesehead]

Originally Posted by storm5510

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

But, once again, you did not properly reinsert the superscript formatting after your copy-and-paste, so what you quote as

x2, x3, x6, x12, x24, and x25

should have been

x², x³, x⁶, x¹², x²⁴, and x²⁵

or, alternatively,

x^2, x^3, x^6, x^12, x^24, and x^25

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]

Originally Posted by storm5510

The spacing went to crap!

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]

Originally Posted by Harvey563

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.

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]

Originally Posted by cheesehead

...But since the algorithm on page http://www.mersenne.org/various/math.php works only for Mersenne numbers...

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

Originally Posted by 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.)

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

Originally Posted by schickel

One help is to use [ CODE] tags rather than [ QUOTE] tags around your quoted text...

Good point.

[Xyzzy]

Possibly not relevant, but fun to read:

http://www.troubleshooters.com/codec...imenumbers.htm

[storm5510]

I saw another bit-array sample written in VB6. It was complex just like the C++ code is in the page you linked to. Worthy of study.