 mersenneforum.org Calculating large numbers
 Register FAQ Search Today's Posts Mark Forums Read 2010-03-26, 04:21 #1 Historian   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^1000000-1.   2010-03-26, 05:50 #2 S485122   Sep 2006 Brussels, Belgium 32068 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 2010-03-26 at 05:58 Reason: removed a hyphen and added another link   2010-03-26, 07:42 #3 cheesehead   "Richard B. Woods" Aug 2002 Wisconsin USA 22×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 multi-digit 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 three-digit 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 (three-digit maximum 999, plus 1) to separate it into three-digit groups. 392871 / 1000 = 392 with remainder of 871 => "392 871". Now that each group represents 0-32767, to break 392871 into short-integer groups, we divide by 32768 (short-integer maximum 32767, plus 1) to separate it into short-integer 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^1000000-1 can be converted to short-integer groups, too. But since that would require ... um ... thousands of short-integer groups, let's reduce the example to 123*2^50-1 = 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^50-1 can be represented by short-integer 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 short-integer 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 short-integer groups will all contain "0" at that point. Borrowing 1 from the, say, leftmost short-integer 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 2010-03-26 at 08:19   2010-03-26, 13:33   #4
R.D. Silverman

Nov 2003

1D2416 Posts Quote:
 Originally Posted by Historian 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^1000000-1.
Read D. Knuth, The Art of Computer Programming, Vol II.

As to how large numbers are stored: Think "arrays"   2010-03-26, 19:39 #5 Historian   Mar 2010 43 Posts Thanks for the help guys.  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Merfighters Miscellaneous Math 2 2010-10-29 16:51 SQUARE Information & Answers 7 2009-05-10 09:13 Mini-Geek Programming 10 2008-07-31 17:04 Elhueno Homework Help 5 2008-06-12 16:37 Bundu Software 5 2004-08-26 01:56

All times are UTC. The time now is 04:35.

Mon May 17 04:35:25 UTC 2021 up 38 days, 23:16, 0 users, load averages: 1.68, 2.30, 2.65