68
$\begingroup$

What is the fastest way to check if $x^y > y^x$ if I were writing a computer program to do that?

The issue is that $x$ and $y$ can be very large.

$\endgroup$
  • 8
    $\begingroup$ You can test if $\ln(y) + \ln \big( \ln(x) \big) > \ln(x) + \ln \big( \ln(y) \big)$. $\endgroup$ – jibounet Oct 7 '13 at 10:39
  • 4
    $\begingroup$ You want fast or robustly correct? $\endgroup$ – lhf Oct 7 '13 at 10:40
  • $\begingroup$ @lhf, Fast and in checking among n such pairs of numbers, n/10 could go wrong. Could you please help me deduce what accuracy I'm looking for? $\endgroup$ – learner Oct 7 '13 at 10:44
  • 12
    $\begingroup$ Are you doing http://projecteuler.net/problem=99? $\endgroup$ – Mårten W Oct 7 '13 at 10:50
  • 2
    $\begingroup$ @MårtenW: His problem is more specific. The link you posted is about x^a < y^b. He is considers the special case a=y, b=x $\endgroup$ – Christian Fries Oct 7 '13 at 12:14
89
$\begingroup$

If both $x$ and $y$ are positive then you can just check: $$ \frac{\log(x)}{x} \gt \frac{\log(y)}{y}$$ so if both $x$ and $y$ are greater than $e \approx 2.7183$ then you can just check: $$x \lt y$$

$\endgroup$
  • $\begingroup$ But how x < y? How can we omit the logs? Intuitively it seems right, but is it really so? $\endgroup$ – learner Oct 7 '13 at 11:18
  • 23
    $\begingroup$ @learner, the point is that the function $log(x)/x$ has a single maximum at $x=e$ and is decreasing after that. $\endgroup$ – lhf Oct 7 '13 at 11:19
  • 1
    $\begingroup$ I don't know why this answer is the accepted one, but multiplication is usually faster than division, so I assume $y log(x) > x log(y)$ is faster than this one. $\endgroup$ – Christian Fries Oct 7 '13 at 12:15
  • 20
    $\begingroup$ @ChristianFries, this answer is the accepted one because of the massive optimization given in the second half of the answer. Even if you don't use the monotonicity of $\frac{\log{x}}{x}$, the fact that it's a single function can make repeated queries much faster. $\endgroup$ – jwg Oct 7 '13 at 12:29
  • 2
    $\begingroup$ If $x$ and $y$ are both between $0$ and $e$ then the test becomes $x \gt y$. The hard part is when one is below and one above: for example $2^4 = 4^2$ and $\frac{\log 2}{2} = \frac{\log 4}{4}$ $\endgroup$ – Henry Oct 7 '13 at 17:16
23
$\begingroup$

You might get by testing whether $y \log x > x \log y$, especially if the numbers are only moderately large.

$\endgroup$
0
$\begingroup$

We reduce the question to: is the quotient (x^y) / (y^x) less or greater than 1.

· Noticing that x > 0, y > 0, we take the xy-th root of the quotient:

is the ratio (x^y)^(1/xy) / (y^x)^(1/xy) less or greater than 1^(1/xy).

We reduce the complicated powers, the power of base 1 is 1:

is the ratio x^(1/x) / y^(1/y) less or greater than 1.

is the function f(x) = x^(1/x) increasing or decreasing at the interval [x,y]?

· If already known, via the derivate, that the function f(x) = x^(1/x) has only one maximum, so an absolute maximum for x = e , the point (e, e^(1/e)),

Consider that a) for x > e and y > e , the function f is decreasing, which means

• if e < x < y => f(x) > f(y). [both x and y are greater than e, the greater exponent wins.]

and b) for x < e and y < e the function f is increasing, which means

• if 0 < x < y < e => f(x) < f(y). [both x and y are less than e, the greater base wins.]

• But if x < e < y, the comparison is not decided through the function’s behaviour. [e is between both.] We have to calculate both powers to compare the outcomes.

So there are pairs of x,y existing for which (x^y) = (y^x), with x < e < y.

For example, x = √(√5) and y = √(√(5^5)) = √(√3125)
both x^y and y^x come out on ≈ 20,25372598…

Many pairs are findable, e.g. by setting y = a·x and resolving the equation (x^y) = (y^x), or

f(x) = f(y).

New contributor
kees canal fp is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\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.