# Fastest method forfinding a solution to x*log(x)

more specifically, $C x \log_2(x)- K = 0$, where $C$ and $K$ are constants ($\log_2$ means log base 2).

I was solving a topcoder problem, SortEstimate, which requires us to solve the aforementioned equation. (Side question: can it be called a polynomial? No? Then what is the name of such an equation?)

I used Binary search to solve this in C++ and was able to do so successfully to high accuracy. But then I came across a rather different solution which I think, having studied Numerical Analysis in college, may be using one of methods for root finding. I want to find the method, but haven't found anything useful on google or other numerical analysis resources available online.

Here's the code – also $K$ in the equation is the variable time here

#include <iostream>
#include <cmath>
using namespace std;
class SortEstimate
{
public:

double howMany(int c, int time){

long double x = 7;
long double r = double(time)/double(c);
for (int i = 0; i<1000; i++) {
x = x - (x * log(x)/log(2.0) - r)/(1.0 + log(x)/log(2.0));
}
return x;

}
};

int main()
{
SortEstimate sort;
cout<<sort.howMany(1,8)<<endl;//4
cout<<sort.howMany(2,16)<<endl;//4
cout<<sort.howMany(37,12392342)<<endl;//23105
cout<<sort.howMany(1,2000000000)<<endl;//7.6375e+07

return 0;
}


In the for loop, what does the statement mean? All I can think is it should be a numerical method. Any information would be useful.

If this is not the right community to ask this doubt, then please refer me to the correct one.

This equation is not polynomial. Assuming both $K$ and $C$ are positive (as in your linked problem), then the solution of $C x \ln_2(x) - K = 0$ can be found in terms of the Lambert $W$ function or the Wright $\omega$ function:
$$x = \frac{D}{W_0(D)} = \frac{D} {\omega\left(\ln\left( D \right)\right)}$$
where $D = \ln(2)K/C$.
Corless, et al. 1996 is a good reference for implementing the Lambert $W$. You can find some basic Matlab code to compute it numerically here, which should be trivial to convert to C++. The performance of this code could be improved by using series and asymptotic expansions to find a better initial guess.
As for what the C++ code in your question is doing, it appears to be nothing more than a naïve implementation of Newton's method. The for loop just iterates one the recurrence relation a large number of times. It assumes that the system will converge after 1,000 steps. This is probably a reasonable assumption, but is quite inefficient. The Matlab code I linked to uses a higher order scheme, Halley's method, and a convergence condition based on a tolerance.