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

Question

I want to find the closest representation of a floating point number in the form N/2**M in python, where N and M are integers. I attempted to use the minimisation function from scipy.optimise but it cannot be confined to the case where N and M are integers.

I ended up using a simple implementation that iterates through values of M and N and finds the minimum, but this is computationally expensive and time consuming for arrays of many numbers, what might be a better way of doing this?

My simple implementation is shown below:

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

Just use the built-in functionality:

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

Note that all non-infinite, non-NaN floats are dyadic rationals, so we can rely on the denominator being an exact power of 2.