python - 不使用除法运算符的浮点除法

Question

Given two positive floating point numbers x and y, how would you compute x/y to within a specified tolerance e if the division operator cannot be used?

You cannot use any library functions, such as log and exp; addition and multiplication are acceptable.

请问我该如何解决？我知道解决除法的方法是使用按位运算符，但在这种方法中，当 x 小于 y 时，循环停止。

def divide(x, y):
    # break down x/y into (x-by)/y + b , where b is the integer answer
    # b can be computed using addition of numbers of power of 2
    result = 0
    power = 32
    y_power = y << power 
    while x >= y:
        while y_power > x:
            y_power = y_power>> 1
            power -= 1
        x = x - y_power
        result += 1 << power
    return result

Answer 1

一种选择是使用已知以二次方式收敛的 Newton-Raphson 迭代(因此精确位数将像 1、2、4、8、16、32、64 一样增长)。

首先用迭代计算y的倒数

z(n+1) = z(n) (2 - z(n) y(n)),

并收敛后形成积

x.z(N) ~ x/y

但挑战在于找到一个好的起始近似值 z(0)，它应该在 1/y 的因子 2 内.

如果上下文允许，您可以直接使用浮点表示的指数并将 Y.2^e 替换为 1.2^-e 或 √2.2^-e.

如果不允许这样做，你可以预先建立一个2的所有可能的幂的表，并执行二分法搜索以在表中定位y。然后在表中很容易找到逆幂。

对于 double float ，有 11 个指数位，因此幂表应该包含 2047 个值，这可以认为很多。您可以通过仅存储指数 2^0、2^±1、2^±2、2 来用存储换取计算^±3... 然后在二分搜索期间，您将通过产品(即 2^5 = 2^4.2^1)按需重新创建中间指数，并在同时，形成逆的乘积。这可以高效地完成，仅使用 lg(p) 乘法，其中 p=|lg(y)| 是所需的幂。

示例:查找 1000 的幂；指数以二进制表示。

1000 > 2^1b = 2
1000 > 2^10b = 4
1000 > 2^100b = 16
1000 > 2^1000b = 256
1000 < 2^10000b = 65536

然后

1000 < 2^1100b = 16.256 = 4096
1000 < 2^1010b = 4.256 = 1024
1000 > 2^1001b = 2.256 = 512

这样

2^9 < 1000 < 2^10.

现在 Newton-Raphson 迭代产出

z0 = 0.001381067932
z1 = 0.001381067932 x (2 - 1000 x 0.001381067932) = 0.000854787231197
z2 = 0.000978913251777
z3 = 0.000999555349049
z4 = 0.000999999802286
z5 = 0.001