c - 自然对数 (ln) 和指数的高效实现

Question

我正在寻找 log() 的实现和 exp() C 库中提供的函数 <math.h> .我正在使用 8 位微 Controller (OKI 411 和 431)。我需要计算 Mean Kinetic Temperature .要求是我们应该能够尽可能快地计算 MKT，并使用尽可能少的代码内存。编译器自带log()和 exp()在 <math.h> 中发挥作用.但是调用任一函数并与库链接都会导致代码大小增加 5 KB，这不适合我们使用的其中一个微处理器 (OKI 411)，因为我们的代码已经消耗了 ~12K 的可用代码内存~15K。

我正在寻找的实现不应使用任何其他 C 库函数(如 pow()、sqrt() 等)。这是因为所有库函数都打包在一个库中，即使调用一个函数，链接器也会将整个 5K 库带到代码内存中。

编辑

算法应精确到小数点后 3 位。

Answer 1

使用泰勒级数既不是最简单的方法，也不是最快的方法。大多数专业实现都使用近似多项式。我将向您展示如何在 Maple 中生成一个(这是一个计算机代数程序)，使用 Remez algorithm .

对于 3 位数的精度，在 Maple 中执行以下命令:

with(numapprox):
Digits := 8
minimax(ln(x), x = 1 .. 2, 4, 1, 'maxerror')
maxerror

它的响应是以下多项式:

-1.7417939 + (2.8212026 + (-1.4699568 + (0.44717955 - 0.056570851 * x) * x) * x) * x

最大误差为:0.000061011436

我们生成了一个近似于 ln(x) 的多项式，但仅在 [1..2] 区间内。增加间隔是不明智的，因为那会进一步增加最大误差。取而代之的是，进行以下分解:

所以首先求出 2 的最高次方，它仍然小于该数(参见:What is the fastest/most efficient way to find the highest set bit (msb) in an integer in C?)。该数字实际上是以 2 为底的对数。除以该值，然后结果进入 1..2 区间。最后，我们必须添加 n*ln(2) 以获得最终结果。

数字 >= 1 的示例实现:

float ln(float y) {
    int log2;
    float divisor, x, result;

    log2 = msb((int)y); // See: https://stackoverflow.com/a/4970859/6630230
    divisor = (float)(1 << log2);
    x = y / divisor;    // normalized value between [1.0, 2.0]

    result = -1.7417939 + (2.8212026 + (-1.4699568 + (0.44717955 - 0.056570851 * x) * x) * x) * x;
    result += ((float)log2) * 0.69314718; // ln(2) = 0.69314718

    return result;
}

虽然如果你打算只在[1.0, 2.0]区间使用它，那么函数是这样的:

float ln(float x) {
    return -1.7417939 + (2.8212026 + (-1.4699568 + (0.44717955 - 0.056570851 * x) * x) * x) * x;
}