1
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Gaurav Kumar Jul 17 '16 at 10:46

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.