mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2010-03-26, 04:21   #1
Historian
 
Historian's Avatar
 
Mar 2010

43 Posts
Default 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.
Historian is offline   Reply With Quote
Old 2010-03-26, 05:50   #2
S485122
 
S485122's Avatar
 
Sep 2006
Brussels, Belgium

3·19·29 Posts
Default

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
S485122 is offline   Reply With Quote
Old 2010-03-26, 07:42   #3
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

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
cheesehead is offline   Reply With Quote
Old 2010-03-26, 13:33   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by Historian View Post
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"
R.D. Silverman is offline   Reply With Quote
Old 2010-03-26, 19:39   #5
Historian
 
Historian's Avatar
 
Mar 2010

1010112 Posts
Default

Thanks for the help guys.
Historian is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Discussion of Large Numbers Merfighters Miscellaneous Math 2 2010-10-29 16:51
Squaring large Numbers SQUARE Information & Answers 7 2009-05-10 09:13
extremely large numbers Mini-Geek Programming 10 2008-07-31 17:04
Calculating perfect numbers in Pascal Elhueno Homework Help 5 2008-06-12 16:37
How do I get LARGE numbers Bundu Software 5 2004-08-26 01:56

All times are UTC. The time now is 23:05.

Mon Mar 8 23:05:20 UTC 2021 up 95 days, 19:16, 0 users, load averages: 1.60, 1.57, 1.61

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.