How do computers evaluate huge numbers?

Question

If I enter a value, for example 1234567^98787878 into Wolfram Alpha it can provide me with a number of details. This includes decimal approximation, total length, last digits etc. How do you evaluate such large numbers? As I understand it a programming language would have to have a special data type in order to store the number, let alone add it to something else. While I can see how one might approach the addition of two very large numbers, I can't see how huge numbers are evaluated.

10^2 could be calculated through repeated addition. However a number such as the example above would require a gigantic loop. Could someone explain how such large numbers are evaluated? Also, how could someone create a custom large datatype to support large numbers in C# for example?

Answer 1

Well it's quite easy and you can have done it yourself

1. Number of digits can be obtained via logarithm:

since `A^B = 10 ^ (B * log(A, 10))` 

we can compute (A = 1234567; B = 98787878) in our case that

 `B * log(A, 10) = 98787878 * log(1234567, 10) = 601767807.4709646...`

integer part + 1 (601767807 + 1 = 601767808) is the number of digits

2. First, say, five, digits can be gotten via logarithm as well; now we should analyze fractional part of the

   B * log(A, 10) = 98787878 * log(1234567, 10) = 601767807.4709646...

   f = 0.4709646...

   first digits are 10^f (decimal point removed) = 29577...

3. Last, say, five, digits can be obtained as a corresponding remainder:

   last five digits = A^B rem 10^5

   A rem 10^5 = 1234567 rem 10^5 = 34567

   A^B rem 10^5 = ((A rem 10^5)^B) rem 10^5 = (34567^98787878) rem 10^5 = 45009

   last five digits are 45009

   You may find BigInteger.ModPow (C#) very useful here

Finally

1234567^98787878 = 29577...45009 (601767808 digits)

Answer 2

There are usually libraries providing a bignum datatype for arbitrarily large integers (eg. mapping digits k*n...(k+1)*n-1, k=0..<some m depending on n and number magnitude> to a machine word of size n redefining arithmetic operations). for c#, you might be interested in BigInteger.

exponentiation can be recursively broken down:

pow(a,2*b)   = pow(a,b) * pow(a,b);
pow(a,2*b+1) = pow(a,b) * pow(a,b) * a;

there also are number-theoretic results that have engenedered special algorithms to determine properties of large numbers without actually computing them (to be precise: their full decimal expansion).