15

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?

5 Answers 5

14

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

  1. 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...

  2. 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)

2
  • Excellent answer! I quite didn't get this part - A rem 10^5 = ((A rem 10^5)^B) rem 10^5. How is that explained?
    – Sundeep
    Jan 10, 2014 at 14:11
  • @Sundeep: It seems that there should be a line break: I've calculated (A rem 10^5) first and after that ((A^B) rem 10^5). I've edited the post. Jan 10, 2014 at 14:18
3

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).

4
  • So does this mean that there is no fancy shortcut to calculating massive exponentials? I assume Wolfram Alpha must have a huge distributed system used just for calculating large numbers?
    – Sam
    Aug 20, 2013 at 11:43
  • 1
    @Sam Yes and no. There are some shortcuts in some specific cases, but in general you have to do full multiplications, and Wolfram Alpha probably has large data centers for answering queries. But much of that will be doing something else than calculating large numbers, and your example, 1234567^98787878, only needs two dozen bignum multiplication, though it does result in ~ 150 megabyte if fully evaluated. A single computer can do this in reasonable time, the "huge distributed" part only enters the picture because it's thousands of people running such queries concurrently.
    – user395760
    Aug 20, 2013 at 11:58
  • the given algorithm is a fancy shortcut as it allows for reuse of interim results.
    – collapsar
    Aug 20, 2013 at 12:00
  • @collapsar It's a more efficient algorithm, but I wouldn't call it a shortcut. A shortcut would be, for example, something that takes OP's expression and gives you the last few digits without calculating the millions of other digits.
    – user395760
    Aug 20, 2013 at 12:02
3

To compute how many digits there are, one uses the following expression:

decimal_digits(n) = 1 + floor(log_10(n))

This gives:

decimal_digits(1234567^98787878) = 1 + floor(log_10(1234567^98787878))
                                 = 1 + floor(98787878 * log_10(1234567))
                                 = 1 + floor(98787878 * 6.0915146640862625)
                                 = 1 + floor(601767807.4709647)
                                 = 601767808

The trailing k digits are computed by doing exponentiation mod 10^k, which keeps the intermediate results from ever getting too large.

The approximation will be computed using a (software) floating-point implementation that effectively evaluates a^(98787878 log_a(1234567)) to some fixed precision for some number a that makes the arithmetic work out nicely (typically 2 or e or 10). This also avoids the need to actually work with millions of digits at any point.

0
1

There are many libraries for this and the capability is built-in in the case of python. You seem primarily concerned with the size of such numbers and the time it may take to do computations like the exponent in your example. So I'll explain a bit.

Representation You might use an array to hold all the digits of large numbers. A more efficient way would be to use an array of 32 bit unsigned integers and store "32 bit chunks" of the large number. You can think of these chunks as individual digits in a number system with 2^32 distinct digits or characters. I used an array of bytes to do this on an 8-bit Atari800 back in the day.

Doing math You can obviously add two such numbers by looping over all the digits and adding elements of one array to the other and keeping track of carries. Once you know how to add, you can write code to do "manual" multiplication by multiplying digits and putting the results in the right place and a lot of addition - but software will do all this fairly quickly. There are faster multiplication algorithms than the one you would use manually on paper as well. Paper multiplication is O(n^2) where other methods are O(n*log(n)). As for the exponent, you can of course multiply by the same number millions of times but each of those multiplications would be using the previously mentioned function for doing multiplication. There are faster ways to do exponentiation that require far fewer multiplies. For example you can compute x^16 by computing (((x^2)^2)^2)^2 which involves only 4 actual (large integer) multiplications.

In practice It's fun and educational to try writing these functions yourself, but in practice you will want to use an existing library that has been optimized and verified.

-1

I think a part of the answer is in the question itself :) To store these expressions, you can store the base (or mantissa), and exponent separately, like scientific notation goes. Extending to that, you cannot possibly evaluate the expression completely and store such large numbers, although, you can theoretically predict certain properties of the consequent expression. I will take you through each of the properties you talked about:

  1. Decimal approximation: Can be calculated by evaluating simple log values.
  2. Total number of digits for expression a^b, can be calculated by the formula Digits = floor function (1 + Log10(a^b)), where floor function is the closest integer smaller than the number. For e.g. the number of digits in 10^5 is 6.
  3. Last digits: These can be calculated by the virtue of the fact that the expression of linearly increasing exponents form a arithmetic progression. For e.g. at the units place; 7, 9, 3, 1 is repeated for exponents of 7^x. So, you can calculate that if x%4 is 0, the last digit is 1. Can someone create a custom datatype for large numbers, I can't say, but I am sure, the number won't be evaluated and stored.
2
  • Actually, these large integers can be stored (and usually are) as an integer form, using bignum libraries. There are many such tools.
    – user85109
    Aug 20, 2013 at 17:29
  • @woodchips - Yes, you are right, I overestimated the number. Precision libraries can hold only as much as the size of the largest buffer. And if one does the calculation using number of digits (and exponents of 2, which give that many number of digits), it requires ~40MB to store it.
    – Sahil M
    Aug 21, 2013 at 7:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.