A figyelem egy számot a tényleges mértékét - Delphi forrásból gyik

Mivel még senki sem találta?
van egy javaslat
Mit értünk el?
Közelítése funkciók 2x
Az új verzió a hatványozást funkció
Közelítése log2x funkció és a „szakosodás” hatványozást
következtetés
kútfeje bölcsesség

Mivel még senki sem találta?

Nem tudom megítélni. Valószínűleg az a probléma, hogyan lehet gyorsan megvalósuljon a valódi pozitív szám tetszőleges valós mértékének megoldott épp olyan gyakran, mint a felkelés - és felkelni, azt hiszem, nem is egyszer. Még nem is olyan régen, rájöttem, a rémület, hogy az RTL a legújabb változat a Borland Delphi (mint a Delphi 6 és Delphi 7) használható döntés nem több szakmai, mint szorgalmas ötödikes, az első alkalommal szembesül egy ilyen probléma.

Vessen egy pillantást a forráskódot teljesítmény függvényében Math modul jóvoltából Borland Software:

Érdemes megjegyezni, hogy a jó érdekében, hogy optimalizálja a processzor egyedül marad a tömeg ágak elvezeti a végén, általában a hírhedt döntés egy ötödik osztályos, nevezetesen, hogy a triviális képlet

Itt x ** y eszközök emelése x a teljesítmény y. egy exp (x) = e ** x.

Mi a baj ezzel a megközelítéssel, hogy a döntést? Először is, egy FPU utasításkészletet nem tartalmaz semmilyen művelet számítási exp (x), vagy természetes logaritmusának ln (x). Ennek megfelelően, az eredmények számított több szakaszban, míg lehetséges, hogy több közvetlen módon, amint azt az alábbiakban bemutatjuk. Ebben a számításban fordulatszám esik; Emellett működik egy intuitív szabály, ami nagyjából a következőképpen fogalmazott: minél nagyobb a végrehajtott műveletek a lebegőpontos koprocesszor nyilvántartások, annál nagyobb lesz az eredménye, és a teljes hiba.

A későbbi vizsgálat azt mutatta, hogy mind a Visual C Visual Studio .NET és C ++ Builder 4.5 végre hatványozást hatékonyabban. Használt nekik egy variáns fogalmilag nem különbözik a megoldás, hogy azt javaslom.

Nézzünk egy leltárt. Mi koprocesszor utasítás kapcsolódó építési a hatalom vagy a logaritmálás? Itt egy rövid részlet az [1] és [2]:

• F2XM1 - kiszámítja 2 ** X-1. ahol -1
• FSCALE (zoom erejét kettő) - sőt, úgy véli, 2 ** TRUNC (x). ahol TRUNC (x) azt jelenti kerekítést 0, azaz, pozitív értékeket lefelé kerekítve, és negatív - nagy.
• FXTRACT - beolvassa a mantissza és exponens egy valós szám.
• FYL2X - kiszámítja Y * log2 (x). ahol log2 (x) - x logaritmusát bázis 2.
• FYL2XP1 - kiszámítja Y * log2 (x + 1) - (1-1 / sqrt (2))

Itt általában minden. De első pillantásra, ez elég ahhoz, hogy megértsük, hogy a problémát meg lehet oldani közvetve vagy közvetlenül kínál RTL Borland Delphi.

Valóban, miért nem helyettesíti a kitevő (1) 2? Miután neperovo szám nem őshonos bináris aritmetikai! akkor kap

Ez a kifejezés az x ** y összhangban a fent említett öt utasításokat lehet képviseli, mint egy készítmény funkciói formájában:

Mivel egyetlen intézkedés nem lehet számítani a f (z), figyelembe kell vennünk a következő:

Általános képletű (4) - (6) a természetben kifejezni, assembler kód:

Futtatása előtt kódrészletet, hogy megbizonyosodjon arról, hogy a vezérlő bit FPU kerekítés ellenőrző szót nullára kerekítési mód. A Delphi a legkönnyebb csinálni használatával SetRoundMode funkció (Math modul):

Mivel az Intel Pentium IV szekvenciális többszörös kapcsolót a kettő között (de nem több) államok ellenőrző szó FPU processzor sokkal gyorsabb, mint a korábbi modellek, azt várhatjuk, hogy olyan helyzetekben is, amikor a szükséges nyomatékot a kihívást, ezt a kódrészletet a műveleteket igénylő különben a kerekítési módot, ha dolgozik a modern technológia, ez nem vezet túlzott további időt. Lásd. Például, a [3].

Teljes működési kód funkciót Object Pascal így néz ki:

Logikus, hogy hozzon létre egy túlterhelt változata a funkció bármilyen típusú FLOATTYPE érveket, mert a gyakorlatban gyakran a fő hátránya a beépített funkció, hogy ő (mint az összes funkciót, hogy felhívja) veszi érvek a tényleges száma típusú Extended, ami igen jelentős költségeket konvertáló fájlformátumairól rakodás a FPU verem.

Sajnos, a nyereség sebesség egyáltalán nem érezhető. Ez érthető: a C. függelékben ( „IA-32 utasítás késleltetési és áteresztő”) a [3], ki ez a fragmens fő számítási terhet helyezni transzcendentális (felelős nem egészen pontos kifejezés használata nem nyugszik rám, és a mesterek intel) művelet, azaz - FYL2X, FRNDINT, F2XM1 és FSCALE. Az összeg ezeket a műveleteket az algoritmus, és a teljes végrehajtási funkciók ln (x) és exp (x) az RTL Delphi ugyanaz.

Természetesen kívánatos lenne növelni a sebességet és a számítástechnika. De a világ nem tökéletes, és akkor meg kell fizetni az összes azonos pontosság. Általában, minden helyzetben van egy határ megengedhető hibákat a számításokat. Szemléltetés céljából, azt határozza meg a maximális megengedhető relatív hibája = 0,0001 0,1%. Sőt, mint látni fogjuk a grafikonok a relatív hiba, hogy sikerült elérni még nagyobb pontossággal.

Továbbá, a cselekvést kell, hogy megszüntesse a transzcendentális matematikai műveleteket. Nyilvánvaló, hogy ábrázolása a végső készítmény formájában elemi aritmetikai műveletek néhány funkciót felbonthatatlanok ilyen készítményben egy közelítése az eredeti funkciót. Azaz, a probléma azt a következőképpen: szükség van ahhoz, hogy a transzcendens függvények használt készítmények elemi műveleteket, míg a fennmaradó elfogadható határokon belül a hiba.

Közelítése funkciók 2x

Ez az intézkedés lehetővé teszi számunkra, hogy megszabaduljon egyszer és hosszú F2XM1, és a futás valamivel gyorsabb FSCALE.

Vannak végtelen módon közelítő függvény f (x). Az egyik számítástechnikailag egyszerű - a kiválasztott alkalmas pontossága a polinom g (x) = egy x n + an-1 x n-1 +. + A1 x + a0. A együtthatók lehetnek állandó, de lehet valamilyen módon függ x. Az első esetben az együtthatók könnyen talál a legkisebb négyzetek módszerével, figyelembe értékei az eredeti funkciója több ponton, és kiegyenlített együtthatók, hogy ezeken a helyeken a polinom értéket vesz fel a lehető legközelebb a függvényértékeket (texte polinom közelítését funkciók és a legkisebb négyzetek módszerével megtalálható könyvek tanfolyamok számítógépes matematika vagy kísérleti adatok). Egyszerűség a módszer vezet jelentős hátránya: néha rossz minőségű trendek azonosítására, de csak gyengén tükrözi az eredeti funkció mennyiség, és mint általában, a hiba növekszik csökkenő fokú polinom n. és kiszámítjuk a sebessége a g (x) csökken N növelésével.

Nagy alternatív, amely lehetővé teszi elég pontosan a sima görbék közelítésére, mint például y = 2 ** x, - közelítés bordákkal. Leegyszerűsítve (talán túl egyszerű - hadd nézhető szakemberek), spline - egy görbét szimuláló formában vett egy rugalmas rúd, deformált rögzítésével egy adott pont. Ez átmegy egy pontosan előre meghatározott ponton, míg benyújtása bizonyos további feltételeket, különösen a feltétel folytonosságának a második derivált. Vannak különféle bordák. Ebben a munkában, elegendő gyakorlati alkalmazása köbös spline. Köbös spline minden intervallum között két egymást követő (növekvő sorrendben a koordinátái x) referenciapontok (x, f (x)) írja le egy harmadik fokú polinom g (x) = a3 x 3 + A2 x 2 + A1 x + a0. ahol egy sor együtthatók (a0, a1, a2, a3) mindegyik egy adott szegmens. A keresést ezek a tényezők - nem túl nehéz feladat, de a módszer leírását az oldat túlmutat ezt a cikket. Táblázat együtthatók. után kapott figyelembe véve az összes megjegyzést, ebben a szakaszban, csatlakozik a cikket.

Szóval szorítkozom használatát együttható értéket kapott engem. Annak érdekében, hogy a szükséges pontosságot el a 0<=x <999, мне понадобились в качестве эталонных 2039 точек, которым соответствовали значения x=(i-40)/2. i= 0..2038. Сорок значений на отрицательной полуоси нужны были только для того, чтобы отразить поведение сплайна в этой части плоскости, слегка скорректировав таким образом его вид на остальных отрезках; в вычислениях эти 40 отрезков не участвуют, т.к. для значений x <0 можно воспользоваться (без ощутимого проигрыша в скорости или точности) соотношением 2**(-|x|)=1/(2**|x|).

A EXP2 funkció bemeneti egyetlen érv x - hatványát számát. Hogyan végre egy funkciót?

Itt van, hogyan csináltam.

Ami az előző funkciót, szükséges, hogy a telepítés biteket kerekítés nullára kerekítési mód.

Művészet ez a töredék nem módosítja a nyilvántartásban EAX.

Úgy becsüljük, a közelítési hiba. Mivel a kapott eredmény, mint egy _Power (2, x) (egy olyan funkció _Power látható az elején), ismert pontosabban, mint EXP2 (x), majd mint ochenki fogadja a relatív eltérés a utolsó funkciója az érték az első: Epsilon = abs (EXP2 ( x) - _Power (2, x)) / _Power (2, x). Természetesen a kifejezés értelme, ha _Power (2 x)<>0.

1. ábra: A legnagyobb hibának a közelítés EXP2 = 2 ** x funkciót (legalább 990 x) nem haladja meg a 0,004%.

Az új verzió a hatványozást funkció

Módosítása hatványozási végrehajtása szerint a javasolt közelítés 2 ** x:

Ez a kód használja az utasítás FCOMIP, amely először a Pentium Pro processzorok. Antik szerelmesei kell használni, hanem egy pár FCOMIP / JE parancs egység

Ehelyett FCOMIP / JA - blokk

Ezen kívül ebben az esetben változik a nyilvántartásban EAX.

Vizsgálati eredmények jelennek meg a grafikonok:

2. ábra Időbefektetés: New_Power - egy új funkció, Power - az RTL Borland Delphi.

Signature X-0,511 az x-tengelyen a tényt tükrözi, hogy a vizsgálatokat vettünk egész érték X, amelyet azután hozzáadjuk a száma 0,511, annak biztosítása érdekében, hogy az alap szinten - a szám nem egész szám (azaz, hogy fontolóra általános eset).

A fekete vonal a tetején a piros set - simított időigényes funkció Power, lila a kék - New_Power funkciót.

Méréseket végeztünk időigényes keresztül RDTSC (processzorok óta Pentium) utasítások:

RDTSC visszatér a nyilvántartásban pár EDX: EAX száma processzor ciklusok óta eltelt az utolsó nullázás (reset). Gépi kódú utasítások - 0Fh, 31h.

Relatív hiba viselkedik meglepően stabil, kezdve 0-,0040%. Ezért, kellően reprezentatív értékeit az érv van állítva, például a (0, 1000).

Látható, hogy a becsült relatív hiba (sőt - az eltérést a visszaadott értékek a beépített funkció) ténylegesen nem haladja meg a 0,004%!

Abban az esetben, a kitevő 17 rezgések egyre gyakrabban, de a teljes kép ugyanaz.

Közelítése log2x funkció és a „szakosodás” hatványozást

Logaritmus rosszul közelítés segítségével harmadfokú spline - vagy inkább, tudtam csinálni, és igen nagy pontossággal, de csak azon az áron, időveszteség képest FYL2X. Azonban van valami, hogy kell venni, és anélkül, hogy spline.

Mint ismeretes, a függvény ln (1 + x) a | x |<1 разлагается в ряд Тейлора следующим образом:

Ha az x abszolút értéke elég kicsi, a sorozat tagjainál, kezdve a harmadik, nem csekély mértékben befolyásolja az eredményt. Ezért az x. kellően közel 1 (belül maradnak elfogadható hibák fent említett, x kell védenie 1 nem több, mint 0,01), a számítás a log2 (x) = ln (x) / ln (2) = ln (x) * log2 (e ) = ln (1+ (X-1)) * log2 (e) lehet cserélni kiszámításával (tt * t / 2) * log2 (e), ahol t = x-1.

Ez lehetővé teszi, hogy egy másik változata a hatványozás funkció az alapértékek közel 1. Nem FYL2X utasításokat, de helyette van egy blokk utasításokat vannak jelölve a „*” (a jel "

„A közelítő egyenlőség):

Ezért ebben az esetben (x, z 1) sikerül megszabadulni minden FPU utasításokat tartozó transzcendentális csoport, így egy lenyűgöző termelékenység növekedése:

4. ábra Időbefektetés: New_Power_XNear1 - speciális változat New_Power.

Sajnos, növelve a kitevőt növeli a maximális hiba, megmarad azonban, meghatározott határokon belül van (azaz kevesebb, mint 0,1%, több, - kisebb, mint 0,01%), még igen magas aránya:

Így tudtuk, hogy a funkciók, amelyek meghaladják a beépített sebesség két és négyszer hiba nagyságrendileg 0,004% - 0,01%. Lehetséges, hogy van egy lehetőség, hogy jobb és előnyösebb szempontjából fordított idő közelítése feladatokat; lehetséges még egy másik elvet, és nem úgy, ahogy ez itt (azaz arány alapján x ** y = 2 ** (y * log2 (x))).

Azokban az esetekben, ahol nagy pontosságú számítások működni, javítása hiánya Delphi RTL tartották, mint az első alapkövet. Kétségtelen, hogy ez a tendencia is érdemes további kutatásokat, hogy felgyorsítsa a közismerten lassú számítások nagyobb pontosságát.

Nagyon informatív olvassa el az alábbi dokumentumokat:

1. Intel® architektúra Software Developer kézikönyv. 2. kötet, utasításkészlete referencia. Megtalálhatók Intel www.intel.com oldalon.
2. Intel® VTune ™ Performance Analyzer, hipertext segítséget. És általában, VTune - egy nagyszerű eszköz megtalálása szabálytalanságok a programban.
3. Intel® Pentium® 4 és Intel® Xeon ™ processzor Optimization Reference Manual. Mindegy, az Intel honlapján.