Simplify $n\log_2n=10^6$

Question

Good Evening,

I know this is a basic question, but I haven't been able to find a clear explanation for how to simplify the follow equation: $$n\log_2n=10^6$$ Solving this equation is part of the solution for Problem 1-1 from the Intro. to Algorithms book by CLRS: http://atekihcan.github.io/CLRS/P01-01/

The author there simplifies the above to: $$n=62746$$ But I can't see how to do this. Thank you.

Answer 1

You are doing one dimensional root finding on the function $f(n)=10^6-n \log n$. This is a large subject, a chapter in every numerical analysis book. The simplest algorithm to describe is bisection. We note that $f(1) \gt 0, f(10^6) \lt 0$ and check the midpoint. We replace the endpoint of the same sign with the midpoint, which cuts the interval in half. We do this as many times as needed to get the interval short enough that the error is acceptable. There are many fancier algorithms that may converge more rapidly.

Answer 2

$$n\log_2n=10^6$$ $$n\ln n=10^6\ln 2$$ $$\ln n=\frac1n10^6\ln 2$$ $$n=e^{(10^6\ln 2)/n}$$ $$10^6\ln2=\frac{10^6\ln2}ne^{(10^6\ln2)/n}$$ Now we require the use of the non-elementary Lambert W function to simplify this further: $$W(10^6\ln2)=\frac{10^6\ln2}n$$ $$n=\frac{10^6\ln2}{W(10^6\ln2)}=62746.126469\dots$$ Computing the Lambert W is a bit hard without libraries, which is why the derivation in the CLRS solutions link simply iterates over $n$ until the expression exceeds a million.

Answer 3

Starting from Parcly Taxel's answer, the problem is to compute $W(x)$ for a very large argument. If you do not have access to Lambert function, let me suggest the very fast algorithm presented in this paper.

For the computation of $$y=\log\big(W(e^x)\big)\implies W(e^x)=e^y$$ the author proposes the very simple iterative scheme $$y_{n+1}=y_n-\frac{2 \left(e^{y_n}+1\right) \left(e^{y_n}+y_n-x\right)}{2 \left(e^{y_n}+1\right)^2-e^{y_n} \left(e^{y_n}+y_n-x\right)}$$ If you need to compute it many time, you could save a lot defining obvious intermediate terms.

The author proposes as starting value $y_0=\log(x)$; in fact, it should be better in my humble opinion, to use $$y_0=\log\big(x-\log(x)\big)$$

Applied to your case, we should get the following iterates $$\left( \begin{array}{cc} n & W\big(10^6\log(2)\big) \\ 0 & \color{red} {1}0.85009305921355973225341 \\ 1 & \color{red} {11.0468}4846509467698238553 \\ 2 & \color{red} {11.046852125521960930}48720 \\ 3 & \color{red} {11.04685212552196093051026} \end{array} \right)$$

Answer 4

Note that $2^{20}=16\cdot 2^{16}=1\,048\,576$ is pretty darn close to one million, so $n=2^{16}$ is pretty close to the answer. Also note that decreasing $n$ by a relatively small amount won't make a big change to $\log_2(n)$. We want a result that's $48\,576$ smaller, we can as a first attempt just reduce our $n$ by $48\,576/16=3036$ and see what we get: $$ \log_2(2^{16}-3036)\cdot(2^{16}-3036)\approx 995\,723 $$ which is only $4277$ away. We missed because of course $\log_2(2^{16}-3036)\approx 15.93$ is a little smaller than $16$.

However, we can now repeat this process, noting that increasing $n$ by $4277/15.93\approx 268$ ought to give us an even better result, this time missing only overshooting by 380.

There is a better method, though, which in a much better way encompasses how also the logarithm changes: use the derivative. Differentiating $f(n)=n\log_2(n)$, we get $$ f'(n)=\log_2(n)+\frac1{\ln(2)} $$ We only used the first term when deciding to decrease $n$ by $3036$ the first time. However, using the full derivative, we're told to decrease $n$ by $48\,576/(16+1/\ln2)\approx 2785$. Let's see where this takes us: $$ \log_2(2^{16}-2785)(2^{16}-2785)\approx 1\,000\,085 $$ and look how close we got immediately, compared to the previous attempt, just by adding $\frac1{\ln2}$. One more iteration ought to do it. Next we will decrease $n$ by $85/f'(2^{16}-2785)\approx4.9$, and this gives us $$ \log_2(2^{16}-2789.9)(2^{16}-2789.9)\approx999\,999.5 $$ and I daresay we clearly can't find a better integer approximation to the solution than $2^{16}-2790=62\,746$.

This is called Newton's method, and it works remarkably well when you have a decent guess to start with. It is a widely used algorithm for numerical solution of equations because of its simplicity and efficiency.