20100326, 04:21  #1 
Mar 2010
43 Posts 
Calculating large numbers
I haven't taken many computer science classes, so could someone explain how GIMPS and other prime searching products store and sieve such large numbers?
Long ago, I remember reading somewhere that a short int only goes from 32768 to +32768, long int goes from 2^31 to 2^31, and even double precision float for positive numbers only goes from 10^308 to 10^308. I think this was using C++, but I'm guessing other programming languages also don't have limits that are high enough to accomodate a number such as 12345*2^10000001. 
20100326, 05:50  #2 
Sep 2006
Brussels, Belgium
3206_{8} Posts 
You could start by looking at the explanations on the PrimeNet page The Maths, there are some links there if you want more explanation. Otherwise a search on Internet of "Arbitrary precision arithmetic" will return many links (Wikipedia, Wolfram MathWorld...) One interesting link is Arbitrary precision computation.
Jacob Last fiddled with by S485122 on 20100326 at 05:58 Reason: removed a hyphen and added another link 
20100326, 07:42  #3 
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 
Historian,
Here's some extra detail for Jacob's answer. Perhaps reading this before going to Arbitrary precision computation will help. It's possible to store large numbers as a series of smaller numbers. E.g., the number 283 can be stored as a 2, an 8 and a 3. Then, one can perform calculations using only the smaller numbers, while being careful to retain the proper relationship between the small numbers and the large number they represent. In fact, this is really how we all learn to do arithmetic with decimal numbers. To add 515 to 283, we don't work with either number in its entirety in one swoop, but instead focus on just single digits at a time, while keeping them in their proper order to represent the larger entire numbers. Add the rightmost digits: 5 + 3 = 8, so put 8 in the rightmost place of the multidigit answer. Add the next digits to the left: 1 + 8 = 9, placed in the next digit to the left of the answer. Then add 5 + 2 = 7 to get the leftmost digit of the answer, which is revealed to be 798. Notice that we never had to add together any number longer than one digit at a time. That example didn't require any carries. For 292 + 488, we have to "carry" when we add the rightmost digits, then again when we add the middle digits (plus the carry from the right). 2 + 8 = 0, and carry 1. 9 + 8 + carry 1 = 8, and carry 1. 2 + 4 + carry 1 = 7. Answer = 780. Now, extend this to operating on three digits at a time. (Yes, we'll do a single digit at a time within each threedigit group, but let's just assume that without explicitly writing it.) Add 392871 + 206318 = 392 871 + 206 318. 871 + 318 = 189, and carry 1. 392 + 206 + carry 1 = 599. Answer = 599 189 = 599189. Now ... here's the big leap ... suppose instead of groups of three digits, we represent each large number by groups of C++ short integers (which go from 32768 to +32767, not +32768). For simplicity, we'll use only positive numbers, so each group can be from 0 to 32767. When the groups were three digits, we divided 392871 by 1000 (threedigit maximum 999, plus 1) to separate it into threedigit groups. 392871 / 1000 = 392 with remainder of 871 => "392 871". Now that each group represents 032767, to break 392871 into shortinteger groups, we divide by 32768 (shortinteger maximum 32767, plus 1) to separate it into shortinteger groups. 392871 / 32768 = 11 with remainder of 32423. So we'll represent 392871 by "11 32423". Similarly, 206318 becomes "6 9710". "11 32423" + "6 9710": Add "32423" and "9710" to get "9365" + carry of "1" to left. (32423 + 9710 = 42133. 42133 / 32768 = 1 with remainder of 9365.) Then add "11" + "6" + carry "1" to get "18". So, answer = "18 9365". Convert back to decimal: (18 * 32768) + 9365 = 589824 + 9365 = 599189. So, we can represent large numbers by using groups of short integers ... or groups of (regular) integers ... or groups of long integers ... or groups of long long integers. (Actually, I should've just looked for a web page that already explained that.) Now go read Arbitrary precision computation.    12345*2^10000001 can be converted to shortinteger groups, too. But since that would require ... um ... thousands of shortinteger groups, let's reduce the example to 123*2^501 = 138485688541642751 138485688541642751 / 32768 = 4226247819263 with remainder of 32767 4226247819263 / 32768 = 128974847 with remainder of 32767 128974847 / 32768 = 3935 with remainder of 32767. So, 123*2^501 can be represented by shortinteger groups as "3935 32767 32767 32767" Yes, there's a reason for all those 32767s. You can figure it out, based on the form of the original number. Start by converting 2^50 to shortinteger groups, then look at the patterns when you multiply by 123, and then when you subtract 1. That subtraction will require some "borrowing" because the three right shortinteger groups will all contain "0" at that point. Borrowing 1 from the, say, leftmost shortinteger group gives you a 32768 for the group to its right. Borrowing 1 from that will leave a 32767 in the second group and give a 32768 for the third group. Borrowing 1 from the third group will leave a 32767 in the third group and give a 32768 for the rightmost group. Then, finally, you can subtract the 1 that you started out wanting to subtract from the rightmost group, giving you 32767 in that group.) Last fiddled with by cheesehead on 20100326 at 08:19 
20100326, 13:33  #4  
Nov 2003
1D24_{16} Posts 
Quote:
As to how large numbers are stored: Think "arrays" 

20100326, 19:39  #5 
Mar 2010
43 Posts 
Thanks for the help guys.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Discussion of Large Numbers  Merfighters  Miscellaneous Math  2  20101029 16:51 
Squaring large Numbers  SQUARE  Information & Answers  7  20090510 09:13 
extremely large numbers  MiniGeek  Programming  10  20080731 17:04 
Calculating perfect numbers in Pascal  Elhueno  Homework Help  5  20080612 16:37 
How do I get LARGE numbers  Bundu  Software  5  20040826 01:56 