实现根计算功能

为各种事情实现数学函数非常简单。 int mul(int,int);,int pow(int,int);，甚至double div(float,float);很容易做到，可以用循环或递归实现。（这些方法与手动或头部执行这些功能的方法相同。）要相乘，只需重复添加数字即可。分割，重复减去它。获得力量，反复倍增。等等。实现根计算功能

然而，我一直想知道的一个数学函数是根。例如，你将如何编写一个函数来计算一个数字的平方（或立方体等）根（即，double root(float num, float root);）？我试图环顾四周，找不到这样做的算法或方法。

当我尝试手工计算根目录时，我通常使用猜测方法（从一个近似数开始，添加一个分数，乘，看它有多远，添加一个更小的分数，再乘以，再次检查，并重复直到满意）。我认为这可以奏效，但肯定会有更好更快的方法（不管计算机能做多少手动）。

显然，LUT并不相关，因为它必须具有足够的通用性才能接受任何操作数（除非您正在编写一组有限数据的游戏）。 Wikipedia article提到了猜测方法，并列出了一些古代的（早在计算机发明之前）以及一些纯粹的数学甚至微积分方法（包括一些具有“无限”作为组分的方法）。似乎与电子产品有关的唯一一些使用技巧或逻辑运算符。（这只是为平方根，更不用说立方体根，等等。）

有没有简单的根计算方法？计算器如何做到这一点？电脑如何做到这一点？（不，只是做double pow(a,0.5);将无法正常工作，因为那么double pow(float,float)将如何实施？）

我只是错误地将根函数与更简单的函数分组？他们比看起来更复杂吗？

来源

2011-06-12 Synetech

有一个简单的实现N-th root algorithm直接链接从你说的文章。它来源于Newton's method。

来源

2011-06-12 06:58:37 Mat

有几种可能性。有几种不同的迭代方法，比如二分法或牛顿法。就使用pow而言，有些计算机（例如x86）有一个指令要做（至少部分）以提高数量，所以纯粹是围绕这一点写一些框架。

这里是一个用于平方根的牛顿法的汇编语言实现，在这种情况下只用16位整数，但是其他类型的基本思想也适用。我在20年前写了这篇文章，因此它是针对没有浮点硬件的16位CPU。

isqrt proc uses di, number:word 
; 
; uses bx, cx, dx 
; 
    mov di,number 
    mov ax,255 
start_loop: 
    mov bx,ax 
    xor dx,dx 
    mov ax,di 
    div bx 
    add ax,bx 
    shr ax,1 
    mov cx,ax 
    sub cx,bx 
    cmp cx,2 
    ja start_loop 
    ret 
isqrt endp

下面是一些代码为的x87计算任意的权力：

pow proc 
    ; x^y = 2^(log2(x) * y) 
    fyl2x  
    fld st(0) 
    frndint 
    fld1  
    fscale 
    fxch st(2) 
    fsubrp 
    f2xm1  
    fld1  
    faddp  
    fmulp  
    ret 
endp

但是请注意，你通常不希望落实只是一再增加乘法，或者除以只是反复减去。相反，你想要移动和加/减两个连续的幂，以更快地得到结果。

下面是一些代码，显示了总体思路：

mult proc 
; multiplies eax by ebx and places result in edx:ecx 
    xor ecx, ecx 
    xor edx, edx 
mul1: 
    test ebx, 1 
    jz mul2 
    add ecx, eax 
    adc edx, 0 
mul2: 
    shr ebx, 1 
    shl eax, 1 
    test ebx, ebx 
    jnz mul1 
done: 
    ret 
mult endp

这是x86的很没有意义的，因为它有内置的乘法指令，但在旧的处理器（PDP-11，8080，6502，等等。）这样的代码是相当常见。

来源

2011-06-12 07:04:02

是的，不要通过重复添加来进行乘法或除法。这是非常多尘，但http://moneybender.com/transactor_article.pdf。 – 2013-08-08 20:48:40

这取决于你想成为多么一般。如果你想计算，例如，（-4.2）^0.23，你将需要复杂的算术。正如Mat指出的，对于整数n和正x来说，有快速算法来计算x ^1/n。如果你想让x ^y为正数x和任何y，那么日志和指数就可以工作。

来源

2011-06-12 07:04:10

实现根计算功能

回答

相关问题