有效实现自然对数​​(ln)和取幂

Question

基本上,我正在寻找C库中提供的实现log()和exp()功能<math.h>.我正在使用8位微控制器(OKI 411和431).我需要计算平均动力学温度.要求是我们应该能够尽可能快地计算MKT并尽可能少地使用代码存储器.编译器附带log()并exp()运行<math.h>.但调用两个函数,并与库链接会导致代码大小5千字节,这将不适合于我们与(OKI 411)工作在微的一个增加,因为我们的代码已经消耗〜12K可用〜15K代码存储器.

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

编辑

该算法应该最多3位小数.

Answer 1

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

对于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的最高功率,它仍然小于数字(参见:在C中的整数中找到最高设置位(msb)的最快/最有效的方法是什么？).该数字实际上是基数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;
}

Answer 2

e ^ x的泰勒级数非常快速地收敛,您可以将实现调整到所需的精度.(http://en.wikipedia.org/wiki/Taylor_series)

日志的泰勒系列不是很好......

Answer 3

如果你不需要其他任何浮点数学,你可以很容易地计算一个近似的小数基数2.首先将您的值向左移动,直到它达到32768或更高,并存储您执行该操作的次数count.然后,重复几次(取决于您所需的比例因子):

n = (mult(n,n) + 32768u) >> 16; // If a function is available for 16x16->32 multiply
count<<=1;
if (n < 32768) n*=2; else count+=1;

如果上述循环重复8次,则该数字的对数基数2将为count/256.如果十次,则计数/ 1024.如果是11,则计数/ 2048.实际上,此函数通过计算n**(2 ^ reps)的2的整数次幂对数来工作,但是中间值被缩放以避免溢出.

Answer 4

死灵术。
我必须对有理数实现对数。

我就是这样做的：

根据维基百科，有哈雷牛顿近似法

可用于非常高精度。

使用牛顿方法，迭代简化为（实现），其三次收敛到 ln(x)，这比泰勒级数提供的要好得多。

// Using Newton's method, the iteration simplifies to (implementation) 
// which has cubic convergence to ln(x).
public static double ln(double x, double epsilon)
{
    double yn = x - 1.0d; // using the first term of the taylor series as initial-value
    double yn1 = yn;

    do
    {
        yn = yn1;
        yn1 = yn + 2 * (x - System.Math.Exp(yn)) / (x + System.Math.Exp(yn));
    } while (System.Math.Abs(yn - yn1) > epsilon);

    return yn1;
}

这不是 C，而是 C#，但我确信任何能够用 C 进行编程的人都能够从中推导出 C 代码。

此外，由于

logn(x) = ln(x)/ln(n)。

因此，您也刚刚实现了 logN。

public static double log(double x, double n, double epsilon)
{
    return ln(x, epsilon) / ln(n, epsilon);
}

其中 epsilon（误差）是最小精度。

现在就速度而言，您可能最好使用 ln-cast-in-hardware，但正如我所说，我使用它作为基础来在以任意精度工作的有理数类上实现对数。

在某些情况下，任意精度可能比速度更重要。

然后，使用有理数的对数恒等式
： logB(x/y) = logB(x) - logB(y)

这里是 C 版本：

// compile with: gcc loga.c -lm -o loga

#include <stdio.h>
#include <math.h>

double ln(double x, double epsilon)
{
    double yn = x - 1.0; // using the first term of the Taylor series as initial-value
    double yn1 = yn;

    do
    {
        yn = yn1;
        yn1 = yn + 2 * (x - exp(yn)) / (x + exp(yn));
    } while (fabs(yn - yn1) > epsilon);

    return yn1;
}

int main()
{
    double x = 2.0; // You can change the values as needed
    double epsilon = 1e-6;
    double result = ln(x, epsilon);

    printf("ln(%lf) = %lf\n", x, result);

    return 0;
}

Answer 5

具有值之间插值的基本表是否会起作用？如果值的范围有限(这可能适用于您的情况 - 我怀疑温度读数范围很大)并且不需要高精度,它可能会起作用.应该很容易在普通机器上测试.

以下是关于函数表表示的许多主题之一:正弦值性能的计算与查找表？