如何加快计算速度以找到最接近 N/2**M 形式的表示

Question

我想在 python 中找到最接近 N/2**M 形式的浮点数表示，其中 N 和 M 是整数。我尝试使用 scipy.optimise 中的最小化函数，但它不能局限于 N 和 M 是整数的情况。

我最终使用了一个简单的实现，它遍历 M 和 N 的值并找到最小值，但是对于许多数字的数组来说，这在计算上是昂贵且耗时的，这样做的更好方法是什么？

我的简单实现如下图：

import numpy as np

def ValueRepresentation(X):
    M, Dp = X
    return M/(2**Dp)

def Diff(X, value):
    return abs(ValueRepresentation(X) - value)

def BestApprox(value):
    mindiff = 1000000000
    for i in np.arange(0, 1000, 1):
        for j in np.arange(0, 60, 1):
            diff = Diff([i, j], value)            
            if diff < mindiff:
                mindiff = diff
                M = i
                Dp = j
    return M, Dp

Answer 1

感谢 jasonharper，我意识到我的实现效率低得离谱，可以更简单。

他的方法实现如下图：

def BestApprox_fast(value):
    mindiff = 1000000000
    for Dp in np.arange(0, 32, 1):
        M = round(value*2**Dp)
        if abs(M) < 1000:
            diff = Diff([M, Dp], value)
            if diff < mindiff:
                mindiff = diff
                M_best = M
                Dp_best = Dp
    return M_best, Dp_best

大约快 200 倍。

Answer 2

只需使用内置功能：

In [10]: 2.5.as_integer_ratio()  # get representation as fraction
Out[10]: (5, 2)

In [11]: (2).bit_length() - 1    # convert 2**M to M
Out[11]: 1

请注意，所有非无限、非 NaN 的浮点数都是二元有理数，因此我们可以相信分母是 2 的精确幂。

Answer 3

在给定 M 和 N 的限制的情况下，N/2**M 的范围是一个明确定义的离散数标度：

[0-1000/2^26、501-1000/2^25、501-1000/2^24、... 501-1000/2^1、501-1000/2^0]。

在这个给定的离散集中，不同的子集有不同的accuracy/resolution。第一个子集 [0-1000/2^26] 的精度为 2^-26 或 26 二进制位分辨率。因此，每当给定数字落在相应的连续域 [0,1000/2^26] 中时，可实现的最佳精度为 2^-26。随后，当给定数字超出第一个域但落在域[500/2^25,1000/2^25]时，最佳精度为2^25，对应于第二个子集[501-1000/2^25] ]. （注意离散集和连续域的区别。）

根据上述逻辑，我们知道由 M 定义的最佳准确度取决于给定数字在刻度上的位置。因此我们可以按以下 python 代码实现它：

import numpy as np

limits = 1000.0/2**np.arange(0,61)

a = 103.23    # test value
for i in range(60,-1,-1):
    if a <= limits[i]:
        N = i
        M = round(a * 2**N)
        r = [M, N]
        break

if a > 1000:
    r = [round(a), 0]

此解决方案的执行时间为 O(c)，因此非常适合多次调用。

如何加快计算速度以找到最接近 N/2**M 形式的表示

How to speed up calculation to find closest representation of the form N/2**M

python

performance

minimization