1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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