extremely large numbers

[Mini-Geek]

How can a programming language do functions with extremely large numbers, such as the over 10 million digit Mersenne numbers being tested by GIMPS? How does it let you have an integer with more than 64 bits? I know it must be somewhere in the source code for Prime95, but I don't know C, so I can't find it.

[ewmayer]

Most programming languages don't in fact have support for such data types - but just think of the way you write a decimal integer of any length, then think of using a computer to store "digits" of some huge number with respect to a convenient base (i.e. each digit something that fits in a computer word, say base-2³² or similar). The relevant arithmetic operations then simply become operations on vectors. The key is to get these vector operations (especially multiplication) to execute as quickly as possible.

The Numerical Recipes section on "Arithmetic at Arbitrary Precision" describes the general aspects of quite nicely, although their implementation sucks.

Some languages have intrinsic math libraries that support multiword arithmetic (e.g. Java has a bigint type, if I recall correctly), and of course any metalanguage like Mathematica will have decent support for such stuff. Again, these are nice and general implementations, which are not however suitable for specific types of primality tests because they are much slower than a highly tuned hand-rolled implementation, especially when one is dealing with a special kind of modulus (as with Mersennes) that permits certain additional arithmetic speedups.

[dsouza123]

One way is to simulate a large integer is to use an array of integers
and write routines to do the operations such as addition, multiplication etc.

num_type = array[0..63] of word;  // 1024 bit number

a : num_type;
b : num_type;
c : num_type;
k : word;
t : dword;

// Addition routine to add two 1024 bit unsigned integers
// place the result in a third 1024 bit integer.
// Doesn't address overflow if the result exceeds 1024 bits.
k := 0;
for i := 0 to 63 do begin
  t := a[i] + b[i] + k;
  if t > word_max then begin
    c[i] := t and word_max;     // c[i] := t mod (word_max+1);
    k := 1;      // k := t div (word_max+1);
   end
  else begin
    c[i] := t;
    k := 0;
  end;
end;

Prime95 does some of the calculations, Lucas-Lehmer, using a form of FFT (Fast Fourier Transforms) called DWT using large numbers of blocks of floating point values with routines to detect and compensate for rounding
issues.

[CRGreathouse]

The problem isn't being able to deal with large numbers -- thousands of programs can do this, and it wouldn't be hard to write yet another -- but to deal with them efficiently. The standard, obvious methods take too long at those sizes.

[bandguyz24]

the best way to handle huge integers is with a string....


i am a java programmer and i use the object BigInteger to handle huge numbers

[cheesehead]

Originally Posted by bandguyz24

the best way to handle huge integers is with a string....

What kind of string, composed of what elements?

i am a java programmer and i use the object BigInteger to handle huge numbers

What is the upper limit on size of BigInteger objects?

[ewmayer]

Originally Posted by bandguyz24

the best way to handle huge integers is with a string....

Maybe if you're mainly interested in printing a poster of the current world-record Mersenne, and don't give a hoot about speed of arithmetic manipulations of the number(s).

i am a java programmer and i use the object BigInteger to handle huge numbers

So it should trivial to write your own Mersenne-testing program, and let us know how the per-iteration speed for a 10Mdigit modulus compares to that of Prime95 running on the same hardware. Once you've done that, we can revisit your "best" claim. Here, I'll even start you off with the single line of C-style pseudocode that is needed - here p is the integer Mersenne exponent, m = 2^p-1is the resulting modulus, and "bigInt" is shorthand for [language-supported big-integer data type], in your case the Java BigInteger type:

for(int i = 0, bigInt x = 4, bigInt m = ((bigInt)1 << p)-1; i < 100; ++i, x = (x*x)%m)

That should allow you to get some 100-iteration timings. For a full LL test you replace the upper loop-index limit with p-2, but I suggest holding off on that for p > 100000, until you have some idea of how the timing behavior scales for large p.

[Aexoden]

Originally Posted by bandguyz24

the best way to handle huge integers is with a string....

And that's exactly how I did it in mIRC's built-in scripting language (since it really has no data types other than strings and hash tables, that's pretty much all that's available).

To make it even more interesting, I went ahead and implemented a version of the Karatsuba algorithm so I could multiply some arbitrarily-long integers. Of course, since mIRC has no recursion ability, I had to (slowly) simulate it using a mIRC hash table as a stack. In the end, it was still faster to do the naïve multiplication algorithm, because it didn't have nearly as much overhead.

I can only shudder to think how slow large-exponent Lucas-Lehmer tests would be in that environment. It's a good thing no one's that insane.

[antlu]

bandguyz24, have u ever implemented your own arbitrary-precision routines? i cannot understand why you would use strings... and i assume you mean a string of characters. also, i've read that java's BigInt class uses the baseline multiplication algorithm, the one most of us were taught way back in the day. I'm not sure if you were trying to suggest that using java's BigInt was a good idea for performance, but from what I have read and understand, it would be an absolute disaster to attempt calculations of the scale needed for the larger mersenne primes with it. interpreted bytecode + quadratic complexity multiplication/squaring algorithm = god knows how long it would take to test a single exponent > 32 million. BigInt was probably meant for more tame applications.

On a different note, I am working on my own multiprecision class specifically for running Lucas-Lehmer test. I've implemented baseline, Comba-style, Karatsuba, and Toom-Cook 3-way squaring so far. Unfortunately, much of the papers regarding FFT multiplication are indecipherable to me (I have no knowledge of ring theory and number theory). If anyone has some sites or tutorials regarding FFT multiplication, I would be very grateful. I still do not even know the distinction between the Schonhage-Strassen algorithm and other FFTs. I realize that if I am to have any hope of testing the multi-million exponents, I will need to implement an FFT squaring routine. Perhaps I will try implementing additional Toom-Cook splits, but as I understand it (and correct me if I am wrong), Schonhage-Strassen's O(n log n loglog n) is still asymptotically superior to any number of splittings by Toom-Cook.

I use arrays of 32-bit integers (I actually only use 28 bits to store the value, additional bits are for carries in addition/subtraction, as well as allowing the Comba routine to work with larger operands), and try to minimize my memory allocs/deallocs since I already know the largest size my Lucas-Lehmer sequence number can ever be during a test (twice the length of the Mersenne number being tested).

That's just incase anyone's interested or has suggestions for me, wants suggestions, whatever.

[antlu]

i am not sure what you mean by a string being the best way of representing an arbitrary-precision integer, bandguyz24, but i assume you mean a string of characters, each being 1 byte. it sounds questionable to me when you could just as easily use an array of 32-bit integers.

as for java and its BigInt class, that must be a sure recipe for disaster when applied to testing multi-million mersenne exponents, as ewmayer suggests. i have read that BigInt only uses a baseline multiplication algorithm (the kind most of us are taught in school). it would take an exorbitant amount of time to perform even a single iteration of the millions you would need to test a single exponent. you will forgive me if I have the impression that you have never tried to implement your own arbitrary-precision arithmetic class.

ewmayer, are you familiar with implementing FFT multiplications? I do not know the difference between the variants, but I am under the impression (perhaps a wrong one) that the Schonhage Strassen exhibits the best asymptotic performance. I do not know if the new Furer algorithm discovered as of 2007 is also considered FFT. if you have any experience with these, i would be glad to learn what i can in the way of theory and implementation. my experience thus far involves baseline, Comba-style, Karatsuba, and Toom-3 multiplication algorithms.

[antlu]

sorry.. doubleposted. i didnt realize that posts had to be approved by a moderator and i thought my first one had simply not worked.