CODEWITHSUNDEEP
javaalgorithmmathlogarithm
Justin
Justin

Reputation: 25277

Logarithm Algorithm

I need to evaluate a logarithm of any base, it does not matter, to some precision. Is there an algorithm for this? I program in Java, so I'm fine with Java code.

How to find a binary logarithm very fast? (O(1) at best) might be able to answer my question, but I don't understand it. Can it be clarified?

Upvotes: 44

Views: 62754

Answers (2)

Alexandre Piccini
Alexandre Piccini

Reputation: 75

I know this is extremely late, but this may come to be useful for some since the matter here is precision. One way of doing this is essentially implementing a root-finding algorithm that uses, from its base, the high precision types you might want to be using, consisting of simple +-x/ operations.

I would recommend implementing Newton's ​method since it demands relatively few iterations and has great convergence. For this sort of application, specifically, I believe it's fair to say it will always provide the correct result provided good input validation is implemented.

Considering a simple constant "a" where log_b(x) = a

Where a is sought to be solved for such that it obeys, then x - b^a = 0

We can use the Newton method iteratively to find "a" within any specified tolerance, where each a-ith iteration can be computed by a_i = a_{i-1} - \frac{x - b^a}{-ab^{a-1}}

and the denominator is

-ab^{a-1} = \frac{\partial}{\partial a},

because that's the first derivative of the function, as necessary for the Newton method. Once this is solved for, "a" is the direct answer for the "a = log,b(x)" problem, obtainable by simple +-x/ operations, so you're already good to go. "Wait, but there's a power there?". Yes. If you can rely on your power function as being accurate enough, then there are no issues with going ahead and using it there. Otherwise, you can further break down the power operation into a series of other +-x/ operations by using these methods to simplify whatever decimal number that is on the power into two integer power operations that can be computed easily with a series of multiplication operations. This process will eventually leave you with nth-roots to solve for, which you can also find with the Newton method. If you do go down that road, you can use this for the newton method

\frac{\partial (\sqrt[b]{x})}{\partial x} = \frac{\sqrt[b]{x}}{bx}

which, as you can see, has to be solved for recursively until you reach b = 1.

Phew, but yeah, that's it. This is the way you can solve the problem by making sure you use high precision types along the whole way with only +-x/ operations. Below is a quick implementation I did in Excel to solve for log,2(3), compared with the solution given by the software's original function. As you can see, I can just keep refining "a" until I reach the tolerance I want by monitoring what the optimization function gives me. In this, I used a=2 as the initial guess, which you can use and should be fine for most cases.

Newton method for the solution of a log operation

Upvotes: 2

Óscar López
Óscar López

Reputation: 235984

Use this identity:

logb(n) = loge(n) / loge(b)

Where log can be a logarithm function in any base, n is the number and b is the base. For example, in Java this will find the base-2 logarithm of 256:

Math.log(256) / Math.log(2)
=> 8.0

Math.log() uses base e, by the way. And there's also Math.log10(), which uses base 10.

Upvotes: 104

Related Questions