Mikä aiheuttaa liukulukujen pyöristysvirheitä?

Tämä johtuu siitä, että jotkut murtoluvut tarvitsevat erittäin suuren määrän (tai jopa ääretöntä) paikkoja ilmaistakseen pyöristämättä. Tämä pätee desimaalimerkintöihin yhtä paljon kuin binäärisiin tai muihin. Jos rajoitat laskelmissasi käytettävien desimaalien määrää (ja vältät laskelmien tekemisen murto-osuuksina), joudut pyöristämään jopa yksinkertaisen lausekkeen 1/3 + 1/3. Sen sijaan, että kirjoitat 2/3 tuloksena, sinun on kirjoitettava 0,33333 + 0,333333 = 0,666666, joka ei ole identtinen 2/3: n kanssa.

Tietokoneen tapauksessa numeroiden määrää rajoittaa tekninen luonne muistin ja suorittimen rekistereistä. Sisäisesti käytetty binäärimerkintä lisää vielä joitain vaikeuksia. Tietokoneet eivät tavallisesti voi ”t ilmaista lukuja murto-osuuksina, vaikka jotkut ohjelmointikielet lisäävät tämän kyvyn, mikä mahdollistaa näiden ongelmien välttämisen tietyssä määrin.

Mitä jokaisen tietojenkäsittelytieteen tutkijan tulisi tietää liukulukulaskennasta

Kommentit

• Paikan päällä. Huomaa kuitenkin myös, että jotkut numerot, jotka päättyy desimaaliluvulla don ’ t päättyy binaariin. Erityisesti 0,1 on toistuva luku binaarissa, joten mikään liukulukuinen binääriluku ei voi edustaa tarkasti 0,1.
• Kelluva pisteet eivät ole ’ t vain hyödyllisiä monille desimaaleille. 32-bittisiä kokonaislukuja voidaan laskea vain noin 4 miljardiin, mutta 32-bittinen kelluva voi olla melkein äärettömän suuri.
• Erityisesti murtoluvut, jotka voimme ilmaista rajallisina desimaaleina, ovat ne, joiden nimittäjät ’ alkuluvut sisältävät vain 2 ja 5 (esim. voimme ilmaista 3/10 ja 7/25 , mutta ei 11/18). Kun siirrymme binääriin, menetämme kertoimen 5, jolloin vain diadiset perustelut (esim. 1/4, 3/128) voidaan ilmaista tarkasti.

Pyöristysvirheet johtuvat ensisijaisesti siitä, että kaikkien reaalilukujen ääretön ei voida edustaa tietokoneen rajallisella muistilla , puhumattakaan pienestä osasta muistia, kuten yksi liukuluku muuttuja , joten monet tallennetut numerot ovat vain likimääräiset numerot, jotka niiden on tarkoitus edustaa.

Koska arvoja on vain rajoitettu määrä, jotka eivät arvio ja kaikki lähentämisen ja toisen luvun väliset toiminnot johtavat likiarvoon, pyöristysvirheet ovat melkein väistämättömiä .

Tärkeitä asia on ymmärtää, milloin ne todennäköisesti aiheuttavat ongelman ja ryhtyä toimenpiteisiin riskien lieventämiseksi .

David Goldberg ”olennainen Mitä jokainen tietojenkäsittelijä t Pitäisi tietää liukulukuaritmeikasta (Sun / Oracle on julkaissut uudelleen niiden numeerisen liitteenä Laskentaopas ), jonka thorsten , ACCU journal Ylikuormitus juoksi erinomaisen Richard Harrisin artikkelisarjan Kelluva piste blues .

Sarja alkoi sanalla

• Sinun täytyy ajatella! Ylikuormitus # 99 ( pdf , s.5-10):

Numeerinen mputingilla on monia sudenkuoppia. Richard Harris alkaa etsiä hopeamallia.

Lukuarvovirheen lohikäärmeä ei usein herätetä unestaan, mutta jos lähestytään varovaisesti, hän satunnaisesti aiheuttaa katastrofaalisia vahinkoja varoittamattoman ohjelmoijan laskelmille.

Niin paljon, että jotkut ohjelmoijat, jotka ovat kuullut häntä IEEE 754: n liukulukuaritmeettisissa metsissä, neuvoo kavereitaan olemaan matkustamattomia tuolla hyvällä maalla.

Tässä artikkelisarjassa tutkitaan numeerisen laskennan maailma, vastakohtana liukulaskutoimitukselle joillekin tekniikoille, jotka on ehdotettu turvallisemmiksi korvikkeiksi. Opimme, että lohikäärmeen alue on todella kaukana ja että meidän on yleensä kuljettava varovasti, jos pelkäämme hänen tuhoisa huomio.

Richard aloittaa selittämällä reaalilukujen, rationaalisten, irrationaalisten, algebrallisten ja transsendenttisten, taksonomiaa. Tämän jälkeen hän selittää IEEE754-esityksen, ennen kuin jatkuu peruutusvirheisiin ja suoritusjärjestysongelmiin.

Jos et lue tätä syvempää, sinulla on erinomainen maadoitus liukulukuihin liittyviin ongelmiin. .

Jos haluat kuitenkin tietää enemmän, hän jatkaa kohdalla

• Miksi kiinteä piste ei parantanut kelluvia pisteitäsi Ylikuormitus # 100 ( pdf , s.15-22)
• Miksi perustelut eivät Paranna kelluvia pisteitä sisältävä blues ylikuormitus # 101 ( pdf , s.9-13)
• Miksi tietokonealgebra ei paranna kelluvia pisteitäsi ylikuormitus # 102 ( pdf , s9- 14).
• Miksi intervalliaritmeikka ei paranna kelluvia pisteitäsi Ylikuormitus 103 ( pdf , s.19-24)

Hän siirtyy sitten yrittämään auttaa sinua parantamaan Calculus Blues

• Miksi [Lisää algoritmi tähän] ei paranna hammaskiveäsi Ylikuormitus 104 ( pdf , s. 22–24).
• Miksi rajalliset erot eivät paranna hammaskiveäsi Ylikuormitus 105 ( pdf , s.5–12).
• Miksi polynomilähestyminen voitti kalkkiblusiisi in Ylikuormitus 106 ( pdf , s. 16-25).
• Miksi tietokonealgebra ei paranna hammaskiveäsi Ylikuormitus 107 ( pdf , s. 15-20).

ja viimeisenä mutta ei vähäisimpänä,

• Miksi automaattinen erottelu ei paranna hammaskiveäsi Ylikuormitus 108 ( pdf , s.4-11).

Koko artikkelisarja on tutustumisen arvoinen ja yhteensä 66 sivua, ne ovat silti pienempiä kuin Goldberg -lehden sivut. 77

sarja kattaa suurelta osin saman maan, minusta se oli helpommin saavutettavissa kuin Goldbergin s paperi . Minusta oli myös helpompaa ymmärtää paperin monimutkaisempia osia lukemalla aikaisemmat Richardsin artikkelit ja näiden varhaisartikkeleiden jälkeen Richard haarautuu monille mielenkiintoisille alueille, joita Goldbergin paperi ei koskenut.

Kuten puhui näin ak , joka mainittiin kommenteissa:

Kirjoittajana nuo artikkelit, joista haluaisin mainita, että olen luonut niistä interaktiivisia versioita blogissani www.thusspakeak.com alkaen thusspakeak.com/ak/2013/06 .

Kommentit

• Noiden artikkelien kirjoittajana ’ haluan mainita, että olen luonut niistä interaktiivisia versioita blogissani www.thusspakeak.com aloittaen thusspakeak.com/ak/2013/06 .
• Kiitos @ thusspakea.k. Lisäsin muistiinpanon ’ vastaukselleni, ja tho interaktiiviset elementit toimivat hyvin.

No, thorsten : llä on lopullinen -linkki . Lisään:

Kaikilla esitystavoilla on pyöristysvirhe joillekin numeroille. Yritä ilmaista 1/3 IEEE-liukulukulla tai desimaalilla. Kumpikaan ei voi tehdä sitä tarkasti. Tämä ylittää kysymykseesi vastaamisen, mutta olen käyttänyt tätä nyrkkisääntöä onnistuneesti:

• Säilytä käyttäjän syöttämät arvot desimaaleina (koska he kirjoittivat sen melkein varmasti desimaaliesitykseen – hyvin harvat käyttäjät käyttää binääriä tai hekssiä). Tällä tavoin sinulla on aina tarkka käyttäjän kirjoittama esitys.
• Jos sinun on tallennettava käyttäjän syöttämät murto-osat, tallenna osoittaja ja nimittäjä (myös desimaalina)
• Jos sinulla on järjestelmä, jossa on useita mittayksiköitä samalle määrälle (kuten Celsius / Fahrenheit), ja käyttäjä voi syöttää molemmat, tallentaa syöttämänsä arvon ja yksiköt, joihin ne on syötetty. Älä yritä muuntaa ja tallentaa yhtenä esityksenä, ellet pysty siihen ilman tarkkuuden ja tarkkuuden menetystä. Käytä tallennettuja arvoja ja yksikköjä kaikissa laskelmissa.
• Tallenna koneen luomat arvot IEEE: n liukulukuihin (tämä voi olla luku, joka on luotu elektronisella mittauslaitteella, kuten analogisella anturilla, jossa on A / D-muunnin, tai pyöristämättömän laskutoimituksen tuloksen). Huomaa, että tämä ei päde, jos luet anturia uudelleen sarjaliitännän kautta ja se antaa jo annat arvon desimaalimuodossa (esim. 18,2 C).
• Säilytä käyttäjän näkyvät kokonaismäärät jne. desimaaleina (kuten pankkitili) saldo). Pyöristetään asianmukaisesti, mutta käytä tätä arvoa lopullisena arvona kaikissa tulevissa laskelmissa.

Kommentit

• Lisään: Harkitse mielivaltaisen tarkan matematiikan paketti, kuten ARPREC tai decNumber.
• En tarkoita, että desimaalilla (toisin kuin binäärillä) on paljon hyötyä kokonaislukuille, kuten osoittaja ja murto-osan nimittäjä. Kumpikin voi tallentaa tarkat kokonaislukuarvot, ja binääri on tehokkaampi. ’ maksaa jonkin verran edestakaisen muuntamisen syötteille ja lähdöille, mutta ne ’ voivat todennäköisesti heikentyä fyysisesti suorittamalla I / O.

Näyttää siltä, ettei toistaiseksi ole mainittu epävakaan algoritmin käsitteitä ja sopimaton ongelma . Käsittelen ensin entistä, koska se näyttää olevan yleisempi kuoppa aloitteleville numeerisille.

Harkitse (vastavuoroisen) kultaisen suhteen φ=0.61803…; yksi mahdollinen tapa edetä siinä on käyttää rekursiokaavaa φ^n=φ^(n-2)-φ^(n-1) alkaen φ^0=1 ja φ^1=φ. Jos suoritat tämän rekursio suosikkilaskentaympäristössäsi ja verrataan tuloksia tarkasti arvioituihin tehoihin, huomaat hitaiden merkittävien lukujen eroosion. Tässä tapahtuu esimerkiksi Mathematicassa :

ph = N[1/GoldenRatio]; Nest[Append[#1, #1[[-2]] - #1[[-1]]] & , {1, ph}, 50] - ph^Range[0, 51] {0., 0., 1.1102230246251565*^-16, -5.551115123125783*^-17, 2.220446049250313*^-16, -2.3592239273284576*^-16, 4.85722573273506*^-16, -7.147060721024445*^-16, 1.2073675392798577*^-15, -1.916869440954372*^-15, 3.1259717037102064*^-15, -5.0411064211886014*^-15, 8.16837916750579*^-15, -1.3209051907825398*^-14, 2.1377864756200182*^-14, -3.458669982359108*^-14, 5.596472721011714*^-14, -9.055131861349097*^-14, 1.465160458236081*^-13, -2.370673237795176*^-13, 3.835834102607072*^-13, -6.206507137114341*^-13, 1.004234127360273*^-12, -1.6248848342954435*^-12, 2.6291189633497825*^-12, -4.254003796798193*^-12, 6.883122762265558*^-12, -1.1137126558640235*^-11, 1.8020249321541067*^-11, -2.9157375879969544*^-11, 4.717762520172237*^-11, -7.633500108148015*^-11, 1.23512626283229*^-10, -1.9984762736468268*^-10, 3.233602536479646*^-10, -5.232078810126407*^-10, 8.465681346606119*^-10, -1.3697760156732426*^-9, 2.216344150333856*^-9, -3.5861201660070964*^-9, 5.802464316340953*^-9, -9.388584482348049*^-9, 1.5191048798689004*^-8, -2.457963328103705*^-8, 3.9770682079726053*^-8, -6.43503153607631*^-8, 1.0412099744048916*^-7, -1.6847131280125227*^-7, 2.725923102417414*^-7, -4.4106362304299367*^-7, 7.136559332847351*^-7, -1.1547195563277288*^-6} 

Väitetty φ^41: lla on väärä merkki, ja vielä aikaisemmin, lasketut ja todelliset arvot kohteelle φ^39 eivät jaa yhteisiä numeroita (3.484899258054952 * ^ – 9 for the computed version against the true value 7.071019424062048 *^-9). Algoritmi on siten epävakaa, eikä tätä rekursiokaavaa pidä käyttää epätarkassa aritmeettisuudessa. rekursiokaavan luontainen luonne: tähän rekursioon on olemassa ”hajoava” ja ”kasvava” ratkaisu, ja yrittää laskea ”hajoava” ratkaisu eteenpäin-ratkaisulla, kun on olemassa vaihtoehtoinen ”kasvava” ratkaisu, anoo numeerista surua. On siis varmistettava, että hänen numeeriset algoritmit ovat vakaita.

Seuraavaksi huonosti ehdollistetun ongelman käsite: vaikka siihen voi olla vakaa tapa jotain numeerisesti, voi hyvinkin olla, että ongelma sinä Ve vain ei voida ratkaista algoritmillasi. Tämä on itse ongelman vika eikä ratkaisumenetelmä. Numeerinen kanoninen esimerkki on lineaaristen yhtälöiden ratkaisu, johon liittyy ns. Hilbert-matriisi:

matriisi on kanoninen esimerkki huonosti ehdollistetusta matriisista: Järjestelmän ratkaiseminen suurella Hilbert-matriisilla saattaa antaa epätarkan ratkaisun.

Tässä ”sa Mathematica esittely: vertaa tarkan aritmeettisen tuloksen

Table[LinearSolve[HilbertMatrix[n], HilbertMatrix[n].ConstantArray[1, n]], {n, 2, 12}] {{1, 1}, {1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}} 

ja epätarkan aritmeettisen tuloksen

Table[LinearSolve[N[HilbertMatrix[n]], N[HilbertMatrix[n].ConstantArray[1, n]]], {n, 2, 12}] {{1., 1.}, {1., 1., 1.}, {1., 1., 1., 1.}, {1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1., 1., 1., 1.}, {1., 1., 1., 0.99997, 1.00014, 0.999618, 1.00062, 0.9994, 1.00031, 0.999931}, {1., 1., 0.999995, 1.00006, 0.999658, 1.00122, 0.997327, 1.00367, 0.996932, 1.00143, 0.999717}, {1., 1., 0.999986, 1.00022, 0.998241, 1.00831, 0.975462, 1.0466, 0.94311, 1.04312, 0.981529, 1.00342}} 

(Jos kokeilit sitä Mathematica : ssa, huomaat muutaman virheilmoituksen, joka varoittaa epäsuotuisasta ilmestymisestä.)

Molemmissa tapauksissa yksinkertaisesti lisätä tarkkuus ei ole parannuskeino; se vain viivästyttää kuvien väistämätöntä heikkenemistä.

Tätä saatat kohdata. Ratkaisut saattavat olla vaikeita: ensimmäiseksi joko palaat piirtotaululle tai kahlaat lehtiä / kirjoja / mitä tahansa löytääksesi, jos joku muu on keksinyt paremman ratkaisun kuin sinulla; toiseksi joko luovut tai muotoilet ongelmasi uudelleen käsiteltävämmäksi.

Jätän sinulle lainauksen Dianne O: lta ”Leary:

Elämä saattaa aiheuttaa meille joitain ehdollisia ongelmia, mutta ei ole mitään hyvää syytä tyytyä epävakaaseen algoritmiin.

koska 10 kymmentä desimaalilukua ei voida ilmaista perustassa 2

tai toisin sanoen 1/10 ei voida antaa muunnetaan murtoon, jonka nimellisarvossa on 2 tehoa (mitä liukuluvut olennaisesti ovat)

Kommentit

• Ei totta: 0,5 ja 0,25 voidaan ilmaista tukikohdassa 2. Luulen, että tarkoitat ” kaikkia perus 10 desimaalilukua ”.
• Tarkemmin. Kaikkia murtolukuja ei voida esittää tarkasti liukuluku merkinnällä (eli. Sekä alustalla 2 että alustalla 10 on tämä tarkka ongelma). Kokeile ja tee 9*3.3333333 desimaalilla ja sovita se 9*3 1/3
• Tämä on yleisin kelluvan pisteen lähde sekavuus. .1 + .1 != .2 koska käytetään liukulukuista binäärikoodausta, ei desimaalia.
• @SeanMcMillan: Ja 1.0/3.0*3.0 != 1.0, koska kelluva Käytetään binääristä koodauskoodausta, ei kolmikomponenttia.

Matematiikassa on äärettömän paljon rationaalilukuja . 32-bittisellä muuttujalla voi olla vain 2 ³² -arvoa ja 64-bittisellä muuttujalla vain 2 ⁶⁴ -arvoa. Siksi on äärettömän monia rationaalilukuja, joilla ei ole tarkkaa esitystä.

Voisimme keksiä kaavoja, joiden avulla voimme edustaa 1/3 täydellisesti eli 1/100. Osoittautuu, että monista käytännön tarkoituksista tämä ei ole kovin hyödyllistä. On yksi iso poikkeus: finanssissa desimaalimurtoluvut tulevat usein esiin. Se johtuu pääasiassa siitä, että rahoitus on lähinnä ihmisen toimintaa, ei fyysistä toimintaa.

Siksi päätämme yleensä käyttää binaarista liukulukua ja pyöristää minkä tahansa arvon, jota ei voida edustaa binaarisena. Mutta rahoituksessa valitsemme joskus desimaalin liukuluvun ja pyöristetyt arvot lähimpään desimaalilukuun .

Kommentit

• Vielä pahempaa, vaikka ääretön (laskemattoman ääretön) määrä muistia antaisi mahdollisuuden edustaa kaikkia järkeistyksiä, se ei riittää reaalien edustamiseen. Vielä pahempaa on, että melkein kaikki reaaliluvut eivät ole laskettavissa olevia numeroita. Parasta, mitä voimme tehdä rajallisella muistimäärällä, on arvioida realien rajallinen alue.
• @Kevin: Sinä ’ puhut laskettavissa olevista luvuista, joka on pieni reaalialaryhmä (osajoukko, jonka mitta on nolla).
• +1 perustavanlaatuisin selitys: Yrität ’ edustaa ääretöntä määrää numeroita, joilla on rajallinen määrä bittejä.
• @DavidHammen: Laskettavat luvut ovat pieni osajoukko ( mitattuna nolla) realiteista – mutta jokainen luku, jonka kanssa ’ koskaan työskentelet ohjelmassa, on määritelmän mukaan laskettavissa.
• @Giorgio: Jos valitset oikean esityksen, 2: n neliöjuuri on edustettavissa esimerkiksi merkkijonona "√2". (Vanha HP-48-laskin pystyi tekemään juuri tämän, ja kyseisen arvon neliöiminen johti tarkalleen 2.0.) mille tahansa edustavalle reaaliluvulle on vain lukematon ääretön määrä äärellinen edustus – mutta mikään laskenta ei voi tuottaa lukua, jota ei periaatteessa voida edustaa. Käytännössä binaarinen liukuluku rajoittaa merkittävästi edustettavien lukujen joukkoa, hyödyksi räjähtävän nopeuden ja pienen varastoinnin suhteessa symbolisiin esityksiin.

ainoa todella ilmeinen ”pyöristyskysymys” liukulukuilla on mielestäni liukuvien keskiarvojen suodattimien kanssa:

$$ \ begin {align} y [n] & = \ frac {1} {N} \ summa \ limits_ {i = 0} ^ {N-1} x [ni] \ & = y [n-1] + \ frac {1} {N} (x [n] – x [nN]) \ \ end {tasaa} $$

saadaksesi tämän toimimaan ilman melun kertymisen vuoksi haluat varmistaa, että nykyisiin näytteisiin lisäämäsi $ x [n] $ on täsmälleen sama kuin $ x [nN] $, vähennät $ N $ -näytteet tulevaisuuteen. jos se ei ole, niin erilainen on pieni muru, joka jumittuu viivästyslinjaasi eikä tule koskaan ulos. Tämä johtuu siitä, että tämä liikkuva keskiarvosuodatin on tosiasiallisesti rakennettu IIR: llä, jolla on marginaalin vakaa napa $ z = 1 $ ja nolla, joka poistaa sen sisältä. mutta se on integraattori, ja kaikki paska, joka integroituu ja jota ei poisteta kokonaan, on olemassa integraattorisummassa ikuisesti. Tällöin kiinteällä pisteellä ei ole samaa ongelmaa kuin liukulukuilla.

Kommentit

• hei, ei ’ t $ LaTeX $ matematiikan merkinnät toimivat prog.SE-foorumilla ??? että ’ on todella ontuva, jos se ei ’ t.
• Katso tämä meta.SO: ssa ja linkitetyt kysymykset