实现根计算功能

| 实现各种功能的数学函数非常简单。 int mul(int,int);，int pow(int,int);，甚至double div(float,float);很容易做到，并且可以通过循环或递归来实现。（这些方法是用手或在头上执行这些功能的相同方法。）要相乘，只需重复将数字相加即可。要进行除法，请反复减去。要获得力量，反复乘以。等等。我一直想知道的一个数学函数是根。例如，您将如何编写一个函数来计算数字（即double root(float num, float root);）的平方根（或立方等）？我尝试环顾四周，却找不到执行此操作的算法或方法。当我尝试手动计算根数时，通常会使用guess方法（从一个近似数开始，加上一个分数，相乘，看看相差多少，再加上一个较小的分数，相乘，再次检查，直到满足为止）。我想这可能行得通，但是肯定有更好的方法，而且更快（无论计算机比手动完成速度快多少）。显然，LUT是无关紧要的，因为它必须足够通用才能接受任何操作数（除非您使用有限的数据集编写游戏）。 Wikipedia文章提到了guess方法，并列出了一些古老的方法（早于发明计算机之前），以及一些纯数学甚至微积分方法（包括一些以“无穷大”为成分的方法）。似乎唯一与电子学有关的东西使用技巧或对数。（这仅适用于平方根，更不用说立方根了。）有没有简单的根计算方法？计算器如何做？电脑如何做到？（不，简单地执行double pow(a,0.5);是行不通的，因为then5将会如何实施？）我只是将根函数与更简单的函数错误地组合了吗？它们比看起来复杂吗？

已邀请:

3 个回复

师埠女

有两种可能性。有两种不同的迭代方法，例如二等分法或牛顿法。就使用ѭ6而言，某些计算机（例如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

但是请注意，您通常不希望仅通过重复加法来实现乘法，也不希望仅通过重复减法来实现除法。相反，您想对连续的2的幂进行移位和加/减，以更快地获得结果。这是一些显示一般想法的代码：

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等）上，这种代码非常普遍。