Solving equations with exponential and polynomial functions of x: the Product Log Function

I was trying to solve an equation of the form cx^p=q^x for x, but couldn’t figure out how to do the algebra needed to isolate x.  The actual problem was to find when an algorithm with O(n^2) runtime performance would have a shorter runtime than an algorithm that is O(2^n).

Text-based searches weren’t turning up anything, so I tried to see how Wolfram Alpha would solve it.  Turns out there is a neat tool called the Product Log function, aka the Lambert W function, that can be used to find a closed-form solution to this equation.  The Wikipedia article explains the solution method, but you basically need to reorganize the original equation into the form y = x e^x using algebraic and logarithmic operations and then x=W(y).  Note that the solution may not be unique; W(y) is a multivalued function.

Of course, for my original problem where I was actually trying to find the closest integer less than or equal to x, and given that q^x grows rather quickly, it is sufficient to use a spreadsheet to calculate the two sides of the original equation for all small values of x.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: