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

[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?

 

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

 

[CRGreathouse]

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?

Numerical methods work well. Here's Brent's method in Pari/GP:

> 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

 

[Hurkyl]

That's a problem of computers, which can't handle too large or too small numbers.

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.

 

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

 

[CRGreathouse]

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

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.

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

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.

 

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

 

[uart]

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?

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.

 

[uart]

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.

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

 

[CRGreathouse]

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

See post #5.

 

[uart]

See post #5.

Whoops, I missed that correction.

 

[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!