N/2 형식의 가장 가까운 표현을 찾기 위해 계산 속도를 올리는 방법 ** M

Question

파이썬에서 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

그냥 내장 된 기능 사용

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 2

덕분에 내 구현 엄청나게 비효율적이다 훨씬 더 간단 할 수 실현 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 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 바이너리 비트 해상도입니다. 주어진 숫자가 해당 연속 영역 [0,1000/2^26]에 속할 때마다 달성 할 수있는 최상의 정확도는 2^-26입니다. 주어진 수는 첫 번째 도메인을 벗어 났지만 두 번째 서브 세트 [501-1000/2^25]에 해당하는 [500/2^25,1000/2^25] 도메인에 속할 때 가장 좋은 정확도는 2^25입니다. ]. (이산 집합과 연속 영역의 차이점에 유의하십시오.)

위의 논리를 사용하면 M으로 정의되는 최상의 정확도는 주어진 숫자가 축척에 해당하는 위치에 따라 달라집니다. 따라서 파이썬 코드 다음으로 구현할 수

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)의 실행 시간을 갖는다.