20021231, 13:05  #1  
Dec 2002
Frederick County, MD
2×5×37 Posts 
The modulo operation, how is it computed?
OK, I've looked at the math of the LL test, and for reference, here is a guote form a thread in "The Software"
Quote:


20021231, 20:21  #2  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
Re: The modulo operation, how is it computed?
Quote:
Quote:
Quote:


20021231, 20:53  #3  
"Richard B. Woods"
Aug 2002
Wisconsin USA
17014_{8} Posts 
Re: The modulo operation, how is it computed?
Quote:
"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/) 

20030102, 12:47  #4 
Dec 2002
Frederick County, MD
2×5×37 Posts 
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^p1.
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). 
20030106, 13:35  #5 
Dec 2002
Frederick County, MD
2·5·37 Posts 
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?

20030107, 07:39  #6  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
Not just any old FFT operation gives the mod 2^P1 for free.
It's CrandallFagin'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^P1. From the GIMPS math page at http://www.mersenne.org/math.htm: Quote:


20030107, 16:01  #7  
Sep 2002
7 Posts 
eepiccolo wrote
Quote:
After squaring and subtracting two, but before reducing modulo 2^p1, 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^p1) 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. 

20030108, 03:07  #8  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
Quote:
Quote:
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How is GHz days computed?  daxmick  Information & Answers  12  20171203 23:36 
Operation: Billion Digits  clowns789  Operation Billion Digits  574  20170912 01:34 
Operation Megabit Twin  Oddball  Twin Prime Search  370  20130103 21:26 
modulo operation for polynomials?  smslca  Math  3  20110418 17:18 
how are odds computed?  crash893  Software  23  20051017 03:47 