So beschleunigen Sie die Berechnung, um die nächste Darstellung der Form zu finden N/2 ** M

Question

Ich möchte die nächste Darstellung einer Gleitkommazahl in der Form N/2 ** M in Python finden, wo N und M sind ganze Zahlen. Ich habe versucht, die Minimierungsfunktion von scipy.optimise zu verwenden, aber es kann nicht auf den Fall beschränkt werden, wo N und M Ganzzahlen sind.

Ich endete mit einer einfachen Implementierung, die durch Werte von M und N iteriert und findet das Minimum, aber das ist rechenintensiv und zeitaufwendig für Arrays aus vielen Zahlen, was könnte eine bessere Möglichkeit, dies zu tun?

Meine einfache Implementierung ist unten dargestellt:

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

Verwenden Sie einfach die integrierte Funktionalität:

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 

Beachten Sie, dass alle nicht unendlich, nicht-NaN Schwimmer dyadic rationals sind, so können wir auf den Nenner verlassen eine genaue Potenz von 2

ist

Answer 2

Dank jasonharper ich meine Implementierung realisiert lächerlich ineffizient und könnte viel einfacher sein.

Die Umsetzung seiner Methode ist unten dargestellt:

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 

Es ca. 200-mal schneller ist.

Answer 3

Mit den angegebenen Grenzwerten für M und N ist der Bereich von N/2 ** M eine gut definierte diskrete Zahlenskala:

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

In diesem gegebenen diskreten Satz haben verschiedene Teilmengen unterschiedliche Genauigkeit/Auflösung. Die erste Teilmenge [0-1000/2^26] hat eine Genauigkeit von 2^-26 oder 26 Bit-Auflösung. Wenn also die gegebene Zahl in die entsprechende kontinuierliche Domäne fällt [0,1000/2^26], ist die erreichbare höchste Genauigkeit 2^-26. Sukzessiv ist die beste Genauigkeit 2^25, wenn die gegebene Zahl jenseits der ersten Domäne liegt, aber in Domäne [500/2^25,1000/2^25] fällt, was der zweiten Teilmenge [501-1000/2^25 entspricht ]. (Beachte den Unterschied zwischen diskreten und kontinuierlichen Domänen.)

Mit der obigen Logik wissen wir, dass die beste Genauigkeit, definiert durch M, davon abhängt, wo die gegebene Zahl auf die Skala fällt. So können wir es als folgende Python-Code implementieren:

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] 

Diese Lösung hat O (c) Ausführungszeit, so ist es ideal für mehrere Anrufungen ist.