Rekenen met computers

Een binaire opteller voert op elke bitpositie dezelfde kleine taak uit. De opteller combineert de twee operandbits met een overdracht van de positie rechts ervan. De betekenis van het voltooide bitpatroon volgt daarna.

Volg de overdracht

Een halve opteller heeft twee ingangen: de som is de XOR ervan en de overdracht is de AND ervan. Een volledige opteller accepteert ook een inkomende overdracht:

Hier betekent vermenigvuldiging AND en optelling OR. De som is 1 bij een oneven aantal ingangen met waarde 1; de overdracht is 1 bij minstens twee. Door volledige optellers achter elkaar te schakelen, maak je een ripple-carryopteller. Alleen bit 0 ontvangt de initiële overdracht; elke volgende bit ontvangt de overdracht van de aangrenzende bit.

Voor 23 + 45 schrijf je 0001 0111 + 0010 1101. Bij bit 0 geeft 1 + 1 som 0 en overdracht 1. Bij bit 1 geeft 1 + 0 + 1 opnieuw 0 en overdracht 1. Bij bit 2 geven drie ingangen met waarde 1 som 1 en overdracht 1. Als je naar links doorgaat, krijg je 0100 0100, oftewel 68, zonder uitgaande overdracht aan het eind.

Een resultaat van n bits bewaart alleen de lage n bits, dus de schakeling berekent de som modulo $2^n$. In 8 bits geeft 1111 1100 + 0000 0101 de uitkomst 0000 0001 en uitgaande overdracht 1. Met teken gelezen is dit −4 + 5 = 1. Zonder teken gelezen is het 252 + 5 = 257, waarvan de lage acht bits 1 voorstellen. De schakeling is niet veranderd; het toegestane bereik wel.

Maak van aftrekken optellen

Tweecomplement geeft de identiteit

Een besturingslijn voor aftrekken past XOR toe op elke bit van de tweede operand en 1, waardoor de bit wordt geïnverteerd, en stelt de initiële inkomende overdracht in op 1. Voor optellen is die lijn 0, zodat de tweede operand ongewijzigd doorgaat en de initiële overdracht 0 is.

Om 23 − 45 te berekenen, inverteer je 0010 1101 tot 1101 0010. Tel 0001 0111 + 1101 0010 + 1 op om 1110 1010 te krijgen, met uitgaande overdracht 0. De waarde met teken is −22. Als je de initiële overdracht op 0 laat staan, krijg je −23: alleen inverteren levert één minder dan de vereiste negatieve waarde.

Bij aftrekken zonder teken betekent uitgaande overdracht 1 geen leenbit; uitgaande overdracht 0 betekent dat een leenbit nodig was. De uitgaande overdracht 0 in 23 − 45 geeft dus aan dat het resultaat zonder teken onder nul ligt. Arm legt deze overdracht die geen leenbit aangeeft vast; x86 legt de inverse ervan vast als de leenvlag.

Maak breedtes gelijk vóór de bewerking

RISC-V lb past tekenuitbreiding toe op een byte, lbu past nuluitbreiding toe en addi past tekenuitbreiding toe op de onmiddellijke operand van 12 bits. Kies de uitbreiding op basis van de betekenis van de operand voordat je de bits naar de opteller stuurt.

De meest negatieve waarde met teken heeft geen positieve tegenhanger met dezelfde breedte. Als je 1000 0000 van 8 bits negatief maakt, wordt die geïnverteerd tot 0111 1111 en wordt 1 opgeteld, wat 1000 0000 oplevert. De gewenste +128 vereist een breder formaat met teken.

Overloop betekent dat het exacte resultaat buiten het bereik van het doelformaat valt. Waarden zonder teken van n bits lopen van 0 tot en met $2^n-1$; tweecomplementwaarden met teken lopen van $-2^{n-1}$ tot en met $2^{n-1}-1$. Acht bits bevatten 0 tot en met 255 zonder teken, of −128 tot en met 127 met teken. Hetzelfde opgeslagen resultaat kan bij de ene interpretatie geldig zijn en bij de andere overloop geven.

Test het juiste signaal

Voor optellen of aftrekken met teken kan hardware dit gebruiken:

waarbij de twee overdrachten de tekenpositie binnenkomen en verlaten. De uitgaande overdracht alleen geeft antwoord op de vraag voor getallen zonder teken.

Tel 107 en 54 op in 8 bits: 0110 1011 + 0011 0110 geeft 1010 0001. Er komt een overdracht bit 7 binnen, maar er gaat er geen uit, dus de overloop is 1. De waarde 161 zonder teken past; de interpretatie met teken, −95, is niet gelijk aan de werkelijke som 161. Omgekeerd geeft −4 + 5 overdracht 1 maar overloop met teken 0. Als je 1000 0000 bij zichzelf optelt, krijg je overdracht 1 en overloop 1, zodat beide interpretaties onjuist zijn.

Optellen met tegengestelde tekens kan geen overloop veroorzaken: de exacte som ligt tussen de operanden. Aftrekken heeft een eigen tekenregel nodig, omdat het aftrekken van een negatief getal de eerste operand vergroot. Zo is 100 − (−40) te groot voor 8 bits met teken, ook al passen beide invoerwaarden.

Weet wat de instructie doet

x86 add stelt overdrachts- en overloopvlaggen in. Arm-instructies die vlaggen instellen, zoals ADDS, doen dat ook; een gewone ADD behoudt de bestaande vlaggen. MIPS add en addi veroorzaken een synchrone uitzondering bij overloop met teken, terwijl addu en addiu dat niet doen. Het optellen van gehele getallen in RISC-V schrijft de lage bits en heeft geen overloopvlaggen of synchrone uitzondering bij rekenkundige overloop.

Na add t0, t1, t2 is een RISC-V-controle zonder teken:

bltu t0, t1, overflow

Een omgeslagen som zonder teken is kleiner dan een oorspronkelijke operand. Waarden met teken hebben een andere controle nodig:

slti t3, t2, 0
slt  t4, t0, t1
bne  t3, t4, overflow

De eerste instructie legt vast of de tweede operand negatief is. De tweede legt vast of het resultaat kleiner is dan de eerste operand. Zonder overloop komen deze tests overeen: een negatief getal optellen verlaagt de waarde, terwijl een niet-negatief getal optellen die niet kan verlagen. Een verschil detecteert overloop. Voor een bekende positieve onmiddellijke operand volstaat een voorwaardelijke sprong met teken die test of de som is afgenomen.

Onderscheid hardware van taalregels

Rekenkundige bewerkingen zonder teken in C en C++ slaan om modulo $2^n$; overloop met teken is ongedefinieerd gedrag. De typen int en long van Java slaan om, terwijl Math.addExact overloop met een uitzondering meldt. Gehele getallen in Python groeien waar nodig. Een omslag in hardware bepaalt dus niet wat een C-programma mag doen.

Omslaande optellingen en aftrekkingen behouden een eindresultaat dat past: in modulaire rekenkunde met 8 bits slaat (100 + 50) − 60 eerst om naar −106 en daarna naar 90. Deze redenering geldt voor omslaande rekenkunde, niet voor expressies met teken in C die overlopen.

Verzadiging is een andere aanpak. Zonder teken in 8 bits verzadigt 200 + 100 tot 255 in plaats van om te slaan naar 44. Dit is nuttig voor pixelintensiteiten en andere begrensde signalen, waarbij omslag van een groot positief resultaat naar een kleine waarde misleidend zou zijn.

Een rekenkundig-logische eenheid, of ALU, ontvangt operanden en besturingsingangen en levert een resultaat en statusuitgangen. De ALU is combinatorisch: de uitgangen hangen af van de huidige ingangen. Registers bewaren operanden en nemen resultaten op; de ALU zelf slaat niets op.

Bouw één bit en herhaal die

Een 1-bits-slice berekent AND, OR en een som met een volledige opteller parallel. Een multiplexer kiest welk mogelijk resultaat de resultaatbit bereikt. In een n-bits-ALU delen alle slices de besturingssignalen voor de bewerking, terwijl de uitgaande overdracht van elke opteller naar de inkomende overdracht van de volgende slice gaat. Logische bewerkingen werken op elke positie onafhankelijk; optellen hangt af van de overdrachtsketen.

Een Bnegate-besturingssignaal inverteert de tweede operand en stelt ook de inkomende overdracht van bit 0 in. Als je vervolgens de opteller selecteert, wordt een aftrekking berekend. Hogere slices ontvangen hun overdracht van de voorgaande slice, niet rechtstreeks van Bnegate. Als je elke overdrachtsingang hoog maakt, voeg je extra enen toe aan de berekening.

Een Ainvert-besturingssignaal kan ook de eerste operand inverteren. Als je AND selecteert met beide operanden geïnverteerd, krijg je volgens de wet van De Morgan NOR:

Als je OR selecteert met beide geïnverteerd, krijg je NAND. In deze logische vergelijkingen staat het plusteken voor OR.

Lees een besturingswoord

Een klassieke ALU uit een leerboek gebruikt de velden Ainvert, Bnegate en een Operation-keuzeveld van twee bits:

Dit zijn de coderingen van dit specifieke ontwerp. Het zijn interne besturingscodes, geen coderingen van RISC-V-instructies.

Voor ingangen 0101 en 0011 inverteert besturingscode 0110 de tweede ingang tot 1100 en levert die initiële overdracht 1. De opteller geeft 0010, met uitgaande overdracht 1: 5 − 3 = 2, zonder leenbit bij getallen zonder teken. Als je voor de oorspronkelijke ingangen AND selecteert, krijg je daarentegen 0001. De ingangswaarden kunnen gelijk blijven terwijl een wijziging van de besturing een ander resultaatpad selecteert.

De meest significante slice levert ook informatie over overloop en vergelijking. Een reductie van alle resultaatbits levert Zero. Met die statusuitgangen kan de omringende processorbesturing het rekenkundige resultaat testen zonder een tweede resultaat over de volledige breedte op te slaan.

Voeg verschuiven naast de opteller toe

Een volledige ALU voor de RISC-V-basisinstructies voor gehele getallen heeft ook XOR, vergelijking zonder teken en verschuivingen nodig. Een barrelshifter gebruikt een reeks multiplexerniveaus. Elk niveau geeft de ingang ongewijzigd door of verschuift die met een macht van twee. Een schuifschakeling van 32 bits heeft niveaus voor 1, 2, 4, 8 en 16 posities en verwerkt zo elke verschuiving van 0 tot en met 31 in vijf niveaus.

Om 13 posities te verschuiven selecteer je de niveaus voor 8, 4 en 1. De geselecteerde verschuivingen vormen samen één resultaat. Een logische verschuiving naar rechts voegt nullen in. Een rekenkundige verschuiving naar rechts kopieert de tekenbit en behoudt zo het teken van een negatieve waarde. Als je 1111 0000 twee posities naar rechts verschuift, krijg je dus 0011 1100 bij logisch verschuiven en 1111 1100 bij rekenkundig verschuiven.

Vergelijkingen gebruiken vaak een aftrekking. Bij gelijkheid is de vraag of het verschil nul is. Bij ordening is de vraag of het wiskundige verschil negatief is. Dat vraagt extra aandacht wanneer een aftrekking met vaste breedte overloopt.

Detecteer gelijkheid over alle bits

De nuluitgang Zero is de NOR van alle resultaatbits:

Eén resultaatbit ongelijk aan nul maakt Zero onwaar. Twee gelijke bitpatronen van elkaar aftrekken geeft nul; twee verschillende patronen van n bits kunnen geen veelvoud ongelijk aan nul van $2^n$ verschillen, dus een omslaande aftrekking creëert geen valse gelijkheid. Een alternatieve gelijkheidsschakeling past XOR toe op overeenkomstige operandbits en test of elk XOR-resultaat nul is.

Corrigeer het teken voor kleiner dan met teken

RISC-V slt schrijft het gehele getal 1 over de volledige breedte als de eerste operand met teken kleiner is, en anders 0. In een ALU met slices berekent de meest significante slice een Set-signaal en stuurt dat terug naar de Less-ingang van bit 0. Alle hogere resultaatbits worden op nul gedwongen.

Het juiste Set-signaal is

Zonder overloop werkt het teken van het verschil direct. Bij overloop is dat teken omgekeerd ten opzichte van het werkelijke verschil, zodat XOR met 1 het corrigeert.

Vergelijk 7 met −8 in vier bits. De aftrekking 0111 + 0111 + 1 geeft 1111. Het teken suggereert een negatief verschil, maar het exacte verschil is 15, buiten het bereik van −8 tot en met 7. De overloop is 1, dus het gecorrigeerde Less-signaal is 1 XOR 1 = 0. Het resultaat van slt is 0000 en geeft terecht aan dat 7 niet kleiner is dan −8.

Gebruik de leenbit voor kleiner dan zonder teken

Vergelijking zonder teken gebruikt een ander signaal:

voor een aftrekking met geïnverteerde tweede ingang en initiële overdracht 1. Uitgaande overdracht 0 betekent dat een leenbit nodig was, dus is de eerste operand zonder teken kleiner.

Dit onderscheid zie je in slt tegenover sltu, en in de voorwaardelijke sprongen blt tegenover bltu en bge tegenover bgeu. Noch alleen het teken van het resultaat, noch een algemene “negatiefvlag” beantwoordt beide vragen.

Pas de vergelijking toe in software

Een bereikcontrole zonder teken kan zowel negatieve indices als indices vanaf de arraylengte afwijzen:

bgeu x10, x11, IndexOutOfBounds

Hier bevat x10 de index met teken en x11 een niet-negatieve lengte die binnen het bereik met teken past. Een negatieve index, opnieuw geïnterpreteerd zonder teken, is minstens $2^{n-1}$ en is daarom groter dan elke dergelijke lengte. De voorwaarde voor de lengte is van belang: die maakt één vergelijking zonder teken voldoende.

Conversies in programmeertalen kunnen ook de betekenis van een vergelijking veranderen. Bij een C-type unsigned int van 32 bits is -1 < 0u onwaar, omdat −1 vóór de vergelijking wordt omgezet naar 4.294.967.295. Volg de conversie voordat je redeneert op basis van het geschreven minteken.

De overdracht van een ripple-carryopteller moet elke bit achtereenvolgens doorlopen. Vooruitberekening van de overdracht vervangt dat achtereenvolgende wachten door logica die overdrachten voorspelt op basis van operandbits en de initiële overdracht.

Beschrijf het overdrachtsgedrag van elke bit

Definieer generatie en doorgifte als

Dit zijn Booleaanse expressies: vermenigvuldiging is AND en optelling is OR. Generatie is 1 als de bit een overdracht maakt, ongeacht de inkomende overdracht. Doorgifte is 1 als een inkomende overdracht kan worden doorgegeven. De recursieve betrekking is

Een bit met beide ingangen op 1 genereert een overdracht; een bit met één ingang op 1 geeft een overdracht door; een bit met beide ingangen op 0 stopt die. Bij deze OR-definitie heeft een genererende bit ook doorgifte 1, wat de overdrachtsformule niet verandert.

Werk de afhankelijkheid uit

Vervang elke voorgaande overdracht door de expressie ervoor:

Elke expressie hangt nu af van signalen die uit de operanden zijn afgeleid en van de initiële overdracht, niet van een opeenvolgende keten van tussenliggende overdrachtsuitgangen. Zodra de overdrachten beschikbaar zijn, is elke sombit nog steeds de XOR van de twee ingangen en de inkomende overdracht.

Voor 1011 + 0110 met initiële overdracht 0 is de generatie vanaf bit 0 naar boven 0, 1, 0, 0 en de doorgifte 1, 1, 1, 1. De inkomende overdrachten van bits 1 tot en met 4 zijn dus 0, 1, 1, 1. De vier resultaatbits zijn 0001 met uitgaande overdracht 1, samen 11 + 6 = 17.

Bouw groepen in plaats van reusachtige poorten

Een blok van vier bits heeft groepssignalen

De uitgaande overdracht is $G+P{c}_0$. Een tweede niveau voor vooruitberekening combineert deze bloksignalen volgens dezelfde regel. Vier blokken van vier bits en een eenheid voor vooruitberekening per groep vormen een opteller van 16 bits. Verdere groepering ondersteunt bredere ontwerpen; parallelle prefixoptellers zoals Kogge–Stone ordenen deze verbanden in een snel netwerk.

In een eenvoudig model voor poortvertraging kost het doorschakelen van een overdracht ongeveer twee poortvertragingen per bit, of 32 voor 16 bits. Een ontwerp met vooruitberekening op twee niveaus kan de laatste overdracht in ongeveer vijf poortvertragingen leveren: één voor bitsignalen, twee voor groepssignalen en twee voor de groepsoverdracht. Deze schatting telt logische niveaus en veronderstelt de vereiste poorten; de werkelijke vertraging hangt ook af van de poortgrootte en bedrading. Groepering ruilt meer hardware in voor een overdrachtspad dat ongeveer logaritmisch groeit met de breedte.

Een opteller met overdrachtsselectie gebruikt oppervlak anders: de opteller berekent een bovenste blok tweemaal, eenmaal voor inkomende overdracht 0 en eenmaal voor inkomende overdracht 1. Een multiplexer selecteert het juiste resultaat wanneer de overdracht van het onderste blok aankomt.

Sommige optellers definiëren doorgifte met XOR in plaats van OR. Ook dat geeft correcte overdrachten en maakt de som $s_i=p_i\oplus c_i$. Gebruik de gekozen definitie consequent bij het afleiden van de groepslogica.

Elke binaire vermenigvuldigerbit kiest een verschoven kopie van het vermenigvuldigtal of nul. Het optellen van die deelproducten geeft het resultaat. Voor een operand van n bits maal een operand van m bits kunnen n + m bits nodig zijn, dus twee operanden van 32 bits hebben een volledig product van 64 bits nodig.

Volg schuiven en optellen

Begin voor operanden zonder teken van n bits met een product van 2n bits dat nul is. Herhaal n keer: test de lage bit van de vermenigvuldiger, tel het huidige vermenigvuldigtal op als die bit 1 is, verschuif het vermenigvuldigtal naar links en verschuif de vermenigvuldiger naar rechts. Het vermenigvuldigtalregister moet breed genoeg zijn om de verschoven kopieën te bewaren.

Voor 6 × 5 met vier bits is de vermenigvuldiger 0101:

Het eindproduct is 30. De geteste bit en de verschuivingsrichting werken samen: als je de hoge bit test terwijl je de vermenigvuldiger naar rechts verschuift, koppel je bits aan de verkeerde gewichten. Dit sequentiële ontwerp neemt n stappen, inclusief stappen waarbij de vermenigvuldigerbit nul is.

Deel registerruimte

Het eerste ontwerp gebruikt een vermenigvuldigtalregister en een opteller van 2n bits. Een verbeterd ontwerp houdt het vermenigvuldigtal vast in n bits, plaatst de vermenigvuldiger in de lage helft van een productregister van 2n bits en begint met nul in de hoge helft.

Als de lage bit 1 is, tel je het vermenigvuldigtal op bij de hoge helft. Bewaar de uitgaande overdracht van de opteller in één extra bit en verschuif daarna die overdracht en beide producthelften samen naar rechts. De vermenigvuldigerbits verlaten het register aan de rechterkant terwijl productbits de vrijgekomen ruimte innemen. Als je de overdracht weglaat, worden grote producten onjuist: met operanden van vier bits zou 15 × 15 ten onrechte 1 worden in plaats van 225. Bij één stap per klokcyclus duurt de eenvoudige implementatie van 32 bits ongeveer 32 cycli.

Houd de productbreedte in het oog

Een product zonder teken past precies dan in n bits als de bovenste n bits van het volledige product nul zijn. Voor 6 × 5 is het volledige resultaat 0001 1110; als je alleen 1110 opslaat, krijg je 14. De vermenigvuldiging zelf was correct, maar de smalle bestemming heeft een deel weggegooid.

Een verschuiving van k posities naar links vermenigvuldigt met $2^k$ als het resultaat past. Vermenigvuldigen met 8 wordt een verschuiving van drie posities; vermenigvuldigen met 10 kan met twee verschoven kopieën:

(x << 3) + (x << 1)

De berekening is $8x+2x=10x$. Breedte en regels van de programmeertaal blijven gelden voor de verschuivingen en optelling; deze herschrijving maakt geen extra resultaatbits.

Lees de RISC-V-resultaathelften

mul geeft de lage XLEN bits terug, waarbij XLEN de breedte van het integerregister is. mulhu geeft de hoge helft voor operanden zonder teken. De instructies voor de hoge helft met teken zijn mulh voor twee operanden met teken en mulhsu voor een eerste operand met teken en een tweede zonder teken.

Software die het volledige product nodig heeft, kan de passende instructie voor de hoge helft uitvoeren, gevolgd door mul met dezelfde operanden. Een implementatie kan het paar samenvoegen. Het lage resultaat alleen kan niet aantonen dat een product zonder teken past; de bovenste helft levert dat bewijs.

Vermenigvuldiging met teken moet de tekens van de operanden verwerken zonder de meest negatieve waarde te verliezen. Snellere hardware heeft ook een manier nodig om veel deelproducten terug te brengen zonder telkens op een volledige optelling met overdrachtsdoorgifte te wachten.

Vermenigvuldig absolute waarden veilig

Eén aanpak legt de tekens vast, vormt absolute waarden zonder teken van n bits, vermenigvuldigt die tot 2n bits en maakt het volledige product negatief als precies één operand negatief was. Voor −8 in vier bits stellen de bits 1000 de waarde 8 zonder teken voor. Je kunt ze niet lezen als een positieve waarde met teken van vier bits.

De lage n productbits zijn identiek bij interpretaties met en zonder teken. 1111 × 0010 geeft 30 zonder teken (0001 1110) of −2 met teken (1111 1110). Beide lage helften zijn 1110; alleen de bovenste helften verschillen. Daarom is één mul-instructie geschikt voor beide interpretaties.

Volg de beslissingen van Booth

Het algoritme van Booth werkt rechtstreeks met tweecomplement. Geef de accumulator n + 1 bits en breid het vermenigvuldigtal met tekenuitbreiding uit tot die breedte, zodat zowel het vermenigvuldigtal als de negatieve waarde ervan past. Begin met de accumulator op nul, plaats de vermenigvuldiger in zijn register van n bits en voeg één extra bit toe die op nul begint.

Bekijk de lage bit van de vermenigvuldiger en de toegevoegde bit als een paar:

Verschuif na elke beslissing het volledige register met accumulator, vermenigvuldiger en extra bit rekenkundig naar rechts. Herhaal dit n keer; verwijder de toegevoegde bit en de overtollige bovenste tekenbit van de accumulator om het product van 2n bits te krijgen.

Gebruik voor 2 × (−3) vermenigvuldigtal 00010, vermenigvuldiger 1101 en accumulator 00000. De paren zijn 10, 01, 10, 11. Na de respectieve bewerkingen en verschuivingen zijn accumulator en vermenigvuldiger 11111 0110, 00000 1011, 11111 0101 en 11111 1010. De lage acht productbits 1111 1010 stellen −6 voor.

Een logische verschuiving zou bovenaan nul invoegen en negatieve tussenresultaten onjuist maken. De extra accumulatorbit is ook van belang: het aftrekken van een meest negatief vermenigvuldigtal van n bits vereist een positieve waarde die niet beschikbaar is in n bits met teken.

Verminder het werk en verkort de overdrachtspaden

Booth-hercodering vervangt een reeks bits met waarde 1 door een aftrekking aan de lage kant en een optelling boven de hoge kant. Zo is 126 gelijk aan 128 − 2. Afwisselende bits leveren mogelijk geen besparing op. Booth met grondtal 4 bekijkt twee vermenigvuldigerbits per stap en gebruikt cijfers van −2 tot en met +2, waardoor het aantal deelproducten afneemt.

Een snelle vermenigvuldiger vormt deelproducten parallel. Een opteller met opgeslagen overdracht brengt drie woorden terug tot twee zonder overdrachten door het woord door te geven. Wallace- of Dadda-bomen herhalen die reductie en gebruiken daarna één laatste opteller met overdrachtsdoorgifte. Het terugbrengen van 32 rijen tot twee kost acht niveaus met opgeslagen overdracht. Pipelining maakt het mogelijk dat meerdere producten tegelijk worden verwerkt; elke cyclus een nieuw product accepteren betekent niet dat elk product in één cyclus klaar is.

Voor een resultaat met teken dat tot n bits wordt versmald, moet elke bit van de bovenste helft gelijk zijn aan de tekenbit van de lage helft. De berekening −8 × −1 met vier bits geeft het volledige product 0000 1000. De bovenste helft is nul maar de behouden tekenbit is 1, dus +8 past niet in het doelformaat met teken.

Een deling levert een quotiënt en een rest op die samen voldoen aan

Voor een deler zonder teken die niet nul is, is de rest niet-negatief en kleiner dan de deler. Een deeltal en deler van n bits hebben een quotiënt en rest van n bits nodig.

Maak het quotiënt bit voor bit

Lees deeltalbits vanaf de meest significante kant. Verdubbel de gedeeltelijke rest, haal de volgende bit erbij en test of de deler past. Zo ja, trek die af en schrijf quotiëntbit 1; behoud anders de gedeeltelijke rest en schrijf 0.

Voor 0111 gedeeld door 0010 zijn de gedeeltelijke resten na het naar beneden halen 0, 1, 3 en 3. De eerste twee zijn kleiner dan 2, dus hun quotiëntbits zijn 0. Bij elke 3 is een aftrekking mogelijk, met rest 1 en quotiëntbit 1. Het quotiënt is 0011 en de rest 0001: 3 × 2 + 1 = 7.

Deling met herstel van de rest probeert eerst een aftrekking. Als het proefresultaat negatief is, tel je de deler terug en schrijf je 0; anders behoud je het resultaat en schrijf je 1. Detecteer het mislukken met een leenbit of een verschil met teken van n + 1 bits. Een tekentest van n bits is onveilig: 0 − 9 in vier bits slaat om naar 0111, waarvan de bovenste bit 0 is ondanks de leenbit.

Compacte hardware plaatst het deeltal in de lage helft van een register van 2n bits en de gedeeltelijke rest in de hoge helft. Het register verschuift elke stap naar links en voegt rechts quotiëntbits in. Aan het eind bevat de hoge helft de rest en de lage helft het quotiënt.

Deling zonder herstel van de rest neemt een negatief proefresultaat mee en telt de deler in de volgende stap op in plaats van direct te herstellen. Een negatieve gedeeltelijke rest aan het eind vereist nog één optelling. SRT-deling selecteert meerdere quotiëntbits per stap met behulp van de voorste bits van deler en rest; ontbrekende waarden in zo'n selectietabel veroorzaakten de Pentium FDIV-fout van 1994. Deling blijft afhankelijk van elke voorgaande gedeeltelijke rest.

Pas deling met teken en afkappen toe

Deel de absolute waarden, maak het quotiënt negatief als de tekens verschillen en geef een rest ongelijk aan nul het teken van het deeltal.

Deze resultaten kappen het quotiënt af naar nul en behouden de delingsidentiteit. RISC-V, Java en C sinds C99 gebruiken deze regel. Python // rondt daarentegen naar beneden af: -7 // 2 is −4 en -7 % 2 is 1.

Handel bijzondere invoer af

Deling door nul in RISC-V geeft een quotiënt dat geheel uit enen bestaat en het oorspronkelijke deeltal als rest. Het geval van overloop met teken, de meest negatieve waarde gedeeld door −1, geeft het meest negatieve quotiënt en rest nul. Geen van beide gevallen veroorzaakt een synchrone uitzondering. x86 veroorzaakt in beide gevallen een uitzondering wegens een delingsfout. Software die fouten moet melden, controleert eerst op nul en controleert ook het paar dat overloop met teken veroorzaakt.

Een logische verschuiving naar rechts deelt waarden zonder teken door machten van twee en rondt naar beneden af. Een rekenkundige verschuiving rondt negatieve waarden ook naar beneden af: −5 één positie naar rechts verschoven wordt −3, terwijl deling door 2 met afkappen −2 geeft. Om afkappen met een verschuiving te implementeren, tel je $2^k-1$ op bij een negatieve invoer voordat je k posities naar rechts verschuift. Voor −5 en k = 1 verschuif je −4 om −2 te krijgen.

Een normale binaire drijvendekommawaarde heeft de vorm

De significand is de volledige waarde 1,f; de opgeslagen fractie bevat alleen f. Normalisatie garandeert de voorste 1, dus het weglaten van deze verborgen bit levert één bit precisie op.

Lees de drie velden

IEEE 754-2019 definieert deze formaten. Enkele en dubbele precisie betekenen meestal binary32 en binary64. De opslagvolgorde is teken, exponent, fractie. Voor een normale waarde trek je de bias af van het exponentveld zonder teken:

Fractie betekent de binaire breuk na de komma, niet de bits gelezen als geheel getal. In binary32 coderen exponentvelden 1 tot en met 254 de exponenten −126 tot en met 127. Velden 0 en 255 hebben bijzondere betekenissen.

Een bias zorgt ervoor dat grotere exponenten grotere velden zonder teken hebben. Voor positieve eindige getallen volgt de volgorde van de volledige patronen zonder teken de numerieke volgorde. Negatieve waarden en NaN-waarden vereisen extra afhandeling.

Codeer en decodeer

Om −0,75 te coderen, schrijf je de absolute waarde als ${\mathrm{0,11}}_2={\mathrm{1,1}}_2\times 2^{-1}$. Het teken is 1 en het exponentveld is −1 + 127 = 126, oftewel 01111110. Laat de verborgen voorste 1 weg en vul de fractie aan met nullen. De velden zijn 1 01111110 10000000000000000000000, wat 0xBF400000 geeft. In binary64 is dezelfde waarde 0xBFE8000000000000.

Om 0x41460000 te decoderen, splits je het op in 0 10000010 10001100000000000000000. Het exponentveld is 130, dus de werkelijke exponent is 3. De significand is

Vermenigvuldigen met 8 geeft 12,375. Als je de verborgen 1 in de opgeslagen fractie zou schrijven, zou de waarde veranderen; als je −1 rechtstreeks in het exponentveld zou opslaan, zou de biasregel verloren gaan.

Onderscheid bereik van precisie

binary32 reikt tot ongeveer $\mathrm{3,40}\times {10}^{38}$, met kleinste positieve normale waarde $2^{-126}$ en ongeveer zeven significante decimale cijfers. binary64 reikt tot ongeveer $\mathrm{1,80}\times {10}^{308}$, met kleinste positieve normale waarde $2^{-1022}$ en ongeveer 15–16 significante cijfers. binary16 heeft maximum 65.504, kleinste positieve normale waarde $2^{-14}$, kleinste positieve subnormale waarde $2^{-24}$ en ongeveer 3,3 significante decimale cijfers.

Precisie telt significante cijfers, geen cijfers na de komma. Zo slaat binary32 1.234.567,89 op als 1.234.567,875.

Binnen het binary32-interval van $2^e$ tot $2^{e+1}$ liggen aangrenzende normale waarden $2^{e-23}$ uit elkaar. Deze afstand is een ulp, een eenheid op de laatste positie. Net boven 1 is die $2^{-23}$, vaak machine-epsilon genoemd. Bij $2^{24}$ wordt de afstand 2, zodat 16.777.217 ontbreekt, ook al passen veel grotere getallen. Meer exponentbits vergroten het schaalbereik; meer fractiebits plaatsen representeerbare waarden bij een bepaalde schaal dichter bij elkaar.

Gereserveerde exponentpatronen laten IEEE 754 waarden voorstellen buiten de gewone genormaliseerde getallen. Classificeer de velden altijd voordat je een formule voor de waarde toepast.

Herken de gereserveerde patronen

binary32 heeft +0 op 0x00000000 en −0 op 0x80000000. Bij vergelijking zijn ze gelijk, maar deling kan het teken zichtbaar maken: 1 gedeeld door +0 geeft +∞, terwijl 1 gedeeld door −0 de uitkomst −∞ geeft. Een heel klein negatief resultaat dat naar nul wordt afgerond, wordt −0.

Positieve oneindigheid is 0x7F800000; de grootste eindige positieve waarde is 0x7F7FFFFF. Bij afronden naar het dichtstbijzijnde getal geeft rekenkundige overloop een oneindigheid met teken. Deling van een eindige waarde ongelijk aan nul door nul geeft ook een oneindigheid met teken, met een andere uitzonderingsvlag. Verdere berekeningen handelen oneindigheid consequent af: 1 optellen bij +∞ laat +∞ onveranderd, vermenigvuldiging met −2 geeft −∞ en de reciproke is +0.

Onderscheid NaN van oneindigheid

Bewerkingen zoals nul gedeeld door nul, oneindigheid min zichzelf, nul maal oneindigheid en de reële wortel van −1 hebben geen betekenisvol numeriek resultaat. Ze leveren NaN, “geen getal”, op en signaleren een ongeldige bewerking.

NaN is ongeordend: gelijkheidstests en geordende tests op kleiner dan of groter dan met NaN zijn onwaar, terwijl ongelijkheid waar is. Met name x == NaN kan NaN niet detecteren. Gebruik isnan(x). Stille NaN-waarden planten zich normaal voort in berekeningen; signalerende NaN-waarden veroorzaken een ongeldige bewerking wanneer ze worden gebruikt. In deze binaire formaten onderscheidt de bovenste fractiebit een stille NaN. De canonieke stille binary32-NaN van RISC-V is 0x7FC00000.

Benader nul geleidelijk

Een subnormaal getal heeft geen verborgen 1. De exponent staat vast op de kleinste normale exponent:

Voor binary32 is 0x00000001 gelijk aan $2^{-149}$ en 0x00400000 aan $2^{-127}$. Voor binary64 is de kleinste positieve waarde $2^{-1074}$. Als je bij een exponentveld van nul de exponent min de bias zou gebruiken, zou je er een factor twee naast zitten, zelfs voordat je ten onrechte een verborgen 1 toevoegt.

Subnormale getallen bieden geleidelijke onderloop: de precisie neemt af naarmate waarden kleiner worden, met een vaste absolute afstand dicht bij nul. Verschillende eindige waarden in één formaat hebben nog steeds een representeerbaar verschil ongelijk aan nul. Modi die naar nul afkappen laten die bescherming vervallen en kunnen de verwerking van subnormale getallen op sommige processors versnellen.

Lees de uitzonderingsvlaggen

IEEE 754 definieert ongeldige bewerking, deling door nul, overloop, onderloop en niet-exact resultaat. De standaardafhandeling geeft een resultaat terug en legt de status vast; de uitvoering hoeft niet te stoppen. Niet-exact betekent dat het afgeronde resultaat verschilt van het exacte resultaat.

Bij de standaardafhandeling vereist onderloop zowel een heel kleine als een niet-exacte waarde. In binary32 is $2^{-126}\mathrm{/}2=2^{-127}$ een exact subnormaal getal en veroorzaakt dit geen onderloop. RISC-V legt NV, DZ, OF, UF en NX vast in fflags binnen fcsr, en uitzonderingen bij drijvendekommagetallen veroorzaken geen rekenkundige synchrone uitzonderingen. Een teruggegeven oneindigheid alleen laat niet zien of er overloop of deling door nul optrad; controleer de vlag.

Rekenen met drijvendekommagetallen werkt afzonderlijk met significands en exponenten. Het eindresultaat moet de exacte bewerking zijn, afgerond naar het doelformaat, dus het tussentijds verschuiven van bits moet voldoende informatie voor die laatste beslissing bewaren.

Tel op met een gemeenschappelijke exponent

Optellen volgt vier stappen: uitlijnen, de bewerking uitvoeren, normaliseren, afronden. Vergelijk de exponenten en verschuif de significand van de kleinere operand naar rechts met het verschil tussen de exponenten. Tel bij gelijke tekens de absolute waarden op; trek bij tegengestelde tekens de absolute waarden van elkaar af. Verschuif het resultaat naar genormaliseerde vorm en pas de exponent aan. Rond daarna af en normaliseer opnieuw als afronden een overdracht veroorzaakt.

Gebruik significands van vier bits om 0,5 + (−0,4375) te bekijken:

1. Schrijf de operanden als ${\mathrm{1,000}}_2\times 2^{-1}$ en $-{\mathrm{1,110}}_2\times 2^{-2}$.
2. Lijn de tweede uit tot $-{\mathrm{0,111}}_2\times 2^{-1}$.
3. Trek de absolute waarden af: ${\mathrm{1,000}}_2-{\mathrm{0,111}}_2={\mathrm{0,001}}_2$.
4. Normaliseer tot ${\mathrm{1,000}}_2\times 2^{-4}$, oftewel 0,0625. Er zijn geen bits ongelijk aan nul verloren gegaan, dus afronden hoeft niets te veranderen.

Cijferverlies door aftrekking kan een grote verschuiving naar links voor normalisatie vereisen. Hardware gebruikt een exponentaftrekker, een schuifschakeling voor uitlijnen, een significandopteller, een teller voor voorloopnullen en logica voor normalisatie en afronding. Optellers voor drijvendekommagetallen gebruiken gewoonlijk pipelining over meerdere cycli.

Een decimaal model laat zien waarom extra cijfers van belang zijn: met vier significante cijfers wordt 99,99 + 0,161 uitgelijnd als $\mathrm{9,999}+\mathrm{0,01610}$ op schaal ${10}^1$. Het exacte tussenresultaat is 10,01510 op die schaal. Normaliseer tot $\mathrm{1,00151}\times {10}^2$ en rond af tot $\mathrm{1,002}\times {10}^2$. Als je de uitgelijnde term te vroeg afkapt, verlies je informatie die nodig is om 100,2 te kiezen.

Vermenigvuldig schalen en significands

Vermenigvuldig de significands, tel de werkelijke exponenten op en pas XOR toe op de tekens. Trek bij velden met bias eenmaal de bias af:

voordat je aanpassingen voor normalisatie doet. Twee normale significands vermenigvuldigd geven een waarde vanaf 1 tot 4, dus hun product vereist hoogstens één verschuiving naar rechts voor normalisatie. Afronding kan nog een aanpassing vereisen; ook de exponentgrenzen moeten worden gecontroleerd.

Voor 0,5 × (−0,4375) geven de binary32-exponentvelden 126 + 125 − 127 = 124, oftewel werkelijke exponent −3. Het significandproduct is ${\mathrm{1,000}}_2\times {\mathrm{1,110}}_2={\mathrm{1,110}}_2$. De XOR van de tekens is 1, wat $-{\mathrm{1,110}}_2\times 2^{-3}=-\mathrm{0,21875}$ geeft.

Rond eenmaal af met gecombineerde vermenigvuldiging en optelling

FMA berekent a × b + c met één afronding na de volledige expressie. Afzonderlijk vermenigvuldigen en optellen rondt tweemaal af. Neem in binary32 $a=1+2^{-23}$, $b=1-2^{-23}$ en c = −1. Hun exacte product is $1-2^{-46}$. Een afzonderlijke vermenigvuldiging rondt dit af tot 1, zodat de optelling nul oplevert. FMA behoudt het kleine productverschil en geeft $-2^{-46}$ terug.

RISC-V F levert 32 drijvendekommagetalregisters, f0 tot en met f31; D verbreedt dezelfde bank voor dubbele precisie. flw/fsw en fld/fsd verplaatsen waarden. Rekenkundige instructies zijn onder meer fadd.s, fmul.s, fdiv.s en fsqrt.s, met .d-vormen voor dubbele precisie. fmadd.s berekent een gecombineerde vermenigvuldiging en optelling. Vergelijkingen zoals flt.s schrijven 0 of 1 naar een integerregister en fcvt zet formaten of integerwaarden om.

Een eindig formaat kan niet elk exact resultaat opslaan. Correcte afronding betekent dat je het representeerbare resultaat kiest dat de afrondingsrichting vereist, alsof de bewerking eerst exact was berekend. Elementaire rekenkundige bewerkingen, worteltrekken en FMA volgen deze regel. Payload- en tekenbits van NaN hoeven niet op alle processors identiek te zijn.

Kies een afrondingsrichting

De eerste vier zijn vereist voor binaire implementaties; bij gelijke afstand naar even afronden is de standaard. Bij gelijke afstand van nul af afronden is vereist voor decimale formaten en RISC-V biedt dit ook voor binaire bewerkingen. De namen zijn RNE, RUP, RDN, RTZ en RMM; een instructie kan een modus direct selecteren of de dynamische modus in fcsr gebruiken.

Bij afronden op gehele getallen met gelijke afstand naar even wordt 2,5 gelijk aan 2 en 3,5 gelijk aan 4. Binair met significands van vier bits rondt ${\mathrm{1,0011}}_2$ af naar ${\mathrm{1,010}}_2$ en rondt ${\mathrm{1,0101}}_2$ ook af naar ${\mathrm{1,010}}_2$. De even bit hoort bij de behouden significand, niet bij de exponent of een weergegeven decimaal cijfer.

Bewaar bewakings-, afrondings- en plakinformatie

Bewaar na normalisatie twee extra bits na de doelsignificand: de bewakingsbit en de afrondingsbit. De plakbit is de OR van elke latere weggegooide bit. Die legt vast of die hele staart nul is.

Bij afronden naar het dichtstbijzijnde getal betekent bewakingsbit 0 dat de waarde onder de helft ligt. Bewakingsbit 1 met afrondingsbit of plakbit 1 betekent boven de helft. Bewakingsbit 1 met beide latere indicatoren 0 betekent precies halverwege. Verhoog bij een waarde precies halverwege de behouden significand alleen als de huidige lage bit 1 is.

Voor de som 8 + 0,5625 met een significand van vier bits geeft uitlijnen

Behoud 1.000; de bewakingsbit is 1, de afrondingsbit is 0 en de plakbit is 1 omdat de resterende staart een 1 bevat. De waarde ligt boven de helft, dus verhoog tot ${\mathrm{1,001}}_2\times 2^3=9$. Als je de plakbit weggooit, lijkt de waarde ten onrechte precies halverwege te liggen en wordt 8 gekozen.

Een plakbit geeft informatie over alle verloren bits, niet alleen over de derde bit na het behouden deel. Als tijdens het verschuiven een verloren bit eenmaal 1 is, blijft de plaktoestand voor die verzamelde staart 1.

Interpreteer fout en overloop

Voor eindige resultaten binnen het bereik heeft afronden naar het dichtstbijzijnde getal een absolute fout van hoogstens een halve ulp; gericht afronden heeft een fout van minder dan één ulp. Voor normale binary32-resultaten is de gebruikelijke relatieve grens bij afronden naar het dichtstbijzijnde getal $2^{-24}$; voor binary64 is die $2^{-53}$. Subnormale resultaten vereisen een redenering met de absolute fout, omdat hun relatieve precisie afneemt.

De afrondingsrichting bepaalt ook de resultaten bij overloop. Positieve overloop geeft +∞ bij afronden naar het dichtstbijzijnde getal of naar positief, maar de grootste eindige positieve waarde bij afronden naar nul of naar negatief. Negatieve overloop geeft het gespiegelde gedrag.

Conversies naar gehele getallen hebben eigen regels. In C kappen representeerbare typeconversies zoals (int)2.7 en (int)-2.7 af tot 2 en −2, onafhankelijk van de huidige afrondingsrichting voor drijvendekommagetallen. Controleer zowel het bereik van het doelformaat als het weggegooide fractionele deel.

Fouten met drijvendekommagetallen volgen vaak direct uit de eindige afstand tussen waarden. Onderscheid de fout die al in opgeslagen operanden zit van de afronding door een bewerking en van informatie die tijdens conversie verloren gaat.

Herken representatiefouten

Een vereenvoudigde breuk heeft precies dan een eindige binaire ontwikkeling als de noemer een macht van twee is. Waarden zoals 0,5, 0,25 en 0,375 zijn exact. De ontwikkeling van 0,1 herhaalt zich, dus binary32 slaat 0x3DCCCCCD op, ongeveer 0,10000000149011612. Ook binary64 slaat een benadering op.

Daardoor levert binary64 0.1 + 0.2 de uitkomst 0,30000000000000004 op, anders dan de opgeslagen waarde die het dichtst bij 0,3 ligt. Een kort weergegeven resultaat zoals 0.1 kan het kortste decimale getal zijn dat bij terugconversie dezelfde opgeslagen bits oplevert; het bewijst niet dat de waarde exact is.

Gebruik voor benaderde eindige resultaten een tolerantie die bij het probleem past, bijvoorbeeld

De absolute tolerantie behandelt waarden dicht bij nul; de relatieve tolerantie schaalt mee met de absolute waarde. De toleranties moeten passen bij de berekening en de aanvaardbare fout, niet alleen bij het aantal weergegeven cijfers.

Let op hoe optellen een kleine invoer verliest

Absorptie treedt bij afronden naar het dichtstbijzijnde getal op wanneer een kleine optelterm een grote operand niet naar het volgende representeerbare buurgetal kan verplaatsen. In binary32 rondt 16.777.216 + 1 terug af naar 16.777.216: de buurwaarden liggen twee uit elkaar en bij gelijke afstand wordt de even significand gekozen. Een teller van het type float die 1 optelt, kan daardoor stoppen met vooruitgaan.

Een andere optelvolgorde kan het antwoord veranderen. Met binary32 x = −1,5 × 10³⁸, y = 1,5 × 10³⁸ en z = 1 geeft (x + y) + z de uitkomst 1. Maar y + z rondt af naar y, dus x + (y + z) geeft nul. Optellen is niet associatief. Parallelle reducties kunnen hun groepering veranderen wanneer het aantal threads verandert, wat de laatste bits beïnvloedt.

Herhaald afronden stapelt zich ook op: als je binary32-waarde 0,1 tien miljoen keer optelt bij een binary32-totaal, krijg je 1.087.937 in plaats van 1.000.000. Een bredere accumulator vermindert het verlies door afronding. Kleinere absolute waarden eerst optellen kan ook bijdragen behouden die een groot lopend totaal zou absorberen.

Onderscheid cijferverlies van niet-exact aftrekken

Cijferverlies door aftrekking verwijdert gemeenschappelijke voorste cijfers van bijna gelijke operanden. De aftrekking zelf kan exact zijn terwijl eerdere operandfouten groot worden ten opzichte van het kleine antwoord. In binary32 wordt 1,0000001 opgeslagen als $1+2^{-23}$. Daar 1 van aftrekken geeft ongeveer $\mathrm{1,1920929}\times {10}^{-7}$ in plaats van $\mathrm{1,0}\times {10}^{-7}$, een relatieve fout van ongeveer 19%.

Controleer conversies en formaatkeuzes

binary64 stelt elk geheel getal van 32 bits exact voor. binary32 doet dat niet: 16.777.217 rondt bij gelijke afstand naar even af naar 16.777.216. Boven $2^{53}$ mist ook binary64 sommige gehele getallen. Het omzetten van een drijvendekommawaarde naar een kleiner type voor gehele getallen kan volledig buiten het bereik vallen.

Tijdens de eerste vlucht van Ariane 5 in 1996 schakelde een conversie buiten het bereik van een drijvendekommagetal van 64 bits naar een geheel getal met teken van 16 bits de traagheidsreferentiesystemen uit en droeg die bij aan het verlies van de raket. Bij het falen van het Patriot-systeem in 1991 in Dhahran zorgde een afgeknotte vastekommabenadering van 0,1 na ongeveer 100 uur voor een opgelopen tijdfout van ongeveer 0,34 s, waardoor het volgvenster ongeveer 687 m verschoof. Dit was een representatiefout met vaste komma, geen IEEE-drijvendekommabewerking.

Kies binary64 voor een grotere precisie bij algemeen gebruik, binary32 wanneer het kleinere geheugengebruik bij de taak past en binary16 of bfloat16 voor geschikte taken met lage precisie. bfloat16 heeft acht exponentbits en zeven fractiebits. Exacte geldbedragen horen in gehele aantallen van de kleinste munteenheid of in een decimaal type.