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

Question

我想在python中找到最接近的浮点数表示形式N/2**M，其中N和M是整数。我试着使用科学优化但它不能局限于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]. 你知道吗

在这个给定的离散集合中，不同的子集具有不同的精度/分辨率。第一个子集[0-1000/2^26]的精度为2^26或26二进制位分辨率。因此，当给定的数字落在相应的连续域[01000/2^26]时，可以达到的最佳精度是2^26。依次地，当给定的数字超出第一个域但落在域[500/2^251000/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）执行时间，因此非常适合多次调用。你知道吗