3
$\begingroup$

I need to solve the equation $$2^x + x = n$$ for $x$ through a programming-based method. Is this possible? If not, then what would be the most efficient way to approximate it?

$\endgroup$
  • $\begingroup$ What language are you using? $\endgroup$ – Alex S Jul 6 '15 at 20:02
  • $\begingroup$ @AlexS I'm using Java $\endgroup$ – JohnW Jul 6 '15 at 20:04
  • $\begingroup$ This is a precalculus problem? $\endgroup$ – Gary. Jul 6 '15 at 20:23
6
$\begingroup$

You could either use numerical methods such as interval bisection, Newtons Method of finding roots applied to $f(x) = 2^x + x - n$, as in Winther's solution.

Secondly, you could solve this equation manually to get the solutions as $x=0$ for $n=1$ and $$x=n-\frac{W_{c}\left(2^n \ln 2\right)}{\ln 2}$$ where we let $c$ range over the integers. If you are utilising a language (Mathematica, let's say) that has the Lambert W function built in, you could simply iterate the function by running through $c \in \mathbb{Z}$.

Note:
If you're looking for real solutions, $W_0(x)$ is real for $−1/e\leq x<\infty$ and $W_{−1}(x)$ is real for $−1/e\leq x < 0$. The other branches do not have real values on $\mathbb{R}$. In this case, we have $2^n \ln 2 > 0$, so we only need $W_0$. (Thanks to Robert Israel)

$\endgroup$
  • $\begingroup$ If you're looking for real solutions, $W_0(x)$ is real for $-1/e \le x < \infty$ and $W_{-1}(x)$ is real for $-1/e \le x < 0$. The other branches do not have real values on $\mathbb R$. $\endgroup$ – Robert Israel Jul 6 '15 at 20:18
  • $\begingroup$ @RobertIsrael I hope you don't mind if I inserted your comment into my answer and credited you. I din't feel confident enough rewording it in my own terms. :-) $\endgroup$ – Zain Patel Jul 6 '15 at 20:21
  • $\begingroup$ You might also note that in this case, $2^n \ln 2 > 0$, so only $W_0$ is needed. $\endgroup$ – Robert Israel Jul 6 '15 at 20:22
3
$\begingroup$

Newton's method is usually the best numerical method for such problems: it's very simple, converges very fast and it works most of the time.

To use it define a function $f(x) = 2^x +x - n$ so that the desired solution to your problem is the solution to $f(x) = 0$. Pick a guess $x_0$, say $x_0 = 0$, and the itterate via

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$

For example if $n=10$ and $x_0 = 0$ then after only $7$ itterations you have the solution to $10$ significant digits. As a convergence criterion you can for example use $|f(x_n)| < \epsilon$ where $\epsilon$ is some small predefined constant.


${\bf More~above~the~convergence~criterion~in~general}$:

There are many ways to do the convergence criterion and depending on the problem at hand one will be better than the other. Here are some options.

As Claude mentioned below for some functions $|f|$ itself might be unaturally small far away from the desired solution so that monitoring the smallness of $|f(x_n)|$ is not advisable. One cn get around this be considering a criterion like $|x_n - x_{n-1}| < \epsilon$.

Another option is the following: after making the initial guess we first perform $N$ itterations (a 'burn-in') and calculate the initial residual $|f(x_N)|$. Then we continue itterating and define convergence when $\frac{|f(x_k)|}{|f(x_{N}|} < \epsilon$.

One can also consider a combination of $|f(x_k)|$ and $|x_n-x_{n-1}|$ as the criterion. The best advise here is to experiment with the problem-type you have at hand to see for your self what works best.

$\endgroup$
  • $\begingroup$ If I may, I should not recommend to use as stopping criteria $|f(x_n)| < \epsilon$. Suppose that you change the function from $f(x) = 2^x +x - n$ to $f(x) = (2^x +x - n)\times 10^{-20}$; the problem is solved immediately. I think that $|x_{n}-x_{n-1}|<\epsilon$ is better. $\endgroup$ – Claude Leibovici Jul 7 '15 at 10:37
  • $\begingroup$ @ClaudeLeibovici You raise an interesting point. I totally agree that the criterion I mentioned is not optimal and can dramatically fail. However I can also come up with similar examples for $|x_n - x_{n-1}|$ in a more complicated setting. This is something I have encountered many times (when using N.M. to solve non-linear PDE’s where $x_n$ are functions) and I still haven't found a good universal solution to it (which still annoys me:) Anyway, I have added some notes on the convergence criterion. $\endgroup$ – Winther Jul 7 '15 at 13:48
  • 1
    $\begingroup$ I have no practical experience with NM in the area of PDE's. I think I have at least a loooong experience with nonlinear equations. In fact, when young, I had scientific subroutines for which convergence was achieved if both conditions $|f(x_n)| < \epsilon_1$ and $|x_n-x_{n-1}| < \epsilon_2$ were satisfied (but I never have been able to understand the first one). It is good you added these notes to your answer. Cheers. $\endgroup$ – Claude Leibovici Jul 7 '15 at 13:55
1
$\begingroup$

As Winther answered, Newton method is probably the simplest numerical method to use.

When you look at the function $$f(x) = 2^x +x - n$$ you should notice that it is quite stiff. But, changing to $$g(x)=x \log(2)-\log(n-x)$$ makes the function quite linear.

Uisng the same case as Winther $n=10$ and starting at $x_0=0$, the iterates are $$x_1=2.903099386$$ $$x_2=2.840013526$$ $$x_3=2.839966365$$ which is the solution for $10$ significant digits.

Let us make it (apparently) more difficult with $n=10^6$ still starting at $x_0=0$; the iterates are $$x_1=19.93153981$$ which is the solution for $10$ significant digits.

In practice, you can use as a starting point the first iterate of Newton method that is to say $$x_0=\frac{\log (n)}{\frac{1}{n}+\log (2)}$$

You could have a better approximation using Halley method which leads to $$x_0=\frac{n \left(2 (n \log (2)+1)^2-\log (n)\right) \log (n)}{2 (n \log (2)+1)^3}$$ For $n=10$, this would give $x_0\approx 2.84997$.

$\endgroup$
0
$\begingroup$

A possibly efficient method: deriving with respect to $n$, you get the differential equation

$$\frac{dx}{dn}(\ln(2)2^x+1)=1,$$

or $$\frac{dx}{dn}=\frac1{ln(2)(n-x)+1}.$$

Using a fixed-step integration method (Runge-Kutta) with step $1$ will give you the $x_n$. (Preferably combined with a step of Newton to avoid drift.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.