Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Sep 2, 2010 #1
    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. jcsd
  3. Sep 2, 2010 #2
    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

    [tex]n^n=c[/tex]

    the equivalent equation

    [tex]n^{\frac{n}{10^k}}=c^{\frac{1}{10^k}}[/tex]

    This way the number on the right is much smaller than c, so maybe you can avoid overflow.
     
  4. Sep 2, 2010 #3

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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
     
  5. Sep 2, 2010 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  6. Sep 2, 2010 #5
    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.
     
  7. Sep 2, 2010 #6

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  8. Sep 3, 2010 #7
    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.
     

    Attached Files:

  9. Sep 3, 2010 #8

    uart

    User Avatar
    Science Advisor

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

    [tex]n=e^{W(c \ln(10))}[/tex].

    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
  10. Sep 3, 2010 #9

    uart

    User Avatar
    Science Advisor

    Hi CRGreathouse. The OP said 10*10^9 not 10^(10^9). :)
     
  11. Sep 3, 2010 #10

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    See post #5.
     
  12. Sep 3, 2010 #11

    uart

    User Avatar
    Science Advisor

    Whoops, I missed that correction.
     
  13. Sep 3, 2010 #12

    uart

    User Avatar
    Science Advisor

    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!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook