2
$\begingroup$

I am trying to code and algorithm that can allow me to calculate power of a function with decimal exponent. The language that I am using to code in doesn't has any predefined power functions.

I already have a simple formula coded which allows me to calculate power of a function with non-decimal exponents.

I don't necessarily need a generalized solution. I only need to find value of a number raised to the power 2.4.

I tried to break down my problem as follows:

x ^ (2.4) = (x ^ 2) * (x ^ 0.4)
= (x ^ 2) * (x ^ (2/5))
= (x ^ 2) * ((x ^ 2) ^ 1/5)

Finding square of x can be done, so my problem breaks down to calculating the "5th root" of a number.

I also thought of breaking my problem into a logarithmic equation but didn't reached anywhere with that.

I am thinking of writing a code implementing the long-divison method of calculating roots but that seems highly inefficient and non-elegant.

Can anyone suggest me a more simpler and efficient way of solving my problem? If not, then has anyone tried coding the long-divison method of calculating roots?

Thanx in advance!!

Note: this is a template that i would be using many many times in my execution so efficiency is all the more important for me.

$\endgroup$
  • 1
    $\begingroup$ You can always write any exponential expression $a^x$ as $exp(x \ln a)$, and $\exp$ and $\ln$ are probably both fast and available. $\endgroup$ – Travis Willse Aug 29 '14 at 6:58
  • $\begingroup$ @Travis i think i should have mentioned that i have been out of touch with mathematics for many years now. So essentially i am a maths noob now. Can you please elaborate, what is exp and ln? $\endgroup$ – Surender Thakran Aug 29 '14 at 7:00
  • $\begingroup$ @Travis ok i just googled them. Unfortunately neither exp() or ln is available in the language. $\endgroup$ – Surender Thakran Aug 29 '14 at 7:06
  • $\begingroup$ However, it could be efficient to use a logarithm table in your computer program if calling values from the memory is "cheaper" than computing. That way, your operations would reduce to multiplications and looking up numbers in tables. $\endgroup$ – Raskolnikov Aug 29 '14 at 7:09
5
$\begingroup$

Suppose you want to compute ${3.21}^{1/5}$. If you have a logarithm table (say base 10), you only need the logarithms of numbers between 0.1 and 1 stored (alternatively between 1 and 10), as many as is relevant for your precision.

Then because

$$\log (3.21^{1/5}) = \frac{1}{5}\left(\log(10) + \log(0.321)\right)= \frac{1}{5}\left(1+\log(0.321)\right)$$

Now you look up $\log(0.321)$ in your table, which will look something like this

$$\begin{array}{c|c} \text{Input} & \text{Output} \\ \hline \ldots & \ldots \\ \color{red}{0.321} & -0.493 \\ \ldots & \ldots \end{array}$$

do the above computation

$$\frac{1}{5}(1+\log(0.321)) = \frac{1}{5}(1-0.493) = 0.101$$

and look up the result in the "answer column" of your table to revert the $\log$ operation. Since the answer is positive, and we worked with a table containing logarithms of numbers between 0 and 1, we'll need to look up the opposite first

$$\begin{array}{c|c} \text{Input} & \text{Output} \\ \hline \ldots & \ldots \\ 0.792 & \color{red}{-0.101} \\ \ldots & \ldots \end{array}$$

and now take the inverse of that number to obtain the result: $1.262$.

$\endgroup$
  • $\begingroup$ "you only need the logarithms of a numbers between 0 and 1 stored": I think you mean between 0.1 and 1. $\endgroup$ – TonyK Aug 29 '14 at 7:34
  • $\begingroup$ True that is largely sufficient, I'll modify that! $\endgroup$ – Raskolnikov Aug 29 '14 at 7:35
  • $\begingroup$ Don't you think that we could also generate two spline functions and just evaluate them ? It could be quite unexpensive once the coefficients have been stored. $\endgroup$ – Claude Leibovici Aug 29 '14 at 7:52
  • $\begingroup$ @Raskolnikov thanks, it seems like it could work. Very high precision is not important for me so i can keep my table shorter. $\endgroup$ – Surender Thakran Aug 29 '14 at 7:57
  • $\begingroup$ @When you say two spline functions, you mean one for the log and one for its inverse, right? I'm willing to write out an answer involving spline functions if nobody does it before me. I'll be AFK for a couple of weeks though. $\endgroup$ – Raskolnikov Aug 30 '14 at 2:52
2
$\begingroup$

To compute fifth roots without logarithms, you can use Newton's method. Suppose we want $a^{1/5}$. Define $f(x) = x^5 - a$; we want to find a root of $f$.

So let $x_0$ be a reasonable starting point (see Where to start), and define for $n \ge 0$ $$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} = x_n - \frac{x_n^5-a}{5x_n^4} = \frac{4x_n^5 - a}{5x_n^4}$$

Now iterate this equation until $|x_{n+1}-x_n|$ is small enough (see When to stop).

Where to start
In this instance, $a$ is strictly positive, and $f$ is well-behaved $-$ monotonic increasing, and convex on $(0,\infty)$. So you can start just about anywhere in $(0,\infty)$. But the algorithm runs faster if you start with a reasonable estimate. A simple method, good enough in this case, would be to try $x_0=1,2,4,8,\ldots$ until $x_0^5 \ge a$.

When to stop
Because of the convexity of $f$, an iteration that starts with $x_0^5 \ge a$ would satisfy $x_n \ge x_{n+1} \ge a^{1/5}$ for all $n$, if all calculations were done to infinite precision. You can't do that, obviously; instead, you can stop as soon as $x_{n+1} \ge x_n$. This means that you have reached the limits of your floating-point precision.

$\endgroup$
1
$\begingroup$

Just a Travis commented, say that you need to compute $A=x^b$ whatever $b$ could be. So taking the logarithms of both sides gives $$\log(A)=b\log(x)$$ Taking the exponentials of both sides gives $$e^{\log(A)}=A=e^{b\log(x)}$$ and you are done for any value of $b$ (integer, rational, irrational, ...).

$\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.