Vraag Is zwevende-punten wiskunde gebroken?


Beschouw de volgende code:

0.1 + 0.2 == 0.3  ->  false
0.1 + 0.2         ->  0.30000000000000004

Waarom gebeuren deze onnauwkeurigheden?


2259
2018-02-25 21:39


oorsprong


antwoorden:


binair zwevend punt wiskunde is zo. In de meeste programmeertalen is het gebaseerd op de IEEE 754-norm. JavaScript gebruikt 64-bits drijvende-kommaweergave, hetzelfde als Java's double. De crux van het probleem is dat getallen in dit formaat worden gerepresenteerd als een geheel getal maal een macht van twee; rationale getallen (zoals 0.1, dat is 1/10) waarvan de noemer geen macht van twee is, kan niet exact worden weergegeven.

Voor 0.1 in de standaard binary64 formaat, de weergave kan precies zo worden geschreven als

  • 0.1000000000000000055511151231257827021181583404541015625 in decimaal, of
  • 0x1.999999999999ap-4 in C99 hexfloat-notatie.

In tegenstelling, het rationele nummer 0.1, dat is 1/10, kan precies zo worden geschreven als

  • 0.1 in decimaal, of
  • 0x1.99999999999999...p-4 in een analoog van C99 hexfloat notatie, waarbij de ... vertegenwoordigt een oneindige reeks van negenen.

De constanten 0.2 en 0.3 in uw programma zullen ook een benadering zijn van hun ware waarden. Het gebeurt dat het dichtst double naar 0.2 is groter dan het rationale getal 0.2 maar dat komt het dichtst in de buurt double naar 0.3 is kleiner dan het rationale getal 0.3. De som van 0.1 en 0.2 wordt groter dan het rationele getal 0.3 en daarom het niet eens zijn met de constante in uw code.

Een vrij uitgebreide behandeling van drijvende-kommaberekeningen is Wat elke computerwetenschap moet weten over drijvende-komma aritmetica. Zie voor een beter verteerbare uitleg floating-point-gui.de.


1718
2018-04-18 11:52



Het perspectief van een hardwarepromoter

Ik geloof dat ik hier het perspectief van een hardwarepromotor aan moet toevoegen omdat ik zwevende-komma-hardware ontwerp en bouw. Het kennen van de oorsprong van de fout kan helpen bij het begrijpen van wat er in de software gebeurt, en uiteindelijk hoop ik dat dit helpt uitleggen waarom er drijvende-kommawfouten optreden en zich in de loop van de tijd lijken te accumuleren.

1. Overzicht

Vanuit technisch oogpunt zullen de meeste drijvende-kommabewerkingen een fout bevatten, omdat de hardware die de drijvende-komma-berekeningen uitvoert, alleen op de laatste plaats een fout van minder dan de helft van één eenheid hoeft te hebben. Daarom zal veel hardware stoppen met een precisie die alleen nodig is om een ​​fout van minder dan de helft van een eenheid op te leveren in de laatste plaats voor een enkele bewerking wat vooral problematisch is in drijvende-komma-verdeling. Wat een enkele bewerking vormt, hangt af van het aantal operanden dat de eenheid inneemt. Voor de meesten zijn het er twee, maar sommige eenheden nemen 3 of meer operanden. Daarom is er geen garantie dat herhaalde bewerkingen een gewenste fout tot gevolg zullen hebben, omdat de fouten na verloop van tijd toenemen.

2. Normen

De meeste processors volgen de IEEE-754 standaard maar sommige gebruiken gedenormaliseerd, of verschillende normen . Er is bijvoorbeeld een gedenormaliseerde modus in IEEE-754 die de weergave van zeer kleine drijvende-kommawaarden ten koste van de nauwkeurigheid mogelijk maakt. Het volgende heeft echter betrekking op de genormaliseerde modus van IEEE-754, wat de typische werkingsmodus is.

In de IEEE-754-standaard hebben hardware-ontwerpers elke waarde van fout / epsilon toegestaan, op voorwaarde dat het minder dan de helft van één eenheid is in de laatste plaats, en het resultaat slechts minder dan de helft van één eenheid in de laatste plaats hoeft te zijn plaats voor één operatie. Dit verklaart waarom als er herhaalde bewerkingen zijn, de fouten kloppen. Voor IEEE-754 dubbele precisie is dit de 54e bit, aangezien 53 bits worden gebruikt om het numerieke deel (genormaliseerd), ook wel de mantisse genoemd, van het drijvende-kommagetal (bijvoorbeeld de 5.3 in 5.3e5) weer te geven. In de volgende secties wordt dieper ingegaan op de oorzaken van hardwarefouten bij verschillende drijvende-kommabewerkingen.

3. Oorzaak van afrondingsfout in divisie

De voornaamste oorzaak van de fout bij drijvende-komma-deling zijn de delingalgoritmen die worden gebruikt om het quotiënt te berekenen. De meeste computersystemen berekenen de verdeling met behulp van vermenigvuldiging door een inverse, voornamelijk in Z=X/Y, Z = X * (1/Y). Een deling wordt iteratief berekend, d.w.z. elke cyclus berekent enkele bits van het quotiënt tot de gewenste precisie is bereikt, hetgeen voor IEEE-754 alles is met een fout van minder dan één eenheid op de laatste plaats. De tabel met reciprocals van Y (1 / Y) staat bekend als de quotiëntselectietabel (QST) in de langzame scheiding en de grootte in bits van de quotiëntselectietabel is gewoonlijk de breedte van de radix, of een aantal bits van het quotiënt berekend in elke iteratie, plus een paar bewakingsbits. Voor de IEEE-754-standaard, dubbele precisie (64-bit), zou dit de grootte zijn van de radix van de verdeler plus enkele bewakingsbits k, waarbij k>=2. Dus bijvoorbeeld, een typische Quotient Selection Table voor een deler die 2 bits van het quotiënt per keer berekent (radix 4) zou 2+2= 4 bits (plus een paar optionele bits).

3.1 Divisie-afrondingsfout: aanpassing van wederkerig

Welke reciprocals in de quotiëntselectietabel zijn, is afhankelijk van de divisiemethode: trage divisie zoals SRT divisie of snelle divisie zoals Goldschmidt divisie; elke invoer wordt aangepast volgens het delingalgoritme in een poging om de laagst mogelijke fout op te leveren. In elk geval zijn echter alle reciprocals benaderingen van het werkelijke reciprocal en introduceer een element van fouten. Zowel de methoden voor langzame verdeling en snelle verdeling berekenen het quotiënt iteratief, dat wil zeggen dat een bepaald aantal bits van het quotiënt elke stap wordt berekend, waarna het resultaat wordt afgetrokken van het dividend en de deler de stappen herhaalt totdat de fout kleiner is dan de helft van een eenheid op de laatste plaats. Langzame werkdelingsmethoden berekenen een vast aantal cijfers van het quotiënt in elke stap en zijn meestal minder duur om te bouwen, en snelle delingmethoden berekenen een variabel aantal cijfers per stap en zijn meestal duurder om te bouwen. Het belangrijkste deel van de divisiemethoden is dat de meeste van hen vertrouwen op herhaalde vermenigvuldiging met een benadering van een reciprocal, dus ze zijn gevoelig voor fouten.

4. Afrondingsfouten in andere bewerkingen: Truncatie

Een andere oorzaak van de afrondingsfouten in alle bewerkingen zijn de verschillende manieren van afkappen van het uiteindelijke antwoord dat IEEE-754 mogelijk maakt. Er is truncate, round-into-zero, van ronde naar dichtstbijzijnde (standaard), afgerond en afgerond. Alle methoden introduceren in de laatste plaats een foutelement van minder dan één eenheid voor een enkele bewerking. Na verloop van tijd en herhaalde bewerkingen, voegt truncatie ook cumulatief toe aan de resulterende fout. Deze truncatiefout is vooral problematisch bij exponentiatie, wat een vorm van herhaalde vermenigvuldiging inhoudt.

5. Herhaalde bewerkingen

Omdat de hardware die de drijvende-komma-berekeningen uitvoert slechts een resultaat hoeft te geven met een fout van minder dan de helft van een eenheid op de laatste plaats voor een enkele bewerking, zal de fout bij herhaalde bewerkingen toenemen als deze niet wordt bekeken. Dit is de reden dat wiskundigen in berekeningen die een begrensde fout vereisen, methoden gebruiken zoals het gebruik van de round-to-nearest zelfs cijfers op de laatste plaats van IEEE-754, omdat na verloop van tijd de kans groter is dat de fouten elkaar opheffen, en Interval Rekenen gecombineerd met variaties van de IEEE 754 afrondingsmodi om afrondingsfouten te voorspellen en te corrigeren. Vanwege de lage relatieve fout in vergelijking met andere afrondingsmodi, is ronde naar het dichtstbijzijnde even cijfer (in de laatste plaats) de standaard afrondingsmodus van IEEE-754.

Merk op dat de standaard afrondingsmodus, van de dichtstbijzijnde naar de dichtstbijzijnde zelfs cijfers op de laatste plaats, garandeert een fout van minder dan de helft van een eenheid op de laatste plaats voor één bewerking. Het alleen gebruiken van de truncatie, round-up en round down kan resulteren in een fout die groter is dan de helft van een eenheid op de laatste plaats, maar minder dan één eenheid op de laatste plaats, dus deze modi worden niet aanbevolen tenzij ze gebruikt in Interval Arithmetic.

6. Samenvatting

Kortom, de fundamentele reden voor de fouten bij drijvende-kommabewerkingen is een combinatie van de truncatie in hardware en de afkapping van een reciprook in het geval van deling. Omdat de IEEE-754-standaard slechts één fout van minder dan de helft van één eenheid vereist op de laatste plaats voor een enkele bewerking, worden de zwevende-komma-fouten over herhaalde bewerkingen opgeteld tenzij gecorrigeerd.


490
2018-02-25 21:43



Wanneer u .1 of 1/10 converteert naar basis 2 (binair) krijgt u een herhalend patroon achter de komma, net als proberen om 1/3 in base 10 weer te geven. De waarde is niet exact en daarom kunt u niet doen exacte wiskunde ermee met behulp van normale drijvende-komma-methoden.


356
2017-11-20 02:39



De meeste antwoorden hier behandelen deze vraag in zeer droge, technische termen. Ik zou dit willen aanpakken in termen die normale mensen kunnen begrijpen.

Stel je voor dat je pizza's wilt snijden. Je hebt een robotachtige pizzasnijder die pizzapunten kan snijden precies door de helft. Het kan een hele pizza halveren, of het kan een bestaande plak halveren, maar in elk geval is de halvering altijd exact.

Die pizzasnijder heeft hele fijne bewegingen, en als je begint met een hele pizza, dan die halveer, en je blijft elke keer de kleinste snede halveren, dan kun je de halvering doen 53 keer voordat het segment te klein is, zelfs voor zijn zeer nauwkeurige vaardigheden. Op dat moment kun je die hele dunne plak niet langer halveren, maar moet je deze insluiten of uitsluiten zoals hij is.

Hoe zou je alle plakjes op zo'n manier verdelen dat dit zou oplopen tot een tiende (0.1) of een vijfde (0.2) van een pizza? Denk er echt over na en probeer het uit te werken. Je kunt zelfs een echte pizza proberen als je een mythische precisie-pizzasnijder bij de hand hebt. :-)


De meeste ervaren programmeurs weten natuurlijk het echte antwoord, namelijk dat er geen manier is om een ​​stuk samen te stellen exact tiende of vijfde van de pizza met die plakjes, het maakt niet uit hoe fijn je ze snijdt. Je kunt een goede benadering doen, en als je bij benadering 0,2 optelt, krijg je een redelijk goede benadering van 0,3, maar het blijft gewoon dat, een benadering.

Voor dubbele precisienummers (dit is de precisie waarmee u uw pizza 53 keer kunt halveren), zijn de getallen onmiddellijk kleiner en groter dan 0,1 0.09999999999999999167332731531132594682276248931884765625 en 0.1000000000000000055511151231257827021181583404541015625. De laatste is een beetje dichter bij 0,1 dan de eerste, dus een numerieke parser zal, gegeven een input van 0,1, de laatstgenoemde begunstigen.

(Het verschil tussen deze twee getallen is de "kleinste snede" die we moeten kiezen om op te nemen, wat een opwaartse bias introduceert, of uitsluit, wat een neerwaartse bias introduceert. De technische term voor die kleinste snee is een ulp.)

In het geval van 0.2 zijn de getallen allemaal hetzelfde, net opgeschaald met een factor 2. Nogmaals, we geven de voorkeur aan de waarde die iets hoger is dan 0,2.

Merk op dat in beide gevallen de benaderingen voor 0.1 en 0.2 een lichte opwaartse vertekening vertonen. Als we genoeg van deze vooroordelen toevoegen, zullen ze het aantal steeds verder weg duwen van wat we willen, en in feite is in het geval van 0.1 + 0.2 de bias hoog genoeg dat het resulterende aantal niet meer het dichtstbijzijnde getal is tot 0,3.

In het bijzonder is 0,1 + 0,2 werkelijk 0,1000000000000000055511151231257827021181583404541015625 + 0,200000000000000011102230246251565404236316680908203125 = 0,3000000000000000444089209850062616169452667236328125, terwijl het getal dat het dichtst bij 0,3 ligt in werkelijkheid 0,299999999999999988897769753748434595763683319091796875 is.


Postscriptum Sommige programmeertalen bieden ook pizzasnijders die dat kunnen deel plakjes in exacte tienden. Hoewel dergelijke pizzasnijders zeldzaam zijn, moet je deze gebruiken als het wel mogelijk is dat je precies een tiende of een vijfde van een segment kunt krijgen.

(Oorspronkelijk gepost op Quora.)


225
2018-02-25 21:41



Duidelijke afrondingsfouten. 0.1 kan niet zo nauwkeurig worden gerepresenteerd in base-2 als in base-10 vanwege de ontbrekende priemfactor van 5. Net zoals 1/3 een oneindig aantal cijfers in decimaal vertegenwoordigt, maar "0.1" in base-3 is, 0.1 neemt een oneindig aantal cijfers in base-2 waar het niet in base-10 staat. En computers hebben geen oneindige hoeveelheid geheugen.


199
2018-04-09 12:25



Naast de andere juiste antwoorden, kunt u overwegen om uw waarden te schalen om problemen met drijvende-kommaberekeningen te voorkomen.

Bijvoorbeeld:

var result = 1.0 + 2.0;     // result === 3.0 returns true

... in plaats van:

var result = 0.1 + 0.2;     // result === 0.3 returns false

De uitdrukking 0.1 + 0.2 === 0.3 komt terug false in JavaScript, maar gelukkig is de berekening van gehele getallen in drijvende komma exact, dus decimale representatiefouten kunnen worden voorkomen door te schalen.

Als een praktisch voorbeeld, om drijvende-komma-problemen te vermijden waarbij nauwkeurigheid van het grootste belang is, wordt het aanbevolen1 om geld te behandelen als een geheel getal dat het aantal centen vertegenwoordigt: 2550 centen in plaats van 25.50 dollars.


1 Douglas Crockford: JavaScript: de goede delen: Bijlage A - Afschuwde onderdelen (pagina 105).


98
2018-02-23 17:15



Mijn antwoord is vrij lang, dus ik heb het in drie delen verdeeld. Omdat de vraag gaat over drijvende-kommawiskunde, heb ik de nadruk gelegd op wat de machine feitelijk doet. Ik heb het ook specifiek gemaakt voor dubbele (64-bits) precisie, maar het argument is gelijkelijk van toepassing op drijvende komma-aritmetica.

Preambule

Een IEEE 754 binair drijvende-komma-formaat met dubbele precisie (binary64) getal staat voor een nummer van het formulier

waarde = (-1) ^ s * (1.m51m50... m2m1m0)2 * 2e-1023

in 64 bits:

  • Het eerste bit is het tekenbit: 1 als het aantal negatief is, 0 anders-1.
  • De volgende 11 bits zijn de exponent, dat is compenseren door 1023. Met andere woorden, na het lezen van de exponentbits van een dubbel-precisienummer moet 1023 worden afgetrokken om het vermogen van twee te verkrijgen.
  • De overige 52 bits zijn de mantisse (of mantisse). In de mantisse, een 'impliciet' 1. is altijd2 weggelaten omdat het meest significante bit van elke binaire waarde is 1.

1 - IEEE 754 staat het concept van a toe ondertekende nul - +0 en -0 worden anders behandeld: 1 / (+0) is positief oneindig; 1 / (-0) is negatieve oneindigheid. Voor nulwaarden zijn de mantisse- en exponentbits allemaal nul. Opmerking: nulwaarden (+0 en -0) worden expliciet niet geclassificeerd als denormaal2.

2 - Dit is niet het geval voor denormale nummers, die een offset exponent van nul hebben (en een impliciete 0.). Het bereik van dubbele denormale precisienummers is dmin ≤ | x | ≤ dmax, waar dmin (het kleinste representeerbare niet-nulgetal) is 2-1023 - 51 (≈ 4,94 * 10-324) en dmax (het grootste denormaantal, waarvoor de mantisse volledig bestaat 1s) is 2-1023 + 1 - 2-1023 - 51 (≈ 2.225 * 10-308).


Een dubbel precisienummer naar binair wijzigen

Veel online converters bestaan ​​om een ​​drijvende-kommagetal met dubbele precisie in binair getal om te zetten (bijvoorbeeld bij binaryconvert.com), maar hier is een voorbeeld van een C # -code om de IEEE 754-representatie te verkrijgen voor een dubbel precisienummer (ik scheid de drie delen met dubbele punten (:):

public static string BinaryRepresentation(double value)
{
    long valueInLongType = BitConverter.DoubleToInt64Bits(value);
    string bits = Convert.ToString(valueInLongType, 2);
    string leadingZeros = new string('0', 64 - bits.Length);
    string binaryRepresentation = leadingZeros + bits;

    string sign = binaryRepresentation[0].ToString();
    string exponent = binaryRepresentation.Substring(1, 11);
    string mantissa = binaryRepresentation.Substring(12);

    return string.Format("{0}:{1}:{2}", sign, exponent, mantissa);
}

Ter zake komen: de oorspronkelijke vraag

(Ga naar de onderkant voor de TL; DR-versie)

Cato Johnston (de vraagsteller) vroeg waarom 0.1 + 0.2! = 0.3.

Geschreven in binair (met dubbele punten die de drie delen scheiden), zijn de IEEE 754-representaties van de waarden:

0.1 => 0:01111111011:1001100110011001100110011001100110011001100110011010
0.2 => 0:01111111100:1001100110011001100110011001100110011001100110011010

Merk op dat de mantisse bestaat uit terugkerende cijfers van 0011. Dit is sleutel naar waarom er een fout is in de berekeningen - 0.1, 0.2 en 0.3 kunnen niet worden gerepresenteerd in binair precies in een eindige aantal binaire bits dat meer dan 1/9, 1/3 of 1/7 bedraagt, kan exact worden weergegeven in decimale cijfers.

Het converteren van de exponenten naar decimalen, het verwijderen van de offset en het opnieuw toevoegen van de impliciete 1 (tussen rechte haken), zijn 0.1 en 0.2:

0.1 = 2^-4 * [1].1001100110011001100110011001100110011001100110011010
0.2 = 2^-3 * [1].1001100110011001100110011001100110011001100110011010

Om twee getallen toe te voegen, moet de exponent hetzelfde zijn, dat wil zeggen:

0.1 = 2^-3 *  0.1100110011001100110011001100110011001100110011001101(0)
0.2 = 2^-3 *  1.1001100110011001100110011001100110011001100110011010
sum = 2^-3 * 10.0110011001100110011001100110011001100110011001100111

Omdat de som niet van de vorm 2 isn * 1. {bbb} we vergroten de exponent met één en verplaatsen het decimaalteken (binair) punt om te krijgen:

sum = 2^-2 * 1.0011001100110011001100110011001100110011001100110011(1)

Er zijn nu 53 bits in de mantisse (de 53e staat tussen vierkante haken in de regel hierboven). De standaard afrondingsmodus voor IEEE 754 is 'Ronde naar dichtstbijzijnde'- d.w.z. als een getal X valt tussen twee waarden een en b, de waarde waarbij het minst significante bit nul is, wordt gekozen.

a = 2^-2 * 1.0011001100110011001100110011001100110011001100110011
x = 2^-2 * 1.0011001100110011001100110011001100110011001100110011(1)
b = 2^-2 * 1.0011001100110011001100110011001100110011001100110100

Let daar op een en b verschillen alleen in het laatste beetje; ...0011 + 1 = ...0100. In dit geval is de waarde met het minst significante bit van nul b, dus de som is:

sum = 2^-2 * 1.0011001100110011001100110011001100110011001100110100

TL; DR

schrift 0.1 + 0.2 in een IEEE 754 binaire weergave (met dubbele punten die de drie delen scheiden) en deze vergelijken met 0.3, dit is (ik heb de verschillende stukjes tussen vierkante haken gezet):

0.1 + 0.2 => 0:01111111101:0011001100110011001100110011001100110011001100110[100]
0.3       => 0:01111111101:0011001100110011001100110011001100110011001100110[011]

Terug geconverteerd naar decimaal, deze waarden zijn:

0.1 + 0.2 => 0.300000000000000044408920985006...
0.3       => 0.299999999999999988897769753748...

Het verschil is precies 2-54, wat ~ 5.5511151231258 × 10 is-17 - niet significant (voor veel toepassingen) in vergelijking met de oorspronkelijke waarden.

Het vergelijken van de laatste paar bits van een drijvend kommagetal is inherent gevaarlijk, net als iedereen die de beroemde "Wat elke computerwetenschap moet weten over drijvende-komma aritmetica"(die alle belangrijke delen van dit antwoord omvat) zal het weten.

De meeste rekenmachines gebruiken extra bewaker cijfers om dit probleem te omzeilen, dat is hoe 0.1 + 0.2 zou geven 0.3: de laatste paar stukjes zijn afgerond.


80
2018-03-16 05:27