I'm trying to understand the intuitions behind working with very large numbers. Specifically, I'm talking about numbers of the form $a^b$ where $a > 10,000$ and $b > 10,000$, and in general $a$ and $b$ are small, but $a^b$ has millions of digits. Obviously, computing the number is infeasible, but I still would like to determine things about them.
I am particularly interested in ideas or rules about evaluating which of two large numbers is larger. I believe I want to use logarithms somehow, but they've always confused me a little bit, so I can't quite see where to go from there.
More generally, I'd love to hear more generic discussion of how one can work with such large numbers easily, sacrificing precision, but not accuracy.
Answer
Since logarithms are monotonically increasing, you can determine if $$a^b > c^d$$ by instead checking if $$\log(a^b) > \log(c^d)$$ which can be rewritten (using basic properties of logarithms) as $$b\log(a) > d\log(c)$$ This results in the comparison of two numbers on the order of those given in the input (that is, both numbers will be within an order of magnitude or so of $a,b,c,d$), which is definitely feasible on a computer.
You can also use logs to calculate other properties, as long as you remember to convert your solution back to the original numbers (by means of an exponential) when you're done. For example, to compute whether $${a_1}^{b_1}{a_2}^{b_2} > {c_1}^{d_1}{c_2}^{d_2}$$, you can take the log of both sides to get
\begin{align}
\log({a_1}^{b_1}{a_2}^{b_2}) &> \log({c_1}^{d_1}{c_2}^{d_2}) \\
\log({a_1}^{b_1}) + \log({a_2}^{b_2}) &> \log({c_1}^{d_1}) + log({c_2}^{d_2}) \\
b_1\log(a_1) + b_2\log(a_2) &> d_1\log(c_1) + d_2\log(c_2) \\
\end{align}
which is again computationally feasible.
No comments:
Post a Comment