După cum nimeni nu a inventat încă?
există o propunere
Ce am realizat?
Apropierea funcțiilor 2x
Noua versiune a funcției exponentiere
Funcția log2x Apropierea și „specializarea“ exponentiere
concluzie
fount de înțelepciune
După cum nimeni nu a inventat încă?
Nu pot judeca. Probabil, problema modului de a construi rapid un număr real pozitiv, într-o măsură reală arbitrară rezolvată doar despre cât de des ca ridicarea în picioare - și de a lua în sus, cred că, mai mult decât o dată. Cu toate acestea, nu atât de mult timp în urmă, am descoperit cu groază că RTL din cele mai recente versiuni ale Borland Delphi (cum ar fi Delphi 6 și Delphi 7) potrivit pentru decizie nu este mai profesionist decât elev de clasa a cincea harnic, prima dată când se confruntă cu o astfel de problemă.
Aruncati o privire la funcția de alimentare codul sursă al modulului Math, prin amabilitatea Software Borland:
Este demn de remarcat faptul că, în stare bună de a optimiza procesorul este lăsat singur cu o mulțime de ramuri care îl conduc, în final, în general, la decizia notorii a unui al cincilea elev de clasa, și anume, de a formula trivială
Aici, x ** y înseamnă creșterea x la puterea y. o exp (x) = e x **.
Ce e în neregulă cu această abordare a deciziei? În primul rând, un set de instrucțiuni FPU nu include orice operațiune de calcul exp (x), sau de a lua ln logaritm natural (x). Prin urmare, rezultatele calculate în mai multe etape, în timp ce este posibil să mai direct, așa cum va fi prezentat mai jos. În această viteză de calcul scade; În plus, operează o regulă intuitivă, care poate afirma aproximativ după cum urmează: cu cât numărul de operații efectuate pe registrele coprocesor în virgulă mobilă, cu atât mai mare va fi rezultatul și eroarea totală.
Testul a aratat ca mai tarziu, atât Visual C de la Visual Studio .NET, și C ++ Builder 4.5 pune în aplicare exponentiere mai eficient. le-a folosit o variantă conceptual nu este diferită de soluția pe care o propun.
Să luăm un inventar. Ce instrucțiuni coprocessor asociate cu construcția puterii sau prin logaritmare? Iată un scurt fragment din [1] și [2]:
- F2XM1 - calculeaza 2 x-1 **. în cazul în care -1
- FSCALE (putere de două zoom) - de fapt, consideră 2 ** trunc (x). unde trunc (x) înseamnă rotunjire la 0, adică, Valorile pozitive sunt rotunjite în jos, și negativ - în mare.
- FXTRACT - preia mantisa și exponentul unui număr real.
- FYL2X - calculeaza y * log2 (x). unde log2 (x) - x logaritmul bază 2.
- FYL2XP1 - calculeaza y * log2 (x + 1) - (1-1 / sqrt (2))
Aici, în general, și toate. Dar, la prima vedere, acest lucru este suficient pentru a înțelege că problema poate fi rezolvată mai direct decât oferă RTL Borland Delphi.
Într-adevăr, de ce nu să înlocuiască exponent (1) 2? După numărul neperovo nu este un nativ pentru aritmetică binară! apoi a lua
Această expresie pentru x ** y, în conformitate cu cele de mai sus cinci instrucțiuni poate fi reprezentat ca o compoziție a funcțiilor de forma:
Deoarece o singură acțiune nu este posibil să se calculeze f (z), trebuie să ia în considerare acest lucru:
Formula (4) - (6) sunt exprimate în mod natural într-un astfel de cod de asamblare:
Înainte de a rula acest fragment de cod pentru a vă asigura că biții de control în cuvântul de control de rotunjire FPU sunt setate la modul de rotunjire la zero. În Delphi este cel mai ușor de a face folosind funcția SetRoundMode (modulul Math):
Deoarece pe Intel Pentium IV comuta mai multe secventiala între cele două (dar nu mai mult) state ale cuvântului de control al procesorului FPU este mult mai rapid decât modelele anterioare, ne putem aștepta ca, chiar și în situațiile în care necesitatea de a puncta provocarea de această bucată de cod pentru acțiunile care au nevoie în caz contrar, modul de rotunjire, atunci când se lucrează la tehnologia modernă, nu duce la timp suplimentar excesiv. A se vedea. De exemplu, în [3].
Full funcția de cod operațional în Object Pascal arată astfel:
Este logic să se creeze o versiune supraîncărcat a funcției pentru orice argumente de tip FLOATTYPE, deoarece, în practică, de multe ori principalul dezavantaj al funcției de built-in este ca ea (la fel ca toate funcțiile pe care aceasta le solicită) are ca argumente numărul real de tip Extended, ceea ce duce la costuri foarte substanțiale de conversie formate de fișiere pentru încărcarea pe stiva FPU.
Din păcate, câștigul în viteză este absolut nu a simțit. Acest lucru este de înțeles: în conformitate cu apendicele C ( „IA-32 Instrucțiuni latenței și Throughput“) din [3], din acest fragment principal de sarcină de calcul pus pe transcendental (responsabil pentru utilizarea nu destul de corectă a termenului nu se bazează pe mine, și stăpânii intel) exploatarea, și anume - FYL2X, FRNDINT, F2XM1 și FSCALE. Valoarea acestor operațiuni în algoritmul propus, iar numărul total în implementarea funcțiilor ln (x) și exp (x) în RTL Delphi aceeași.
Desigur, ar fi de dorit să se mărească viteza și de calcul. Dar lumea nu este perfectă și va trebui să plătească toate aceeași precizie. De obicei, în fiecare situație există o limită de erori admisibile în calcule. Pentru motive ilustrative, definesc eroarea relativă maximă tolerată = 0,0001 până la 0,1%. De fapt, după cum se va observa din graficele erorii relative, a reușit să realizeze o precizie mai mare.
Mai mult, acțiunile noastre ar trebui să elimine operațiile matematice transcendentale. In mod evident, orice reprezentare a compoziției finale sub formă de operații aritmetice elementare unele funcții indecompozabil în astfel de compoziție este o aproximare a funcției inițiale. Aceasta este, problema este relatată după cum urmează: este necesar să se aducă funcțiile transcendente compoziții ale operațiilor elementare utilizate, rămânând în același timp în limitele acceptabile pentru eroarea.
Apropierea funcțiilor 2x
Această măsură ne va permite să scape o dată și de F2XM1 lung, și prin rularea FSCALE ușor mai repede.
Există modalități infinite pentru funcția aproximativă f (x). Una dintre cele mai computațional simplu - selectarea o precizie corespunzătoare a polinomul g (x) = o x n + o-1-x n + 1. + A1 x + a0. Coeficienții săi poate fi constantă, dar poate într-un fel dependentă de x. În primul caz, coeficienții găsi cu ușurință o metoda celor mai mici pătrate, luând valori ale funcției inițiale la mai multe puncte și corespund cu coeficienți, astfel că, la aceste puncte polinomul ia o valoare cât mai aproape posibil de valorile funcției (TEXTE funcții de aproximare polinomiale și metoda celor mai mici pătrate pot fi găsite în cărți despre cursuri de matematică de calcul sau date experimentale). Simplitatea metodei conduce la un dezavantaj semnificativ: este de calitate proastă, uneori, pentru a identifica tendințele, dar slab reflectă cantitatea caracteristică originală, și, de regulă, crește odată cu scăderea eroare gradul polinomului n. și calcularea vitezei g (x) scade odată cu creșterea n.
Marea alternativă, care să permită suficient precizie pentru a aproxima curbe netede, cum ar fi y = 2 ** x, - apropierea de spline. In termeni simpli (poate prea simplu - să-mi fie specialiști scuzat), spline - o curbă care simulează o formă luată de o tijă elastică, deformată prin fixarea unui punct dat. Se trece printr-un punct predeterminat precis, în timp ce depunerea unor condiții suplimentare, în special condiția de continuitate a doua derivată. Există diferite tipuri de spline. În această lucrare, utilizarea practică suficientă de spline cubi. spline pe fiecare interval între două puncte succesive de referință (în ordine crescătoare a coordonatelor x) (x, f (x)) este descris de un al treilea grad g polinom (x) = a3 x 3 + a2 x 2 + a1 x + a0. în cazul în care un set de coeficienți (a0, a1, a2, a3) fiecare pentru un anumit segment. Căutarea acestor factori - sarcină nu este prea dificil, dar descrierea metodei de soluționare a acesteia este dincolo de domeniul de aplicare al acestui articol. Coeficienții de masă. obținute după luarea în considerare toate observațiile în această secțiune, este atașat la articol.
Așa că mă voi limita la utilizarea valorilor coeficientului obținute de mine. Pentru a asigura acuratețea necesară în intervalul 0<=x <999, мне понадобились в качестве эталонных 2039 точек, которым соответствовали значения x=(i-40)/2. i= 0..2038. Сорок значений на отрицательной полуоси нужны были только для того, чтобы отразить поведение сплайна в этой части плоскости, слегка скорректировав таким образом его вид на остальных отрезках; в вычислениях эти 40 отрезков не участвуют, т.к. для значений x <0 можно воспользоваться (без ощутимого проигрыша в скорости или точности) соотношением 2**(-|x|)=1/(2**|x|).
Pe Exp2 funcția de intrare este doar un argument x - a ridicat la numărul de putere. Cum pot pune în aplicare o funcție?
Iată cum am făcut-o.
În ceea ce privește funcția anterioară, este necesar să se asigure biții de control al instalării în rotunjire la modul de rotunjire zero.
Efectuarea acestui fragment modifică conținutul registrului EAX.
Estimăm eroarea de aproximare. Deoarece rezultatul obținut ca _Power (2 x) (a _Power funcție prezentată la început), cunoscut mai precis decât Exp2 (x), apoi ca ochenki accepta abaterea relativă a ultimei funcție a valorii primului: Epsilon = abs (Exp2 ( x) - _Power (2 x)) / _Power (2 x). Desigur, expresia are sens dacă _Power (2 x)<>0.
Figura 1. Eroarea maximă Exp2 = 2 ** x function (cel puțin 990 x) apropierea nu depășește 0,004%.
Noua versiune a funcției exponentiere
Schimbarea de implementare exponentiere în funcție de apropierea propusă pentru 2 ** x:
Acest cod utilizează FCOMIP de instrucțiuni, care a apărut pentru prima dată în procesoare Pentium Pro. Iubitorii de antichități vor trebui să fie utilizat în locul unei unități de comandă pereche FCOMIP / JE
In schimb FCOMIP / JA - Bloc
În plus, în acest caz, se schimbă EAX registru.
Rezultatele testului sunt prezentate în graficele:
Figura 2. Timp de investiții: New_Power - o nouă caracteristică, de putere - de la RTL Borland Delphi.
Semnătura X-0,511 pe axa x reflectă faptul că testele au fost luate valoare întreagă X, care este apoi adăugat la numărul 0,511, pentru a se asigura că nivelul de bază - numărul nu este un întreg (de exemplu, să ia în considerare posibil caz general).
Linia neagră pe partea de sus a setului rosu - netezită consumatoare de timp funcție de putere, violet peste albastru - funcția New_Power.
Măsurătorile au fost efectuate mari consumatoare de timp, prin intermediul RDTSC (procesoare Pentium), deoarece instrucțiuni:
RDTSC se întoarce în perechea registru EDX: EAX numărul de cicluri de procesor, care au trecut de la ultima resetare (reset). instrucțiuni de cod mașină - 0Fh, 31h.
Eroarea relativă se comportă în mod surprinzător stabil, variind între 0% 0.0040. Prin urmare, valori suficient de reprezentative ale argumentului este stabilit, de exemplu, intervalul (0, 1000).
Se poate observa că eroarea estimată relativă (de fapt - o abatere de la valorile returnate de funcția încorporată) de fapt, nu depășește 0,004%!
În cazul exponentului 17 oscilațiile devin mai des, dar imaginea de ansamblu este aceeași.
Funcția log2x Apropierea și „specializarea“ exponentiere
Logaritm este aproximarea slab folosind spline cubice - sau, mai degrabă, am fost în stare să facă acest lucru, și cu o precizie foarte mare, dar numai la costul de a pierde timp, în comparație cu FYL2X. Cu toate acestea, există ceva ce trebuie luate, și fără a recurge la spline.
După cum se știe, ln funcție (1 + x) | x |<1 разлагается в ряд Тейлора следующим образом:
Dacă valoarea absolută a lui x este suficient de mic, membri ai seriei, pornind de la al treilea, mai degrabă afectează rezultatul slab. Prin urmare, pentru valorile lui x. suficient de aproape 1 (să rămână în erori acceptabile prezentate mai sus, x trebuie să apere 1 nu mai mult de 0,01), calculul log2 (x) = ln (x) / ln (2) = ln (x) * log2 (e ) = ln (1+ (x-1)) * log2 (e) pot fi înlocuite prin calcularea (tt * t / 2) * log2 (e), unde t = x-1.
Acesta permite să construiască o altă versiune a funcției exponentiere pentru valorile de bază apropiate de 1. Nu este FYL2X instrucțiuni, dar în schimb există un bloc de instrucțiuni care sunt marcate cu „*“ (semnul "
„Înseamnă egalitatea aproximativă):
De aceea, noi, în acest caz (x, aproape de 1) reușesc să scape de toate instrucțiunile FPU care aparțin unui grup transcendental, rezultând într-o creștere impresionantă a productivității:
Figura 4. Timp de investiții: New_Power_XNear1 - specializată versiunea New_Power.
Din păcate, creșterea exponentul crește eroarea maximă, rămânând totuși în limitele specificate (adică mai puțin de 0,1%, mai mult - mai puțin de 0,01%), chiar și la rate foarte ridicate:
Astfel, am fost capabili de a obține caracteristicile care depășesc viteza încorporat între două și patru ori cu o eroare de ordinul a 0,004% - 0,01%. Este posibil ca exista o oportunitate pentru o mai bună și mai avantajoasă din punct de vedere al timpului de aproximare a funcțiilor cheltuite; posibil chiar și pe un principiu diferit, și nu, așa cum sa făcut aici (adică, bazat pe raportul x ** y = 2 ** (y * log2 (x))).
Pentru acele cazuri în care mare precizie de calcule, pentru a funcționa, corectarea lipsei de Delphi RTL a fost considerat ca fiind prima piatra de temelie. Fără îndoială, această tendință este, de asemenea, demn de cercetari suplimentare pentru a accelera calculele notorie lente, cu o precizie sporită.
Foarte informativ citiți următoarele documente:
- Intel Architecture Software Manualul dezvoltatorului. Volumul 2, set de instrucțiuni de referință. Poate fi găsit pe site-ul www.intel.com Intel.
- Intel® VTune Analyzer Performance ™, hipertext ajutor. Și, în general, VTune - un instrument excelent pentru a găsi nereguli în program.
- Intel Pentium 4 și Intel Xeon ™ Procesor de optimizare Reference Manual. Tot la fel, pe site-ul Intel.