Kompletteringsmetode - Method of complements

Komplementnumre på en tilføjelsesmaskine c. 1910. De mindre tal, til brug ved subtraktion, er niernes komplement til de større tal, som bruges ved tilføjelse.

I matematik og computing er komplementeringsmetoden en teknik til at kode et symmetrisk område af positive og negative heltal på en måde, så de kan bruge den samme algoritme (hardware) til tilføjelse i hele området. For et givet antal steder koder halvdelen af de mulige repræsentationer af tal for de positive tal, den anden halvdel repræsenterer deres respektive additive inverser . Parene med indbyrdes additive inverse tal kaldes komplementer . Således subtraktion af et vilkårligt antal implementeres ved at tilføje dens komplement. Ændring af tegnet på ethvert tal kodes ved at generere dets komplement, hvilket kan udføres ved en meget enkel og effektiv algoritme. Denne metode blev almindeligvis brugt i mekaniske regnemaskiner og bruges stadig i moderne computere . Det generaliserede koncept for radix -komplementet (som beskrevet nedenfor) er også værdifuldt i talteori , såsom i Midys sætning .

De niere komplement af et nummer givet i decimal repræsentation er dannet ved at erstatte hvert ciffer med ni minus dette ciffer. For at trække et decimaltal y ( subtrahend ) fra et andet nummer x ( minuend ) kan to metoder bruges:

I den første metode føjes nines komplement af x til y . Derefter dannes nines komplement af det opnåede resultat for at frembringe det ønskede resultat.

I den anden metode tilføjes nines komplement af y til x, og et tilføjes til summen. Det venstre ciffer '1' i resultatet kasseres derefter. Kassering af '1' til venstre er især praktisk på regnemaskiner eller computere, der bruger et fast antal cifre: der er ingen steder at gå, så det går simpelthen tabt under beregningen. Niernes komplement plus et er kendt som tiernes komplement.

Komplementeringsmetoden kan udvides til andre talbaser ( radiser ); især bruges det på de fleste digitale computere til at udføre subtraktion, repræsentere negative tal i basis 2 eller binær regning og teste underflow og overløb i beregningen.

Numeriske komplementer

Den radix komplement af et n cifret tal y i radix b er per definition . Radix -komplementet opnås lettest ved at tilføje 1 til det formindskede radix -komplement , hvilket er . Da cifferet gentages n gange (fordi ; se også Geometrisk serieformel ), findes det formindskede radixkomplement for et tal ved at supplere hvert ciffer i forhold til (det vil sige at trække hvert ciffer i y fra ). ${\ displaystyle b^{n} -y}$ ${\ displaystyle \ venstre (b^{n} -1 \ højre) -y}$ ${\ displaystyle \ venstre (b^{n} -1 \ højre)}$ ${\ displaystyle b-1}$ ${\ displaystyle b^{n} -1 = (b-1) \ venstre (b^{n-1}+b^{n-2}+\ cdots+b+1 \ højre) = (b-1) b^{n-1} +\ cdots +(b-1)}$ ${\ displaystyle b-1}$ ${\ displaystyle b-1}$

Subtraktionen af y fra x kan udføres som følger. Tilføjelse af det formindskede radixkomplement af x til y resulterer i værdien, eller som er det formindskede radixkomplement af . Det formindskede radix -supplement af dette er værdien . Alternativt vil tilføjelse af radix -komplementet af y til x resultere i værdien eller . Forudsat at y ≤ x , vil resultatet altid være større eller lig med, og at droppe den indledende '1' er det samme som at trække fra , gøre resultatet eller bare det ønskede resultat. ${\ displaystyle b^{n} -1-x+y}$ ${\ displaystyle b^{n} -1- (xy)}$ ${\ displaystyle xy}$ ${\ displaystyle xy}$ ${\ displaystyle x+b^{n} -y}$ ${\ displaystyle x-y+b^{n}}$ ${\ displaystyle b^{n}}$ ${\ displaystyle b^{n}}$ ${\ displaystyle x-y+b^{n} -b^{n}}$ ${\ displaystyle xy}$

I decimalnummereringssystemet kaldes radix -komplementet tiens komplement og det formindskede radix komplementerer niernes komplement . I binær er radix supplement kaldet to-komplement og den formindskede radix supplere dem supplement . Navngivningen af komplementer i andre baser er den samme. Nogle mennesker, især Donald Knuth , anbefaler at bruge placeringen af apostrofen til at skelne mellem radix -komplementet og det formindskede radix -komplement. I denne brug, den fire-komplement refererer til radix komplement af et tal i bunden fire, mens fire supplement er den formindskede radix komplement af et tal i bunden 5. Men sondringen er ikke vigtig, når radix fremgår (næsten altid) , og den subtile forskel i apostrofplacering er ikke almindelig praksis. De fleste forfattere bruger ens og ni's komplement , og mange stilmanualer udelader apostrofen, anbefaler dem og ni komplement .

Decimal eksempel

Ciffer	Nies komplement
0	9
1	8
2	7
3	6
4	5
5	4
6	3
7	2
8	1
9	0

Nines komplement til et decimaltal er det tal, der skal tilføjes til det for at producere 9; komplementet af 3 er 6, komplementet af 7 er 2 og så videre, se tabel. For at danne niernes komplement til et større tal erstattes hvert ciffer med dets niers komplement.

Overvej følgende subtraktionsproblem:

  873  [x, the minuend]
- 218  [y, the subtrahend]

Første metode

Vi beregner nines komplement af minuend, 873. Føj det til subtrahend 218, og bereg derefter nines komplement af resultatet.

  126  [nines' complement of x = 999 - x]
+ 218  [y, the subtrahend]

=

  344  [999 - x + y]

Beregn nu niernes komplement af resultatet

  344  [result]
  655  [nine's complement of 344 = 999 - (999 - x + y) = x - y, the correct answer]

Anden metode

Vi beregner nines komplement på 218, hvilket er 781. Fordi 218 er tre cifre lang, er det det samme som at trække 218 fra 999.

Dernæst tages summen af x og niernes komplement af y :

  873  [x]
+ 781  [nines' complement of y = 999 - y]

=

 1654  [999 + x - y]

Det førende "1" ciffer falder derefter, hvilket giver 654.

 1654
-1000  [-(999 + 1)]

=

  654  [x - y - 1]

Dette er endnu ikke korrekt. Vi har i det væsentlige tilføjet 999 til ligningen i det første trin. Derefter fjernede vi 1000, da vi tabte den førende 1 i resultatet 1654 ovenfor. Dette vil dermed gøre det svar, vi får (654) til et mindre end det korrekte svar . For at løse dette skal vi tilføje 1 til vores svar: ${\ displaystyle (xy)}$

  654
+   1

=

  655  [x - y]

Tilføjelse af en 1 giver 655, det korrekte svar på vores originale subtraktionsproblem. Vi kunne have sprunget over dette sidste trin med at tilføje 1, hvis vi i stedet tog tiernes komplement af y i det første trin.

Antal tal

I det følgende eksempel har resultatet af subtraktionen færre cifre end x :

  123410  [x, the minuend]
- 123401  [y, the subtrahend]

Anvendelse af den første metode summen af niere komplement af x og y er

  876589  [nines' complement of x]
+ 123401  [y]

=

Nines komplement på 999990 er 000009. Fjernelse af de førende nuller giver 9 det ønskede resultat.

Hvis subtrahend, y , har færre cifre end minuend, skal x , førende nuller tilføjes i den anden metode. Disse nuller bliver førende ni, når komplementet tages. For eksempel:

  48032  [x]
-   391  [y]

kan omskrives

  48032  [x]
- 00391  [y with leading zeros]

Udskiftning af 00391 med sine nines komplement og tilføjelse af 1 giver summen:

  48032  [x]
+ 99608  [nines' complement of y]
+     1

=

At slippe den førende "1" giver det korrekte svar: 47641.

Binær metode

Binært ciffer	Enes komplement
0	1
1	0

Komplementmetoden er især nyttig i binær (radix 2), da komplementet meget let opnås ved at invertere hver bit (ændre '0' til '1' og omvendt). Tilføjelse af 1 for at få de tos komplement kan gøres ved at simulere en carry i den mindst betydelige bit. For eksempel:

  0110 0100  [x, equals decimal 100]
- 0001 0110  [y, equals decimal 22]

bliver summen:

  0110 0100  [x]
+ 1110 1001  [ones' complement of y = 1111 1111 - y]
+         1  [to get the two's complement = 1 0000 0000 - y]
===========
 10100 1110  [x + 1 0000 0000 - y]

Fælder man initialen "1", får man svaret: 0100 1110 (svarer til decimal 78)

Negative tal repræsentationer

Komplementmetoden forudsætter normalt, at operanderne er positive, og at y ≤ x , logiske begrænsninger givet, at tilføjelse og subtraktion af vilkårlige heltal normalt udføres ved at sammenligne tegn, tilføje de to eller trække de mindre fra de større og give resultatet det korrekte skilt.

Lad os se, hvad der sker, hvis x < y . I så fald vil der ikke være et "1" -ciffer, der skal stryges efter tilføjelsen, da det vil være mindre end . For eksempel (i decimal): ${\ displaystyle x-y+b^{n}}$ ${\ displaystyle b^{n}}$

  185  [x]
- 329  [y]

At supplere y og tilføje giver:

  185  [x]
+ 670  [nines' complement of y]
+   1

=

På dette tidspunkt er der ingen enkel måde at afslutte beregningen på ved at trække fra (1000 i dette tilfælde); man kan ikke bare ignorere en ledende 1. Det forventede svar er −144, hvilket ikke er så langt væk som det ser ud til; 856 er tilfældigvis tiernes supplement til 144. Dette problem kan løses på en række måder: ${\ displaystyle b^{n}}$

Ignorer problemet. Dette er rimeligt, hvis en person betjener en beregningsanordning, der ikke understøtter negative tal, da det er let for mennesker at sammenligne de to operander før beregningen, så de kan indtastes i den rigtige rækkefølge og kontrollere, at resultatet er rimeligt. .
Brug den samme metode til at trække 856 fra 1000, og tilføj derefter et negativt tegn til resultatet.
Repræsentere negative tal som radix komplementerer deres positive modstykker. Tal mindre end anses for positive; resten betragtes som negative (og deres størrelse kan opnås ved at tage radix -komplementet). Dette fungerer bedst for lige radiser, da tegnet kan bestemmes ved at se på det første ciffer. For eksempel er tal i ti's komplementnotation positive, hvis det første ciffer er 0, 1, 2, 3 eller 4 og negativt, hvis 5, 6, 7, 8 eller 9. Og det fungerer meget godt i binært siden det første bit kan betragtes som et tegn bit: tallet er positivt, hvis tegnet bit er 0 og negativt, hvis det er 1. Faktisk bruges tos komplement i de fleste moderne computere til at repræsentere signerede tal. ${\ displaystyle b^{n}/2}$
Suppler resultatet, hvis der ikke er udførelse af det mest betydningsfulde ciffer (en indikation på, at x var mindre end y ). Dette er lettere at implementere med digitale kredsløb end at sammenligne og bytte operander. Men da at tage radix -komplementet kræver tilføjelse af 1, er det svært at gøre direkte. Heldigvis kan et trick bruges til at komme uden om denne tilføjelse: I stedet for altid at indstille en carry i det mindst signifikante ciffer ved at trække fra, bruges udførelsen af det mest signifikante ciffer som carry input til det mindst signifikante ciffer (en operation kaldet en ende-rundt-bære ). Så hvis y ≤ x , tilføjes bæreværdien fra det mest betydningsfulde ciffer, der normalt ville blive ignoreret, hvilket giver det korrekte resultat. Og hvis ikke, tilføjes 1 ikke, og resultatet er et mindre end svarets radix -komplement, eller det formindskede radix -komplement, som ikke kræver en tilføjelse for at opnå. Denne metode bruges af computere, der bruger tegn og størrelse til at repræsentere signerede numre.

Praktiske anvendelser

Comptometer fra 1920'erne, med ni 'komplementer markeret på hver tast

Komplementmetoden blev brugt i mange mekaniske lommeregnere som et alternativ til at køre gearene baglæns. For eksempel:

Pascals lommeregner havde to sæt resultatcifre, et sort sæt, der viser det normale resultat, og et rødt sæt, der viser nines komplement til dette. En vandret lamel blev brugt til at dække over et af disse sæt og afsløre det andet. For at trække fra blev de røde cifre udsat og sat til 0. Derefter blev niernes komplement af minuend indtastet. På en eller anden maskine kan dette gøres ved at ringe ind i minuend ved hjælp af inderhjul af komplementer (dvs. uden mentalt at skulle bestemme nines komplement til minuend). Ved at vise disse data i komplementvinduet (rødt sæt) kunne operatøren se nines komplement af nines komplement til minuend, det vil sige minuend. Lamellen blev derefter flyttet for at afsløre de sorte cifre (som nu viste nines komplement til minuend) og subtrahend blev tilføjet ved at ringe den ind. Endelig måtte operatøren flytte lamellen igen for at læse det korrekte svar.
Den Comptometer havde nitaller komplement cifre trykt med mindre typen sammen med de normale cifre på hver tast. For at trække fra forventedes det, at operatøren mentalt trak 1 fra subtrahend og indtast resultatet ved hjælp af de mindre cifre. Da subtraktion af 1 før komplementering svarer til at tilføje 1 bagefter, vil operatøren således effektivt tilføje ti's komplement til subtrahend. Operatøren havde også brug for at holde "fanen for subtraktionsafbrydelse" nede, svarende til svarets ciffer længst til venstre. Denne fane forhindrede transporten i at blive spredt forbi den, Comptometers metode til at slippe den første 1 fra resultatet.
Den Curta regnemaskine Benyttes metoden med komplementer til subtraktion, og det lykkedes at skjule dette fra brugeren. Tal blev indtastet ved hjælp af cifferindgangsslider langs siden af enheden. Tallet på hvert objektglas blev tilføjet til en resultattæller ved hjælp af en gearmekanisme, der aktiverede knaster på en roterende "echelon -tromle" (også kaldet "step drum"). Tromlen blev drejet ved hjælp af en håndsving på toppen af instrumentet. Antallet af knaster, som hvert ciffer stødte på, når håndsvinget drejes, blev bestemt af værdien af det ciffer. For eksempel, hvis et dias er indstillet til dets "6" -position, vil der blive stødt på en række med 6 knaster omkring tromlen svarende til den position. For subtraktion blev tromlen forskudt lidt, før den blev drejet, hvilket flyttede en anden række knaster på plads. Denne alternative række indeholdt nines komplement af cifrene. Således havde rækken med 6 knaster, der havde været i position til tilføjelse, nu en række med 3 knaster. Den skiftede tromle aktiverede også en ekstra knast, der tilføjede 1 til resultatet (efter behov for komplementeringsmetoden). Den altid tilstedeværende ti's komplement "overløb 1", som udførtes ud over resultatregisterets mest betydningsfulde ciffer, blev i realiteten kasseret.

I computere

Brug af komplementeringsmetoden er allestedsnærværende i digitale computere, uanset hvilken repræsentation der bruges til signerede numre. Det krævede kredsløb afhænger imidlertid af repræsentationen:

Hvis tos komplementrepræsentation bruges, kræver subtraktion kun at vende bitene i subtrahenden og indsætte en carry i den bit længst til højre.
At bruge ens komplementsrepræsentation kræver invertering af bitene i subtrahenden og tilslutning af udførelsen af den mest betydningsfulde bit til indføringen af den mindst signifikante bit (end-around carry).
Brug af tegnstørrelsesrepræsentation kræver kun komplementering af subtrahendens tegnbit og tilføjelse, men additions-/subtraktionslogikken skal sammenligne tegnbitene, supplere et af inputene, hvis de er forskellige, implementere en end-around-bæring og supplere resultat, hvis der ikke var carry fra den mest betydningsfulde bit.

Manuelle anvendelser

Metoden til komplimenter blev brugt til at rette fejl, når regnskabsbøger blev skrevet i hånden. For at fjerne en post fra en kolonne med tal kan revisoren tilføje en ny post med tiens komplement af tallet for at trække fra. Der blev tilføjet en bjælke over cifrene i denne post for at angive dens særlige status. Det var derefter muligt at tilføje hele talekolonnen for at opnå det korrigerede resultat.

Supplering af summen er praktisk for kasserere, der foretager ændringer for et køb fra valuta i en enkelt pålydende værdi på 1, der er hævet til et helt tal i valutaens base. For decimalvalutaer, der ville være 10, 100, 1.000 osv., F.eks. En regning på $ 10,00.

I folkeskoleuddannelsen

På folkeskoler undervises eleverne undertiden i metoden til komplimenter som en genvej, der er nyttig i hovedregning . Subtraktion udføres ved at tilføje tiens komplement til subtrahend , som er nines komplement plus 1. Resultatet af denne tilføjelse bruges, når det er klart, at forskellen vil være positiv, ellers bruges tiens komplement til tilføjelsens resultat med den markeret som negativ. Den samme teknik fungerer til at trække fra på en tilføjelsesmaskine.

Se også

To komplement - specialcase til binære computere

Referencer

^ Florida Tech
^ Enkel betjeningsvejledning til det kontrollerede nøglekomptometer , Comptometer Division, Felt and Tarrant Mfg. Co., Chicago, 1917, s. 12
^ Carl Barnett Allendoerfer (1971). Aritmetiske og geometriske principper for folkeskolelærere . Macmillan.

[1] Florida Tech

[2] Enkel betjeningsvejledning til det kontrollerede nøglekomptometer , Comptometer Division, Felt and Tarrant Mfg. Co., Chicago, 1917, s. 12

[3] Carl Barnett Allendoerfer (1971). Aritmetiske og geometriske principper for folkeskolelærere . Macmillan.

Languages

In other projects