How do computers evaluate huge numbers?
data-structures, math
Solution
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)
Problem
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?