Calculate logarithm by hand

Question

I'd like to calculate the mathematical logarithm "by hand"...

... where stands for the logarithmBase and stands for the value.

---

Some examples (See Log calculator):

The base 2 logarithm of 10 is 3.3219280949

The base 5 logarithm of 15 is 1.6826061945

...

---

Hoever - I do not want to use a already implemented function call like Math.ceil, Math.log, Math.abs, ..., because I want a clean native solution that just deals with +-*/ and some loops.

This is the code I got so far:

function myLog(base, x)  {
  let result = 0;
  do {
    x /= base;
    result ++;
  } while (x >= base)
  return result;
}

let x = 10,
    base = 2;

let result = myLog(base, x)
console.log(result)

But it doesn't seems like the above method is the right way to calculate the logarithm to base N - so any help how to fix this code would be really appreciated.

Thanks a million in advance jonas.

Answer 1

You could use a recursive approach:

 const log = (base, n, depth = 20, curr = 64, precision = curr / 2) => 
   depth  <= 0 || base ** curr === n 
      ? curr
      : log(base, n, depth - 1, base ** curr > n ? curr - precision : curr + precision, precision / 2);

Usable as:

log(2, 4) // 2
log(2, 10) // 3.32196044921875

You can influence the precision by changing depth, and you can change the range of accepted values (currently ~180) with curr

---

How it works:

If we already reached the wanted depth or if we already found an accurate value:

 depth  <= 0 || base ** curr === n 

Then it just returns curr and is done. Otherwise it checks if the logarithm we want to find is lower or higher than the current one:

         base ** curr > n

It will then continue searching for a value recursively by 1) lowering depth by one 2) increasing / decreasing curr by the current precision 3) lower precision

---

If you hate functional programming, here is an imperative version:

  function log(base, n, depth = 20) {
   let curr = 64, precision = curr / 2;
   while(depth-- > 0 && base ** curr !== n) {
     if(base ** curr > n) {
       curr -= precision;
     } else {
       curr += precision;
     }
     precision /= 2;
    }
    return curr;
  }

By the way, the algorithm i used is called "logarithmic search" commonly known as "binary search".

Answer 2

First method: with a table of constants.

First normalize the argument to a number between 1 and 2 (this is achieved by multiplying or dividing by 2 as many times as necessary - keep a count of these operations). For efficiency, if the values can span many orders of magnitude, instead of equal factors you can use a squared sequence, 2, 4, 16, 256..., followed by a dichotomic search when you have bracketed the value.

F.i. if the exponents 16=2^4 works but not 256=2^8, you try 2^6, then one of 2^5 and 2^7 depending on outcome. If the final exponent is 2^d, the linear search takes O(d) operations and the geometric/dichotomic search only O(log d). To avoid divisions, it is advisable to keep a table of negative powers.

After normalization, you need to refine the mantissa. Compare the value to √2, and if larger multiply by 1/√2. This brings the value between 1 and √2. Then compare to √√2 and so on. As you go, you add the weights 1/2, 1/4, ... to the exponent when a comparison returns greater.

In the end, the exponent is the base 2 logarithm.

Example: lg 27

27 = 2^4 x 1.6875

1.6875 > √2 = 1.4142 ==> 27 = 2^4.5 x 1.1933

1.1933 > √√2 = 1.1892 ==> 27 = 2^4.75 x 1.0034

1.0034 < √√√2 = 1.0905 ==> 27 = 2^4.75 x 1.0034

...

The true value is 4.7549.

Note that you can work with other bases, in particular e. In some contexts, base 2 allows shortcuts, this is why I used it. Of course, the square roots should be tabulated.

Second method: with a Taylor series.

After the normalization step, you can use the standard series

log(1 + x) = x - x²/2 + x³/3 - ...

which converges for |x| < 1. (Caution: we now have natural logarithms.)

As convergence is too slow for values close to 1, it is advisable to use the above method to reduce to the range [1, √2). Then every new term brings a new bit of accuracy.

Alternatively, you can use the series for log((1 + x)/(1 - x)), which gives a good convergence speed even for the argument 2. See https://fr.wikipedia.org/wiki/Logarithme_naturel#D%C3%A9veloppement_en_s%C3%A9rie

Example: with x = 1.6875, y = 0.2558 and

2 x (0.2558 + 0.2558³/3 + 0.2558^5/5) = 0.5232

lg 27 ~ 4 + 0.5232 / ln 2 = 4.7548