11
$\begingroup$

Let's say that $n$ and $m$ are two very large natural numbers, both expressed as product of prime factors, for example:

$n = 3×5×43×367×4931×629281$

$m = 8219×138107×647099$

Now I'd like to know which is smaller. Unfortunately, all I have is an old pocket calculator that can show at most (say) ten digits. So while there are enough digits to enter each factor individually, $n$ and $m$ are both too large to fit in the calculator. To my disappoint, they are also so close that even their logarithms are indistinguishable looking at the first 10 digits.

Question: how would one go to determine which one of two integers is smaller in a case like this? Any easier alternative than calculating the full decimal expansion of both products with pen and paper?

$\endgroup$
  • 1
    $\begingroup$ Is this meant to be a theoretical question? If you just want the answer, you could use an online calculator (Wolfram|Alpha, for example) with greater precision. $\endgroup$ – John Gowers Dec 27 '14 at 1:45
  • $\begingroup$ @Donkey_2009 this does make for an interesting question (using access to only 10 digits) what is the most efficient way to compare the any two numbers? $\endgroup$ – frogeyedpeas Dec 27 '14 at 1:46
  • 1
    $\begingroup$ You can determine if $m/n > 1$ or $m/n < 1$ by working with a few factors at a time. E.g., compute 3*5*43*367/8219, then multiply by 4931, then divide by 138107, then multiply by 629281, then divide by 647099. $\endgroup$ – Kimball Dec 27 '14 at 1:54
  • 1
    $\begingroup$ @Kimball $m/n=1.0000000000000027228555049\dots$, which is indistinguishable from $1$ up to $10$ decimal places. How can we tell whether it's greater to or less than $1$? $\endgroup$ – John Gowers Dec 27 '14 at 1:58
  • $\begingroup$ @Donkey_2009 ah, well, I didn't actually try this out, but since the ratio is distinguishable from 1 looking up to 20 digits, possibly one can just compare 2 partial ratios. $\endgroup$ – Kimball Dec 27 '14 at 4:01
14
$\begingroup$

If you can prove that the two numbers are fairly close, then you could use modular arithmetic.

For example, we know that the two numbers are indistinguishable by looking at only $10$ digits. Specifically, we can work out: $$ n/10000=\frac1{10000}\times3×5×43×367×4931×629281=7345230022\\ m/10000=\frac1{10000}\times8219×138107×647099=7345230022 $$ (both correct to $10$ significant figures). This means that $m$ and $n$ differ by less than $10000$. Working modulo $10000$: $$ 3\times5\times43\times367=236715\equiv-3285\\ -3285\times4931=-16198335\equiv1665\\ 629281\equiv-719\\ 1665\times-719=-1197135\equiv2865 $$ Therefore: $$ n\equiv2865\mod10000 $$ Now: $$ 8219\equiv-1781\\ 138107\equiv-1893\\ 647099\equiv-2901\\ -1781\times-1893=3371433\equiv1433\\ 1433\times-2901=-4157133\equiv2867 $$ Therefore: $$ m\equiv2867\mod10000 $$ Now we've worked out the last four digits of $m$ and $n$. Since we know that $m$ and $n$ differ by less than $10000$, we must have that $m>n$.

Update: As Paŭlo points out, it isn't enough just to know that $n$ and $m$ differ by less than $10000$ and that $n\equiv2865,m\equiv2867$. For example, $12865$ and $2867$ differ by less than $10000$ and satisfy the same congruences, yet $12865>2867$. In this case, however, our calculations are enough to give us the answer. From our first calculation, we know that:

$$ 73452300215000\le m,n\le73452300225000 $$ This, coupled with the facts that $n\equiv2865,m\equiv2867\mod10000$, is enough to tell us that $m>n$.

$\endgroup$
  • $\begingroup$ there is something wrong there, because $m$ is bigger than $n$. $\endgroup$ – Integral Dec 27 '14 at 2:57
  • $\begingroup$ @Integral corrected! $\endgroup$ – John Gowers Dec 27 '14 at 3:06
  • $\begingroup$ Hmm, I'm not sure that the order doesn't get lost in general when working $\mod 10000$. I guess one should use a modulus quite larger (at least a factor two) than the established maximal difference to be sure. $\endgroup$ – Paŭlo Ebermann Dec 27 '14 at 10:15
  • $\begingroup$ @PaŭloEbermann I think we're OK here, though the same thought occurred to me too. Another way o thinking about it is: $m$ and $n$ both have $15$ digits; we can check that the first $10$ digits of each are the same; then modular arithmetic tells us the last $5$ digits of each, which shows that $m>n$. $\endgroup$ – John Gowers Dec 27 '14 at 10:41
0
$\begingroup$

Scientific notation maybe very useful for analysis here.

Notice how for n we have an order of $3 \cdot 5 \cdot 4.3 \times10^1 \cdot 3.7 \times10^2 \cdot 4.9 \times 10^3 \cdot 6.3 \times10^5$

By the properties of exponents and multiplication you know this has a magnitude of at least $10^{11}$ by just adding up the exponents of the tens.

Similarly for m we get a magnitude of at least $10^{13}$ via the same method.

Without using a calculator or multiplying the digits we already get the implication that the m is larger.

However in the interest of precision: multiplying the digits show that both quantities have the exponential magnitude of $10^{14}$, yet the digits of n multiply to roughly 7.4 (after rounding) and the digits of m multiply roughly to 7.5 (after rounding) so the second is probably larger.

Feel free to use as many significant figures for more accuracy.

$\endgroup$
  • 2
    $\begingroup$ You might be interested in working out the exact values of $m$ and $n$ - they differ by only $2$, yet are $15$ digits long, so nothing like this is going to work. $\endgroup$ – John Gowers Dec 27 '14 at 2:31
0
$\begingroup$

Your pocket calculator can work with the factors of $n$ and $m$, in this case, let $n = n_1\cdot n_2\cdot\ldots n_r$ and $m = m_1\cdot m_2\cdot\ldots m_s$, now calculates $\log(n) = \log(n_1) + \log(n_2) + \ldots + \log(n_r)$ and $\log(m) = \log(m_1) + \log(m_2) + \ldots + \log(m_s)$. This calculations are pretty possible if their factors aren't huge.

Note that $n > m \iff \log(n/ m) > 0$, and $n<m \iff \log(n/ m) < 0$. Therefore all you need to do is check the sign of $\log(n/m)$.

You have that $\log(n/ m) = \log(n_1) + \ldots + \log(n_r) - \log(m_1) - \ldots - \log(m_s)$, so you can expect to do this test to really large (but not arbitrarily large) numbers.

$\textbf{Edit}$: I just realize that $\log(n/ m) = -0.0000000000000027\ldots$ in your example, so maybe this test is not good enough. But the problem are not the zeros (which are more then 10), the problem is if your pocket calculator will return the minus sign or not. Because an output like $-0.0000000000$ would be enough to know which one is bigger.

$\endgroup$
  • $\begingroup$ If you read the question carefully, it says, 'To my disappoint, they are also so close that even their logarithms are indistinguishable looking at the first 10 digits.' This is something the OP already tried, and found didn't work. $\endgroup$ – John Gowers Dec 27 '14 at 10:44
  • $\begingroup$ If you read carefully my answer, the "edit" part, I said the same thing and pointed out that the digits are not important, the sign is important. Maybe he wasn't aware of that fact, which is relevant. $\endgroup$ – Integral Dec 27 '14 at 16:48
0
$\begingroup$

As a practical example, in a programming language like C or C++, you can easily calculate both products using floating-point arithmetic, and you can easily calculate both products modulo 2^64 using unsigned integer arithmetic.

If you can estimate the rounding error in the floating-point arithmetic products, and prove that the total rounding error is less than 2^63, then it's easy: Calculate the difference d between the products in floating-point arithmetic. If the difference is >= 2^63 or <= -2^63 then that decides. Otherwise, you know that the exact difference is greater than $d - 2^63$ and less than $d + 2^63$. We also know the exact difference modulo 2^64; this is enough to determine the exact difference. This should work for numbers up to 33 or 34 digits.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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