The modulo operation, how is it computed?

[eepiccolo]

OK, I've looked at the math of the LL test, and for reference, here is a guote form a thread in "The Software"

Originally Posted by smh

The math page gives more information about what the program actually does.

From that page:

People talk about the multiplication of large numbers, and how we use a DFT to accomplish this. While I don't fully understand this process yet, I have found resources and am studying it. However, I haven't found anything about how the modulo operation works. Is the modulo operation something so simple that people don't really talk about it? If so, I'm sure someone could give me a simple explanation of how the operation is preformed. Or perhaps something else is going on that I haven't found out about yet? Could someone please help me out on this?

[cheesehead]

Originally Posted by smh

From that page:

There's a mistake in that quote.

... if and only if S^p-2 is zero ...

should be

... if and only if S(p-2) is zero ...

[cheesehead]

Originally Posted by eepiccolo

Is the modulo operation something so simple that people don't really talk about it?

Um ... yeah ... but once you know the secret password, it's easy. :)

"M modulo N", in the context of GIMPS, basically means "the remainder when M is divided by N". "Modulo" is usually abbreviated as "mod".

Examples:[list]7 mod 2 = 1
7 mod 4 = 3
8 mod 2 = 0
2 mod 8 = 2[/list:u]

There's more to it than just that, but as long as you're discussing only positive integers, you can usually get along all right with the simple "remainder when M is divided by N" definition.

"Congruence" is a term closely associated with "modulo".

See http://mathworld.wolfram.com/Congruence.html for a more complete explanation of "modulo".

(BTW, http://mathworld.wolfram.com/ is a great reference for almost any mathematical term! Eric Weisstein, its author, has done a great service to mathematics by compiling definitions and explanations of thousands (over 11,000) of math terms.

But that's not all! Eric Weisstein has also compiled similar databases for some of the sciences and music. See http://www.ericweisstein.com/encyclopedias/)

[eepiccolo]

Actually... I wasn't refering to what the modulus opperator does... I have a pretty good handle on congruences and whatnot. I am curious from a computer's point of view how a mod is calculated, which I guess boils down do modular arithmetic in base 2. The impression I get is that there is some sort of shortcut to taking mods with 2^p-1.
I'm just trying to figure out why we don't have to worry about the time it takes to mod, since from all I've read, we only worry about the time it takes to square (which, of course, is sped up by an FFT).

[eepiccolo]

Hmmm, now, before the crash , Cheesehead had told me that the FFT gives us the mod for free. But someone else had also given a method for taking mods, and unfortunately, I don't remember who that was, and I didn't write down what that person wrote. So could whoever it was that posted that please post their reply again?

[cheesehead]

Not just any old FFT operation gives the mod 2^P-1 for free.

It's Crandall-Fagin's discrete weighted transform using an irrational base that mods for free, because it performs within itself the same set of operations that produce the mod 2^P-1.

From the GIMPS math page at http://www.mersenne.org/math.htm:

In a January, 1994 Mathematics of Computation article by Richard Crandall and Barry Fagin titled "Discrete Weighted Transforms and Large-Integer Arithmetic", the concept of using an irrational base FFT was introduced. This improvement more than doubled the speed of the squaring by allowing us to use a smaller FFT and it performs the mod 2^P-1 step for free.

[zygote]

eepiccolo wrote

But someone else had also given a method for taking mods

The method only works when the calculation is done in base 2, which fortunately is the way computers are designed. It relies on the fact that 2^p-1 is one less than a power of two. In mod notation, 2^p = 1 (mod 2^p-1). That allows one to reduce the modulo calculation to a simple additon.

After squaring and subtracting two, but before reducing modulo 2^p-1, S(n) is a number of no more than 2p binary digits. This can be written

S(n) = 2^p * (top p significant digits) + (bottom p significant digits)
= (top p significant digits) + (bottom p significant digits) (mod 2^p-1)

Please note how similar this is to determining whether a base 10 number is divisible by 9. The fact that 9 is one less than a power of ten allows one to transform an issue of divisibility into a simple addition problem by the method of "casting out nines". Simply add up the digits of the number and check to see if the sum is divisible by nine.

[cheesehead]

Originally Posted by zygote

S(n) = 2^p * (top p significant digits) + (bottom p significant digits)
= (top p significant digits) + (bottom p significant digits) (mod 2^p-1)

Let me add brackets to avoid the potential misinterpretation I made first time I read this:

S(n) = [ 2^p * (top p significant digits) ] + [ (bottom p significant digits) ]
= [ (top p significant digits) + (bottom p significant digits) ] (mod 2^p-1)

IOW, add the top p significant digits (as a p-bit integer) to the bottom p significant digits (as another p-bit integer), then (if there was a carry out of the most significant bit during the addition) do a modulo 2^p-1 on that sum.

Originally Posted by zygote

Please note how similar this is to determining whether a base 10 number is divisible by 9. The fact that 9 is one less than a power of ten allows one to transform an issue of divisibility into a simple addition problem by the method of "casting out nines". Simply add up the digits of the number and check to see if the sum is divisible by nine.

Yes! We're "casting out (2^p-1)s"! :D