20070213, 22:09  #1 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17×251 Posts 
extremely large numbers
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.

20070214, 00:34  #2 
∂^{2}ω=0
Sep 2002
República de California
7·11·151 Posts 
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 base2^{32} 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 handrolled implementation, especially when one is dealing with a special kind of modulus (as with Mersennes) that permits certain additional arithmetic speedups. Last fiddled with by ewmayer on 20070214 at 00:35 
20070214, 01:37  #3 
Sep 2002
2·331 Posts 
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. Code:
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; issues. Last fiddled with by dsouza123 on 20070214 at 01:41 
20080323, 23:42  #4 
Aug 2006
3^{2}·5·7·19 Posts 
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.

20080710, 09:50  #5 
Jul 2008
3 Posts 
programmming with an extra m for math
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 
20080712, 21:27  #6  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
What kind of string, composed of what elements?
Quote:
Last fiddled with by cheesehead on 20080712 at 21:39 

20080715, 18:07  #7  
∂^{2}ω=0
Sep 2002
República de California
7×11×151 Posts 
Maybe if you're mainly interested in printing a poster of the current worldrecord Mersenne, and don't give a hoot about speed of arithmetic manipulations of the number(s).
Quote:
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 100iteration timings. For a full LL test you replace the upper loopindex limit with p2, but I suggest holding off on that for p > 100000, until you have some idea of how the timing behavior scales for large p. Last fiddled with by ewmayer on 20080715 at 23:31 

20080716, 20:24  #8 
Jun 2008
Spokane, WA
6_{16} Posts 
And that's exactly how I did it in mIRC's builtin 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 arbitrarilylong 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 largeexponent LucasLehmer tests would be in that environment. It's a good thing no one's that insane. 
20080730, 00:40  #9 
Jul 2008
1101_{2} Posts 
string? why?
bandguyz24, have u ever implemented your own arbitraryprecision 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 LucasLehmer test. I've implemented baseline, Combastyle, Karatsuba, and ToomCook 3way 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 SchonhageStrassen algorithm and other FFTs. I realize that if I am to have any hope of testing the multimillion exponents, I will need to implement an FFT squaring routine. Perhaps I will try implementing additional ToomCook splits, but as I understand it (and correct me if I am wrong), SchonhageStrassen's O(n log n loglog n) is still asymptotically superior to any number of splittings by ToomCook. I use arrays of 32bit 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 LucasLehmer 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. 
20080730, 03:44  #10 
Jul 2008
13 Posts 
i am not sure what you mean by a string being the best way of representing an arbitraryprecision 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 32bit integers.
as for java and its BigInt class, that must be a sure recipe for disaster when applied to testing multimillion 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 arbitraryprecision 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, Combastyle, Karatsuba, and Toom3 multiplication algorithms. 
20080731, 17:04  #11 
Jul 2008
13 Posts 
sorry.. doubleposted. i didnt realize that posts had to be approved by a moderator and i thought my first one had simply not worked.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
GMPECM crashing for large numbers or high RAM use  lavalamp  Software  6  20110106 05:29 
Discussion of Large Numbers  Merfighters  Miscellaneous Math  2  20101029 16:51 
Calculating large numbers  Historian  Information & Answers  4  20100326 19:39 
Squaring large Numbers  SQUARE  Information & Answers  7  20090510 09:13 
How do I get LARGE numbers  Bundu  Software  5  20040826 01:56 