实现求根函数

发布于 2024-11-14 22:55:46 字数 928 浏览 6 评论 0原文

为各种事物实现数学函数非常简单。 int mul(int,int);、int pow(int,int);，甚至 double div(float,float); 都很简单to do 可以用循环或递归来实现。（这些方法与用手或头脑执行这些功能的方法相同。）要进行乘法，只需重复将数字相加即可。要进行除法，请重复减去它。要获得力量，请反复相乘。等等。

然而，我一直想知道的一个数学函数是根。例如，您将如何编写一个函数来计算数字的平方（或立方等）根（即，double root(float num, float root);）？我尝试环顾四周，但找不到执行此操作的算法或方法。

当我尝试手动计算根时，我通常使用猜测方法（从一个近似数开始，添加一个分数，相乘，看看相差多远，添加一个更小的分数，相乘，再次检查，然后重复直到满意为止））。我认为这可行，但肯定有更好、更快的方法（无论计算机比手工快多少）。

显然 LUT 是不相关的，因为它必须足够通用才能接受任何操作数（除非您正在使用有限的数据集编写游戏）。维基百科文章提到了猜测方法并列出了一些古老的方法（早在计算机发明之前）：以及一些纯数学甚至微积分方法（包括一些以“无穷大”为组成部分的方法）。唯一与电子学有关的似乎是使用技巧或对数。（这只是平方根，更不用说立方根等了。）

有没有简单的根计算方法？计算器是如何做到这一点的？计算机是如何做到的？（不，简单地执行 double pow(a,0.5); 是行不通的，因为那么如何实现 double pow(float,float) ？）

我只是不正确吗将根函数与更简单的函数分组？它们比看起来更复杂吗？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

沩ん囻菔务 2024-11-21 22:55:46

有几种可能性。有几种不同的迭代方法，例如二分法或牛顿法。就使用 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

但是请注意，您通常不想通过重复加法来实现乘法，或者通过重复减法来实现除法。相反，您希望通过移位和加/减连续的 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 等）上，这样的代码相当常见。

There are a couple of possibilities. There are a couple of different iterative approaches, such as bisection or Newton's. As far as using pow goes, some computers (x86, for example) have an instruction to do (at least part of) raising a number to a power, so it's purely a matter of writing a bit of framework around that.

Here's an assembly language implementation of Newton's method for a square root, in this case working only with 16-bit integers, but the same basic idea applies to other types. I wrote this around 20 years ago, so it was for 16-bit CPUs with no floating point hardware.

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

Here's some code for an x87 to compute arbitrary powers:

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

Note, however, that you don't normally want to implement multiplication by just repeatedly adding, or division by just repeatedly subtracting. Rather, you want to shift and add/subtract successive powers of two to get the result much more quickly.

Here's some code that shows the general idea:

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

This is pretty pointless for x86, because it has multiplication instructions built in, but on older processors (PDP-11, 8080, 6502, etc.) code like this was quite common.

回复收藏 0 原文