Using Lambert W to solve n*log(n) = c

1. Sep 2, 2010

wwshr87

I intend to solve the following problem n*log(n)=c, where log is base 10.

n*log(n)=c, expressing this as n=10^(c/n), then this becomes n^n=10^c.

Now this can be solved using a numerical method such as Lambert W function.

The Lambert W function solves the problem x*e^(x)=c, where c is a constant, we can use

this to solve our problem. ln(x)*e^(ln(x))= ln(c).

Lets say I want find n*log(n)=100, then using this method I find n=56.9612. Which is

correct, but what happens as c approaches a very large value such as 10*10^9? Is there

no solution for this? This is an assignment but I am getting infinity as a solution since c

is too large, any ideas?

2. Sep 2, 2010

Petr Mugver

That's a problem of computers, which can't handle too large or too small numbers. The mathematic problem always has a solution, the informatic one not!

A trick would be (but I don't know if it works) to solve, instead of

$$n^n=c$$

the equivalent equation

$$n^{\frac{n}{10^k}}=c^{\frac{1}{10^k}}$$

This way the number on the right is much smaller than c, so maybe you can avoid overflow.

3. Sep 2, 2010

CRGreathouse

Numerical methods work well. Here's Brent's method in Pari/GP:
Code (Text):
> solve(n=1,9e9,n*log(n)/log(10)-100)
time = 0 ms.
%1 = 56.961248432260820305122298236945720381
> solve(n=1,9e9,n*log(n)/log(10)-10*10^9)
time = 0 ms.
%2 = 1105747502.5934196047121510163796270508

4. Sep 2, 2010

Hurkyl

Staff Emeritus
I assume what you meant to say is "that is a problem of calculators that weren't programmed to work with large or small numbers", and have implicitly assumed our goal is to enumerate a decimal string.

5. Sep 2, 2010

wwshr87

I am sorry, I made a mistake. The value c=10^(10^9), which in MatLab is inf.

I will look into Brent's method and see what I can do.

Thank you.

6. Sep 2, 2010

CRGreathouse

Code (Text):
solve(n=1,10^1e9,n*log(n)/log(10)-10^1e9)
time = 0 ms.
%3 = 1.0000000090000000770913503056206873776 E999999991
although in this case the answer is good to only 30 decimal places.

If you're going to write it on your own, I recommend the secant method instead. For this problem it's just as good, and much easier to implement.

7. Sep 3, 2010

JJacquelin

Indeed, equation x*ln(x)=c can be numerically solved, even for large c.
It is also possible to solve it in term of the Lambert W function x=exp(W(c)).
In case of large c, one can use the asymptotic series development of the LambertW function. For example, see formula (15) in :
http://mathworld.wolfram.com/LambertW-Function.html
Of course the series can be reduced to a lower number of terms, depening on the needed accuracy.

File size:
9.9 KB
Views:
215
8. Sep 3, 2010

uart

Im assuming that you've already figured out the solution is:

$$n=e^{W(c \ln(10))}$$.

I don't see what's the problem with evaluating the lambert W function for large arguments. I tried both Newtons method and a fixed point iteration and had no convergence problems with either.

The simple fixed point iteration : w = ln(x/w) converges accurate 10 significant figures only 8 iterations for c=10^10 (and of course x = c ln(10) as required in the above solution).

Note: I'm finding W(x) by solving for "w" in "w e^w = x", using starting value of w=ln(x) for the fixed point iterations.

Last edited: Sep 3, 2010
9. Sep 3, 2010

uart

Hi CRGreathouse. The OP said 10*10^9 not 10^(10^9). :)

10. Sep 3, 2010

CRGreathouse

See post #5.

11. Sep 3, 2010

uart

Whoops, I missed that correction.

12. Sep 3, 2010

uart

In that case the OP definitely should go with the asymptotic solution mentioned above by JJacquelin. It will converge quite rapidly given that (L1=log(c)) >> (L2 = log(log(c))) and it is especially easy to caclulate due to the convienient properties of "log". Even for c=10^(10^9) it's straight forward to evaluate L1 and L2 with just a pocket calculator!