How do computers evaluate huge numbers?
Well it's quite easy and you can have done it yourself
- 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
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...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)
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).