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

Question

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.

Answer 1

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.