87
$\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$
10
  • 8
    $\begingroup$ You can test if $\ln(y) + \ln \big( \ln(x) \big) > \ln(x) + \ln \big( \ln(y) \big)$. $\endgroup$
    – pitchounet
    Commented Oct 7, 2013 at 10:39
  • 4
    $\begingroup$ You want fast or robustly correct? $\endgroup$
    – lhf
    Commented Oct 7, 2013 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
    Commented Oct 7, 2013 at 10:44
  • 12
    $\begingroup$ Are you doing http://projecteuler.net/problem=99? $\endgroup$
    – Mårten W
    Commented Oct 7, 2013 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
    Commented Oct 7, 2013 at 12:14

4 Answers 4

Reset to default
114
$\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$
11
  • 33
    $\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
    Commented Oct 7, 2013 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
    Commented Oct 7, 2013 at 12:15
  • 26
    $\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
    Commented Oct 7, 2013 at 12:29
  • 7
    $\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
    Commented Oct 7, 2013 at 17:16
  • 1
    $\begingroup$ @Henry: Sorry for hijacking this comment thread (I will delete this comment in a moment), but I have a question to Henry: I noticed that you just removed your answer to my question on integer division. Was the answer wrong? $\endgroup$
    – Sid
    Commented Dec 20, 2016 at 12:31
26
$\begingroup$

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

$\endgroup$
9
$\begingroup$

We reduce the question to: is the quotient $\frac{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)^{\frac1{xy}} / (y^x)^{\frac1{xy}}$ less or greater than $1^{\frac1{xy}}$.

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

is the ratio $x^{\frac1x} / y^{\frac1y}$ less or greater than 1.

is the function $f(x) = x^{\frac1x}$ increasing or decreasing at the interval $[x,y]$?

· If already known, via the derivate, that the function $f(x) = x^{\frac1x}$ has only one maximum, so an absolute maximum for $x = e$ , the point $(e, e^{\frac1e})$,

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

$\endgroup$
1
0
$\begingroup$

The equation $x^y=y^x$ has solution along the bisector $y=x$ and along a curve symmetric with respect to the bisector. In the following image the gray region is where $x^y > y^x$

enter image description here

A parametric representation of the curve is $(e^{f(t)},e^{f(-t)})$ where $$ f(t) = \frac{t}{e^t-1} $$

A curve very similar to that is the equilateral hyperbola $$ (x-1)(y-1) = (e-1)^2 $$ and here there is a graphical comparison between the two curves

enter image description here

So a possible test with very low error is, assuming $x < y$ $$ (x-1)(y-1) > (e-1)^2 \quad \Leftrightarrow \quad x^y > y^x $$

As an empirical measure of the error, over a million random samples in the range $0<x<y<2e$ the rate of errors is below 0.3%.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .