Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
7  
You can test if $\ln(y) + \ln \big( \ln(x) \big) > \ln(x) + \ln \big( \ln(y) \big)$. –  jibounet Oct 7 '13 at 10:39
3  
You want fast or robustly correct? –  lhf Oct 7 '13 at 10:40
    
@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? –  learner Oct 7 '13 at 10:44
10  
Are you doing http://projecteuler.net/problem=99? –  Mårten W Oct 7 '13 at 10:50
2  
@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 –  Christian Fries Oct 7 '13 at 12:14

2 Answers 2

up vote 56 down vote accepted

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$$

share|improve this answer
    
But how x < y? How can we omit the logs? Intuitively it seems right, but is it really so? –  learner Oct 7 '13 at 11:18
14  
@learner, the point is that the function $log(x)/x$ has a single maximum at $x=e$ and is decreasing after that. –  lhf Oct 7 '13 at 11:19
1  
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. –  Christian Fries Oct 7 '13 at 12:15
14  
@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. –  jwg Oct 7 '13 at 12:29
2  
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}$ –  Henry Oct 7 '13 at 17:16

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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