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

## 1 Answer

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.

• In Newton's method, the denominator has the first derivative of the function given, accordingly the denominator statement should be >> (1+log(x))/log2 but instead it is >> (1+ log(x)/log2) , this was the reason i though that it may not be newton's method Commented Jul 17, 2016 at 10:46