How to work with 100+digit numbers

[Edi]

I am studying programming for the first year so I don't have whole lot of experience. I am interested in how to work with super-large numbers, numbers that are much, much larger then the included Int or _int64. I mean some 100, 1000 .. 17 million (largest prime) digit numbers. How do they do that? I understand that my home pc has no chance at calculating some of the monster primes (unless I come up with a genius, simple way to find primes :tongue: ), but I might do some other manipulations with monster numbers. Cryptography and what not.
I figure one way might be to use an array (or a string) where each iteration is a single digit along with a custom made function to do maths digit by digit (kinda like on-paper multiplication)..
That might be one way, but then each element of the array would consume 4 bytes (2 if I define it as short int ) and I only need .. half a byte to represent a digit from 0 to 9.A lot of memory wasted. I might resolve that problem by working in a higher base (2 byte max value base) ..
Maybe, but how do professionals do it? Even ms calculator can do calculations with larger numbers...

 

[voko]

There are two basic approaches. One uses whatever machine instructions available on the given platform to perform arithmetic operations with "carry". Another emulates "carry" in software. For example, you can represent your big number using a sequence of 64 bit "limbs", and each limb uses only 63 bits to store data. When you add two limbs, you then check that the 64-th bit in the result is set or not. If set, that's your "carry" flag. The second approach is generally slower and uses more memory, but it is portable.

 

[jedishrfu]

Many languages like Python, Groovy and Java have support for large numbers:

http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic

 

[.Scott]

// Using voko's numbers (see post #2)
// Each input array specifies an integer with nWords*63 bits. The words are grouped in big endian form.
// Integer at pnB is added to the integer at pnA.
AddBigNums(int nWords, __int64 *pnA, const __int64 *pnB)
{
int n, nCarry;
__int64 nSum;

nCarry = 0;
for(n=0;n<nWords;n++) {
nSum = pnB[n] + pnA[n] +nCarry;
if(nSum<0) {
nSum &= 0x7FFFFFFFFFFFFFFF;
nCarry = 1;
} else {
nCarry = 0;
}
pnA[n] = nSum;
}

 

[voko]

.Scott, I would use unsigned arithmetic and shifts to get the carry bit. That eliminates conditional statements.

 

[.Scott]

.Scott, I would use unsigned arithmetic and shifts to get the carry bit. That eliminates conditional statements.

I was trying to be explicit. If I was actually implementing something, I would have created a "BigNumber" class; I would have used all 64 bits; and I would have used operator overloading for "+".

Actually, I would have search for some existing implementation of this class.

 

[Borek]

Actually, I would have search for some existing implementation of this class.

:thumbs:

 

[rcgldr]

I am interested in how to work with super-large numbers.

It's a complicated combination of algorithms like Karatsuba's binary splitting for doing large multiplies, and performing the math modulo some prime number (less than 32 bits or 64 bits depending on the word size), and FFT like methods. Example description from apfloat (a downloadable source code library for large number math):

http://www.apfloat.org/ntt.html

Another link: (look for the FFT stuff):

http://numbers.computation.free.fr/Constants/constants.html

These methods are overkill for 100 to 1000 digits, but for large numbers (1 million + digits) they are fast.

 

[SixNein]

Well if your want to look at a good existing library, GMP is probably the best. And it's written in C++.

just do a search for it in google.

 

[chiro]

If it is for non-commercial use, then MIRACL is a good library to use (it's free for non-commercial use).

I've used it in the past and it had good performance.

Other suggestions include looking at cryptography libraries which often contain big number libraries out of necessity.