Metoda doplňků - Method of complements

Doplňte čísla na sčítacím stroji c. 1910. Menší čísla, která se používají při odčítání, jsou devítkovým doplňkem větších čísel, která se používají při sčítání.

V matematice a výpočetní technice je metoda doplňků technikou kódování symetrického rozsahu kladných a záporných celých čísel takovým způsobem, že mohou použít stejný algoritmus (hardware) pro sčítání v celém rozsahu. Pro daný počet míst polovina možných reprezentací čísel kóduje kladná čísla, druhá polovina představuje jejich příslušné aditivní inverze . Dvojice vzájemně aditivních inverzních čísel se nazývají komplementy . Tak odčítání jakékoliv množství se provádí přidáním její komplement. Změna znaménka libovolného čísla je kódována generováním jeho doplňku, což lze provést velmi jednoduchým a efektivním algoritmem. Tato metoda se běžně používala v mechanických kalkulačkách a stále se používá v moderních počítačích . Zobecněný koncept radixového komplementu (jak je popsán níže) je cenný také v teorii čísel , například v Midyově větě .

The doplňkem Nines' z množství uvedeného v desítkové vyjádření je tvořen tím, že nahradí každou číslici s devíti minus číslice. K odečtení desetinného čísla y ( subtrahend ) od jiného čísla x ( menuend ) lze použít dvě metody:

V první metodě se k y přidá devítkový doplněk x . Poté se vytvoří komplement devíti získaného výsledku, aby vznikl požadovaný výsledek.

Ve druhé metodě se devítkový doplněk y přičte k x a jeden se přičte k součtu. Nejlevnější číslice '1' výsledku je poté zahozena. Vyřazení levého „1“ je obzvláště výhodné na kalkulačkách nebo počítačích, které používají pevný počet číslic: není kam jít, takže se během výpočtu jednoduše ztratí. Doplněk devíti plus jeden je znám jako doplněk desítek.

Metodu doplňků lze rozšířit na další číselné báze ( radice ); zejména se na většině digitálních počítačů používá k provádění odčítání, reprezentování záporných čísel v základně 2 nebo binární aritmetice a testování podtečení a přetečení při výpočtu.

Numerické doplňky

Radix doplněk z n číslo číslice y v radix B je podle definice . Radixový komplement se nejsnáze získá přidáním 1 ke zmenšenému radixovému komplementu , což je . Protože se číslice opakuje nkrát (protože ; viz také Vzorec geometrické řady ), zmenšený radixový doplněk čísla se najde doplněním každé číslice vzhledem k (to znamená odečtením každé číslice v y od ). ${\ Displaystyle b^{n} -y}$${\ Displaystyle \ left (b^{n} -1 \ right) -y}$${\ Displaystyle \ left (b^{n} -1 \ right)}$${\ displaystyle b-1}$${\ Displaystyle b^{n} -1 = (b-1) \ left (b^{n-1}+b^{n-2}+\ cdots+b+1 \ right) = (b-1) b^{n-1} +\ cdots +(b-1)}$${\ displaystyle b-1}$${\ displaystyle b-1}$

Odečtení y od x lze provést následujícím způsobem. Sečtením zmenšeného radixového komplementu x k y se získá hodnota nebo, která je zmenšeným radixovým komplementem . Snížený radixový doplněk tohoto je hodnota . Alternativně přidání radixového doplňku y k x vede k hodnotě nebo . Za předpokladu, že y ≤ x , bude výsledek vždy větší nebo roven a vynechání počáteční „1“ je stejné jako odečtení , takže výsledek nebo jen požadovaný výsledek. ${\ 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}$

V systému desítkového číslování se radixový doplněk nazývá desítkový doplněk a zmenšený radix doplňuje doplněk devíti . V binární podobě se radixový doplněk nazývá komplement těchto dvou a zmenšený radix doplňuje komplement těch . Pojmenování doplňků v jiných základnách je podobné. Někteří lidé, zejména Donald Knuth , doporučují použít umístění apostrofu k rozlišení mezi radixovým komplementem a zmenšeným radixovým komplementem. V tomto použití se doplněk čtyř týká radixového doplňku čísla v základně čtyři, zatímco doplněk čtyř je zmenšený radixový doplněk čísla v základně 5. Rozlišování však není důležité, když je radix zřejmý (téměř vždy) , a jemný rozdíl v umístění apostrofu není běžnou praxí. Většina spisovatelů používat něčí a devíti jeho doplněk , a mnoho manuály stylu vynechat apostrof, doporučovat ones a devitkovou doplněk .

Desetinný příklad

Devítkový doplněk desítkové číslice je číslo, které k ní musí být přidáno k vytvoření 9; doplněk 3 je 6, doplněk 7 je 2 atd., viz tabulka. K vytvoření devítkového doplňku většího počtu je každá číslice nahrazena jeho devítkovým doplňkem.

Zvažte následující problém odčítání:

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

První metoda

Vypočítáme devítkový doplněk menuendu, 873. Přidejte to k podtrendu 218, poté vypočítejte devítkový doplněk výsledku.

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

=

  344  [999 - x + y]

Nyní spočítejte výsledek devíti

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

Druhá metoda

Vypočítáme doplněk devíti 218, což je 781. Protože 218 je dlouhý tři číslice, je to stejné, jako odečíst 218 od 999.

Dále se vezme součet x a doplněk devítek y :

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

=

 1654  [999 + x - y]

Úvodní číslice „1“ je poté vypuštěna, což dává 654.

 1654
-1000  [-(999 + 1)]

=

  654  [x - y - 1]

To ještě není správné. V podstatě jsme do rovnice v prvním kroku přidali 999. Poté jsme odstranili 1000, když jsme ve výsledku 1654 výše shodili úvodní 1. To způsobí, že odpověď, kterou dostaneme (654), bude o jednu menší než správná odpověď . Abychom to vyřešili, musíme k naší odpovědi přidat 1: ${\ displaystyle (xy)}$

  654
+   1

=

  655  [x - y]

Sečtením 1 dostaneme 655, správnou odpověď na náš původní problém odčítání. Tento poslední krok přidání 1 bychom mohli přeskočit, kdybychom místo toho v prvním kroku vzali desítkový doplněk y.

Velikost čísel

V následujícím příkladu má výsledek odčítání méně číslic než x :

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

Použití první metodu součet komplementu devítky ze dne x a y je

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

=

  999990

Devítkový doplněk 999990 je 000009. Odstranění úvodních nul dává 9 požadovaný výsledek.

Pokud má podtrend, y , méně číslic než minuend, x , musí být do druhé metody přidány úvodní nuly. Když se vezme doplněk, tyto nuly se stanou vedoucími devítkami. Například:

  48032  [x]
-   391  [y]

lze přepsat

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

Nahrazením 00391 jeho devítkovým doplňkem a přidáním 1 vznikne součet:

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

=

 147641

Odhozením úvodní „1“ získáte správnou odpověď: 47641.

Binární metoda

Metoda komplementů je zvláště užitečná v binárních (radix 2), protože jejich komplement je velmi snadno získán převrácením každého bitu (změnou '0' na '1' a naopak). Přidání 1 k získání doplňku těchto dvou lze provést simulací přenosu na nejméně významný bit. Například:

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

se stává součtem:

  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]

Vypustením počáteční „1“ získáte odpověď: 0100 1110 (rovná se desítkové hodnotě 78)

Záporné číslo reprezentace

Metoda doplňků obvykle předpokládá, že operandy jsou kladné a že y ≤ x , logická omezení daná tím, že sčítání a odčítání libovolných celých čísel se běžně provádí porovnáváním znamének, sčítáním dvou nebo odečtením menších od větších a výsledkem je správný podepsat.

Podívejme se, co se stane, když x < y . V takovém případě nebude po sčítání přeškrtnuta číslice „1“, protože bude menší než . Například (v desítkové soustavě): ${\ Displaystyle x-y+b^{n}}$${\ displaystyle b^{n}}$

  185  [x]
- 329  [y]

Doplněním y a přidáním získáte:

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

=

  856

V tomto okamžiku neexistuje jednoduchý způsob, jak dokončit výpočet odečtením (v tomto případě 1 000); nelze jednoduše ignorovat úvodní 1. Očekávaná odpověď je −144, což není tak daleko, jak se zdá; 856 je shodou okolností desítkovým doplňkem 144. Tento problém lze řešit několika způsoby: ${\ displaystyle b^{n}}$

• Problém ignorujte. To je rozumné, pokud osoba obsluhuje výpočetní zařízení, které nepodporuje záporná čísla, protože porovnání obou operandů před výpočtem, aby je bylo možné zadat ve správném pořadí, a ověření, že výsledek je přiměřený, je pro člověka snadné .
• Stejnou metodou odečtěte 856 od 1000 a pak k výsledku přidejte záporné znaménko.
• Záporná čísla reprezentujte jako radixový doplněk jejich kladných protějšků. Čísla menší než jsou považována za kladná; zbytek je považován za negativní (a jejich velikost lze získat odebráním radixového komplementu). To funguje nejlépe pro sudé radice, protože znaménko lze určit pohledem na první číslici. Například čísla v desítkovém zápisu komplementu jsou kladná, pokud je první číslice 0, 1, 2, 3 nebo 4, a záporná, pokud 5, 6, 7, 8 nebo 9. A funguje to velmi dobře binárně od prvního bit lze považovat za znaménkový bit: číslo je kladné, pokud je znaménkový bit 0, a záporné, pokud je 1. Skutečně, dvojkový doplněk se ve většině moderních počítačů používá k reprezentaci podepsaných čísel.${\ Displaystyle b^{n}/2}$
• Doplňte výsledek, pokud nedojde k provedení nejvýznamnější číslice (údaj, že x bylo menší než y ). To je jednodušší implementovat s digitálními obvody než porovnávat a vyměňovat operandy. Ale vzhledem k tomu, že užívání radixového doplňku vyžaduje přidání 1, je obtížné to udělat přímo. Naštěstí lze tento doplněk obejít trikem: Místo toho, abyste při odečítání vždy nastavili přenos na nejméně významnou číslici, jako vstup pro přenesení do nejméně významné číslice se použije provedení nejvýznamnější číslice (operace s názvem end-around carry ). Pokud tedy y ≤ x , sečte se přenesení od nejvýznamnější číslice, která by byla normálně ignorována, čímž se získá správný výsledek. A pokud ne, 1 se nepřidá a výsledek je o jeden menší než radixový doplněk odpovědi nebo zmenšený radixový komplement, který k získání nevyžaduje přidání. Tuto metodu používají počítače, které používají znak a velikost k reprezentaci podepsaných čísel.

Praktické využití

Comptometr z dvacátých let minulého století, na každém klíči jsou vyznačeny doplňky devíti

Metoda doplňků byla použita v mnoha mechanických kalkulačkách jako alternativa k chodu ozubených kol vzad. Například:

• Pascalova kalkulačka měla dvě sady číslic výsledků, černá sada zobrazující normální výsledek a červená sada zobrazující doplněk devíti. K zakrytí jedné z těchto sad byla použita horizontální lamela, druhá odhalila. Pro odečtení byly červené číslice vystaveny a nastaveny na 0. Poté byl zadán doplněk devíti minut. Na nějakém stroji to bylo možné provést vytáčením v nabídce pomocí vnitřních koleček doplňků (tj. Bez nutnosti mentálně určovat doplněk devítek nabídky). Při zobrazování těchto dat v okně komplementu (červená sada) mohl operátor vidět devítkový doplněk devítkového doplňku menuend, to je minuend. Lamela byla poté přesunuta, aby se odhalily černé číslice (které nyní zobrazovaly doplnění devíti menuend) a podtrend byl přidán vytočením. Nakonec operátor musel znovu posunout lať, aby přečetl správnou odpověď.
• Comptometer měl komplementu Číslice devítky vytištěny malým písmem spolu s normálními číslic na každé klávese. Odečíst se očekávalo, že operátor mentálně odečte 1 od podtrendu a zadá výsledek pomocí menších číslic. Protože odečtení 1 před komplementací je ekvivalentní přidání 1 poté, operátor by tedy efektivně přidal desítkový doplněk subtrahendu. Operátor také potřeboval podržet „záložku mezního odčítání“ odpovídající číslici úplně vlevo od odpovědi. Tato záložka zabraňovala šíření přenosu za ním, což byla metoda Comptometru, která z výsledku vypustila počáteční 1.
• Curta kalkulačky použili metodu doplňků pro odčítání, a podařilo se mu skrývat to od uživatele. Čísla byla zadávána pomocí posuvníků pro zadávání číslic podél boku zařízení. Číslo na každém snímku bylo přidáno k počítadlu výsledků pomocí převodového mechanismu, který zabíral vačky na rotujícím „echelonovém bubnu“ (aka „krokovém bubnu“). Buben byl otočen pomocí kliky na horní části nástroje. Počet vaček, s nimiž se setkala každá číslice při otáčení klikou, byl určen hodnotou této číslice. Pokud je například posuvník nastaven do polohy „6“, kolem bubnu odpovídající této poloze by se objevila řada 6 vaček. Pro odečtení byl buben mírně posunut, než byl otočen, což přesunulo jinou řadu vaček do polohy. Tento alternativní řádek obsahoval doplnění číslic devítkami. Řada 6 vaček, které byly v pozici pro přidání, měla nyní řadu se 3 vačkami. Posunutý buben také zapojil jednu další vačku, která přidala 1 k výsledku (jak je požadováno pro metodu doplňků). Vždy přítomný desítkový doplněk „přetečení 1“, který se uskutečnil za nejvýznamnější číslicí registru výsledků, byl ve skutečnosti vyřazen.

V počítačích

Použití metody doplňků je v digitálních počítačích všudypřítomné, bez ohledu na reprezentaci použitou pro podepsaná čísla. Požadované obvody však závisí na reprezentaci:

• Pokud je použita reprezentace komplementu dvou, odčítání vyžaduje pouze invertování bitů subtrendu a nastavení přenosu na bit úplně vpravo.
• Použití jejich komplementární reprezentace vyžaduje invertování bitů podtrendu a připojení provádění nejvýznamnějšího bitu k přenosu nejméně významného bitu (end-around carry).
• Použití reprezentace znaménkové velikosti vyžaduje pouze doplnění znaménkového bitu podtrendu a sčítání, ale logika sčítání/odčítání potřebuje porovnat znaménkové bity, doplnit jeden ze vstupů, pokud se liší, implementovat end-around carry a doplnit výsledek, pokud nedošlo k přenosu z nejvýznamnějšího bitu.

Ruční použití

K opravě chyb při ručním psaní účetních knih byla použita metoda doplňků. Chcete -li odebrat záznam ze sloupce čísel, účetní by mohl přidat nový záznam s doplňkem čísla k odečtení. K číslům tohoto záznamu byl přidán pruh, který označuje jeho zvláštní stav. Poté bylo možné přidat celý sloupec obrázků, abychom získali opravený výsledek.

Doplnění částky je užitečné pro pokladní, kteří provádějí změnu při nákupu z měny v jediné nominální hodnotě 1, která se zvýší na celočíselnou moc základny měny. U desetinných měn, které by byly 10, 100, 1 000 atd., Např. Účet 10,00 USD.

Ve školním vzdělávání

Na základních školách se studenti někdy učí metodu doplňků jako zkratku užitečnou v mentální aritmetice . Odečtení se provede sečtením doplňku podtrendu , který je devítkovým doplňkem plus 1. Výsledek tohoto sčítání se použije, když je jasné, že rozdíl bude kladný, jinak se s ním použije doplnění výsledku sčítání označeno jako negativní. Stejná technika funguje pro odčítání na sčítacím stroji.

Viz také

• Doplněk dvou - speciální případ pro binární počítače

Reference