mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2007-02-13, 22:09   #1
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default 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.
Mini-Geek is offline   Reply With Quote
Old 2007-02-14, 00:34   #2
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

7·11·151 Posts
Default

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

Last fiddled with by ewmayer on 2007-02-14 at 00:35
ewmayer is offline   Reply With Quote
Old 2007-02-14, 01:37   #3
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2·331 Posts
Default

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

Last fiddled with by dsouza123 on 2007-02-14 at 01:41
dsouza123 is offline   Reply With Quote
Old 2008-03-23, 23:42   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32·5·7·19 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Old 2008-07-10, 09:50   #5
bandguyz24
 
Jul 2008

3 Posts
Default 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
bandguyz24 is offline   Reply With Quote
Old 2008-07-12, 21:27   #6
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

Quote:
Originally Posted by bandguyz24 View Post
the best way to handle huge integers is with a string....
What kind of string, composed of what elements?

Quote:
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?

Last fiddled with by cheesehead on 2008-07-12 at 21:39
cheesehead is offline   Reply With Quote
Old 2008-07-15, 18:07   #7
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

7×11×151 Posts
Default

Quote:
Originally Posted by bandguyz24 View Post
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).
Quote:
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 = 2p-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.

Last fiddled with by ewmayer on 2008-07-15 at 23:31
ewmayer is offline   Reply With Quote
Old 2008-07-16, 20:24   #8
Aexoden
 
Jun 2008
Spokane, WA

616 Posts
Default

Quote:
Originally Posted by bandguyz24 View Post
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.
Aexoden is offline   Reply With Quote
Old 2008-07-30, 00:40   #9
antlu
 
antlu's Avatar
 
Jul 2008

11012 Posts
Default string? why?

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 is offline   Reply With Quote
Old 2008-07-30, 03:44   #10
antlu
 
antlu's Avatar
 
Jul 2008

13 Posts
Default

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 is offline   Reply With Quote
Old 2008-07-31, 17:04   #11
antlu
 
antlu's Avatar
 
Jul 2008

13 Posts
Default

sorry.. doubleposted. i didnt realize that posts had to be approved by a moderator and i thought my first one had simply not worked.
antlu is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
GMP-ECM crashing for large numbers or high RAM use lavalamp Software 6 2011-01-06 05:29
Discussion of Large Numbers Merfighters Miscellaneous Math 2 2010-10-29 16:51
Calculating large numbers Historian Information & Answers 4 2010-03-26 19:39
Squaring large Numbers SQUARE Information & Answers 7 2009-05-10 09:13
How do I get LARGE numbers Bundu Software 5 2004-08-26 01:56

All times are UTC. The time now is 10:31.

Fri May 7 10:31:54 UTC 2021 up 29 days, 5:12, 0 users, load averages: 3.20, 3.05, 3.05

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.