Computing Logarithms on Microcontrollers

Nomenclature and Identities

Three logarithm bases are commonly used in engineering and computing:

Key identities (valid for any base f):

Conversion between bases:

Borchardt's Algorithm

A simple rational approximation to the natural logarithm:

Accurate to about 3 significant figures for \(x\) near 1. For a PIC without hardware square root, this alone is not practical, but serves as a useful reference.

Factoring Method for Binary Logarithms

The identity \(f(a \cdot b) = f(a) + f(b)\) lets us decompose any number into factors whose logarithms we know. For binary logarithms, we factor \(x\) as:

Finding \(n\) is easy: it equals the position of the most significant bit. The challenge is computing \(\lg(c)\) for \(c \in [1, 2)\).

Method 3a — Factors of the form \(2^i/(2^i - 1)\)

Build a lookup table:

The first values: \(\lg(2), \lg(4/3), \lg(8/7), \lg(16/15), \ldots\)

Algorithm (Knuth Vol.1, section 1.2.3, exercise 25):

// Input: 16-bit x > 0. Output: y = lg(x)
// L1. Initialize
y = 0;
z = x >> 1;
k = 1;

// L2–L5. Main loop
while(x != 1) {
    if(x - z >= 1) {        // L3: Compare
        x = x - z;          // L4: Reduce
        z = x >> k;
        y = y + log2arr[k]; //     Add partial log
    } else {
        z = z >> 1;         // L5: Shift
        k = k + 1;
    }
}

The division \(x / (2^k/(2^k-1))\) simplifies to a shift:

Method 3b — Factors of the form \(1 + 2^{-(i+1)}\)

Alternative table:

Values: \(\lg(3/2), \lg(5/4), \lg(9/8), \lg(17/16), \ldots\)

for(i = 1, d = 0.5; i < M; i++, d /= 2) {
    if(x > 1 + d) {
        x /= (1 + d);
        g += log2arr[i-1];
    }
}

The division by \((1 + 2^{-i})\) can be expanded as a series:

Table Look-up with Linear Interpolation

After range-reducing \(x\) to \([1, 2)\) using bit manipulation, apply linear interpolation between tabulated values:

When \(a\) and \(b\) are consecutive table entries separated by a power of 2, the division reduces to a right shift:

// Scale x so MSB is in bit 15
g = 15;
while(g && !(x & 0x8000)) { x <<= 1; g--; }
if(!g) return 0;

x <<= 1;                    // Normalize: remove known MSB
j = x >> 12;                // 4-bit table index
x_minus_a = x & 0x0FFF;    // Fractional part

// Linear interpolation (shift instead of divide)
gf = log_table[j] + (x_minus_a * (log_table[j+1] - log_table[j])) >> 12;

Series Expansions

Useful series for computing natural logarithms without tables:

Algorithm Comparison