retagged by
678 views

1 Answer

Best answer
1 1 vote

If you are asking this for the purpose of GATE, you have to find the (approximate) numerical value of $x$ for a given $N$ by hit and trial.

You can use bisection method to quickly approach the answer (or other faster converging methods if you like).

$$f(x) = x^x - N$$


Bisection Method:


Find points $x_{low}$ and $x_{high}$ such that $f(x_{low}) < 0$ and $f(x_{high}) > 0$

Repeat:

  • $x_{mid} = x_{low} + \dfrac{x_{high} - x_{low}}{2}$
     
  • if $f(x_{mid})$ is sufficiently close to $0$, exit the loop.
     
  • If $f(x_{mid}) > 0$, then $x_{high} = x_{mid}$
     
  • Else if $f(x_{mid}) < 0$, then $x_{low} = x_{mid}$

The desired solution is $x_{mid} \log x_{mid} \approx \log N$

For example: $N = 12345$

$\small \begin{array}{|l|r|r|r|}
\hline
\text{Iteration} & x_{low} & x_{high} & x_{mid} & f(x_{mid}) & \text{ error}\\[1em]
\hline 1 & 0.0000 & 10.0000 & 5.0000 & -9220.000 & 74.69 \;\%\\
\hline 2 & 5.0000 & 10.0000 & 7.5000 & 3643261.791 & 29512.04 \;\%\\
\hline 3 & 5.0000 & 7.5000 & 6.2500 & 81898.218 & 663.41 \;\%\\
\hline 4 & 5.0000 & 6.2500 & 5.6250 & 4229.453 & 34.26 \;\%\\
\hline 5 & 5.0000 & 5.6250 & 5.3125 & -5213.997 & 42.24 \;\%\\
\hline 6 & 5.3125 & 5.6250 & 5.4688 & -1497.607 & 12.13 \;\%\\
\hline 7 & 5.4688 & 5.6250 & 5.5469 & 1056.190 & 8.56 \;\%\\
\hline 8 & 5.4688 & 5.5469 & 5.5078 & -289.806 & 2.35 \;\%\\
\hline
\end{array}$

We get a satisfactory answer after $8$ iterations. This calculation can be easily done with a calculator within 2 minutes.


Newton Raphson:

$\begin{align}
f'(x) &= x^x ( 1+ \log x)\\[2em]
\hline
x_{n+1} &= x_n - \frac{f(x_n)}{f'(x_n)}\\[1em]
&= x_n - \frac{x_n^{x_n} - N}{x_n^{x_n}(1+\log x_n)}\\[1em]
\end{align}$

For example: $N = 12345$

We need to make an initial guess which is sufficiently close to the answer, else the algorithm won't converge. We guess $x = 5$

$\small \begin{array}{|l|r|r|r|}
\hline
\text{Iteration} & x & f(x) & \text{error} & x_{next}\\[1em]
\hline 1 & 5.0000 & -9220.000 & 74.69 \;\% & 6.1307\\
\hline 2 & 6.1307 & 54944.165 & 445.07 \;\% & 5.8404\\
\hline 3 & 5.8404 & 17602.403 & 142.59 \;\% & 5.6278\\
\hline 4 & 5.6278 & 4357.900 & 35.30 \;\% & 5.5322\\
\hline 5 & 5.5322 & 532.647 & 4.31 \;\% & 5.5169\\
\hline 6 & 5.5169 & 11.126 & 0.09 \;\% & 5.5169\\
\hline
\end{array}$

We converge to a better answer in lesser iterations.


The above methods are the easy ways of finding the solution.

If the value of $N$ is nice, for example, $N = 46,656$, hit and trial will only take a few steps and can be done mentally to get $x = 6$.


You shouldn't be looking for formulas for $x$ in terms of $N$, because your equation won't have a pretty formula.

If you insist, then try this: http://www.wolframalpha.com/input/?i=x*log%28x%29%3Dlog%28y%29+solve+for+x

selected by
Position:
Show:

Related questions

0 0 votes
1 1 answer
826
826 views
deepti asked Jul 31, 2016
826 views
It is given in CLRS book chapter 3, page no. 56 that lg^k(n) = (lg n)^k. Can somebody please give me an example or check if my example is correct? Shoudn't lg^k(n) be { l...
0 0 votes
2 answers 2 answers
858
858 views
dragonball asked Aug 2, 2018
858 views
How the slowness and the fastness of any algorithm depends ?Is (n/logn) is slower than log(logn) ?
1 1 vote
3 3 answers
2.8k
2.8k views
Tushar Garg asked Jul 4, 2018
2,756 views
How to find log n base2+ log n base 3+ log n base4+........log n base n?
0 0 votes
1 1 answer
446
446 views
piyushkr asked Jan 10, 2016
446 views
What is the difference between $\log^m n$ and $(\log n)^m.$ Can anyone explain?