Skip to main content
4 of 4
log -> ln
horchler
  • 763
  • 1
  • 5
  • 17

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.

horchler
  • 763
  • 1
  • 5
  • 17