algorithm - 实现求根功能

Question

为各种事物实现数学函数非常简单。 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) 将如何实现？)

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

Answer 1

有两种可能性。有几种不同的迭代方法，例如二分法或牛顿法。就使用 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 等)上，这样的代码很很常见。 p>