Řešíme zdrojový kód – algoritmus násobení
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

Řešíme zdrojový kód – algoritmus násobeníŘešíme zdrojový kód – algoritmus násobení

 
Hledat
Vybavení pro Laser Game
Spuštěn Filmový magazín
Laser Game Brno
Laser Game Ostrava

Řešíme zdrojový kód – algoritmus násobení

Google       Google       13. 2. 2012       21 403×

V článku budeme tak trochu vynalézat kolo. Ukážeme si zajímavý postup odvození algoritmu celočíselného násobení. Postup a tipy mohou být inspirací čtenáři, tréningem logického myšlení a věřím že i zábavou.

Reklama
Reklama

Pro násobení dvou přirozených čísel platí:

Totéž zapíšu v kódu, nejlépe se zde hodí přes cyklus for:

y = 0;
for (i = 0; i < a; i++) {
    y += b;	 
}

Tento kód násobí přirozená čísla včetně nuly, jinými slovy celá nezáporná čísla. Násobení celých čísel, z nichž alespoň jedno je záporné, je pro úplnost uvedeno ke konci článku rozšířením odvozeného kódu i na záporná čísla.

Příklad funkce výchozího algoritmu násobení pro vstupy a = 9; b = 13

Zapsal jsem zadání do formy výchozího kódu, ale je to zoufale pomalý algoritmus násobení.
Nevadí, jeho výrazné urychlení je předmětem následujícího textu.

Poznámka:
Nedefinuju typ proměnných a, b, i, y. Bylo by to překážkou obecnosti. V průběhu odvození předpokládám, že pro jakýkoli vstup a hodnoty celých čísel ve všech místech kódu existuje vhodná (abstraktní) implementace, schopná proměnné uchovávat a operace s nimi provádět bez přetečení. Tedy navzdory tomu, že nejsme schopni držet v paměti celá čísla od mínus nekonečna do nekonečna, je možné pro jakýkoli vstup průběžně „držet hodnoty“ čísel, jež se „za běhu objeví“. Podrobněji k tomu viz můj delší příspěvek v názorech k článku Řešíme zdrojový kód – vztahy a pravidla.

Pomůcky pro řešení

Užitečnou pomůckou při úpravách cyklu je zkusit cyklus rozbalit, stačí pro pár průchodů. U uvedeného kódu je to snadné:

y += b;
y += b;
y += b;
y += b;
.
.
.

Můžu spojit dva průchody cyklu do jednoho. Snížím tím původní počet opakování cyklu na polovinu:

y += 2*b;
y += 2*b;
.
.
.

Řešení kódu

Poznámka:
Při každé následující úpravě kódu je výsledná funkce kódu po úpravě stejná jako funkce kódu před úpravou, tj. budu provádět ekvivalentní úpravy kódu. Nevypisuju v průběhu řešení na začátku kódů inicializaci y = 0;, to všude zůstává.

Úpravu naznačenou výše provedu ve výchozím kódu. Počet opakování cyklu vydělím dvěma a tělo cyklu naopak opakuju dvakrát. Musím přitom ošetřit případ, kdy je zbytek po celočíselném dělení dvěma nenulový a je třeba původní tělo cyklu provést ještě jednou:

for (i = 0; i < a / 2; i++) {
    y += 2 * b; // y += b; y += b;	 
}
if (a % 2 != 0) y += b;

Stejné „dělení cyklu“ na polovinu provedu znovu:

for (i = 0; i < a/2 / 2; i++) {
    y += 2 * 2*b; // y += 2*b; y += 2*b;	 
}
if (a/2 % 2 != 0) y += 2*b;
if (a   % 2 != 0) y += b;

A ještě jednou:

for (i = 0; i < a/2/2 / 2; i++) {
    y += 2 * 2*2*b; // y += 2*2*b; y += 2*2*b;	 
}
if (a/2/2 % 2 != 0) y += 2*2*b;
if (a/2   % 2 != 0) y += 2*b;
if (a     % 2 != 0) y += b;

S každou takovou úpravou přibývá pod cyklem jeden nový řádek kódu. Počet opakování cyklu naopak rychle klesá (a/2, a/4, a/8, …). Budu-li pokračovat ve stejných úpravách, dojde pro každou vstupní hodnotu proměnné a dříve či později k tomu, že výraz a / 2^N v podmínce cyklu bude roven nule a podmínka pokračování cyklu i < a / 2^N nebude splněna ani pro i = 0. Od okamžiku, kdy k tomu dojde, se tělo cyklu nevykoná už ani jednou. Proto je původní cyklus zbytečný, pryč s ním:

.
. 
.   
if (a/2/2 % 2 != 0) y += 2*2*b;
if (a/2   % 2 != 0) y += 2*b;
if (a     % 2 != 0) y += b;

V celém kódu se mění jen proměnná y, jejíž změna závisí na proměnných ab, které se nemění, a platí: y + m + n = y + n + m (m, n – libovolná čísla). Proto můžu obrátit pořadí podmínek:

if (a     % 2 != 0) y += b;
if (a/2   % 2 != 0) y += 2*b;
if (a/2/2 % 2 != 0) y += 2*2*b;
.
. 
.

Nyní trochu obecněji využiju princip popisovaný v úvodním článku. Každý řádek je možné nahradit za if (d % 2 != 0) y += e;, kde výchozí hodnoty d = a, e = b. Funkce zůstane zachována, když se mezi řádky provede d /= 2;e *= 2. Pomocné proměnné de můžu rovnou zase zpátky přejmenovat na ab:

if (a % 2 != 0) y += b; 
a /= 2;
b *= 2;

if (a % 2 != 0) y += b;
a /= 2;
b *= 2;

if (a % 2 != 0) y += b;
a /= 2;
b *= 2;

.
.
.

V kódu je zatím neznámý počet opakujících se stejných trojic řádku. S každou trojicí se proměnná a celočíselně dělí dvěma, v určitém okamžiku už bude nulová a zůstane nulová, protože 0/2 = 0. Když má proměnná a nulovou hodnotu, je test a % 2 != 0 nepravda a proměnná y se už nikdy nezmění, proto další trojici řádků už pak netřeba provádět (a doplním zpátky vynechávanou inicializaci proměnné y):

y = 0;
while (a != 0) {
    if (a % 2 != 0) y += b;
    a /= 2;
    b *= 2;
}

= Výsledný algoritmus, asymptoticky rychlejší než původní. Jde o variantu Shift-Add algoritmu, často užívaného algoritmu násobení. I dnes najde praktické využití třeba na některých jednočipech, které nemají přímo instrukci pro násobení.

Příklad funkce odvozeného algoritmu násobení pro vstupy a = 9; b = 13

Finální optimalizace

Násobení a dělení dvěma jsou jednoduché operace ekvivalentní bitovým posunům. Test nenulovosti zbytku po dělení dvěma je ekvivalentní maskování nejnižšího bitu proměnné a:

y = 0;
while (a != 0) {
    if (a & 1) y += b;
    a >>= 1;
    b <<= 1;
}

Poznámka:
S tímto algoritmem také souvisí počítání v binární soustavě.

Příklad implementace

Užitím odvozeného algoritmu můžu napsat rutinu pro násobení 16bitových čísel. Mohla by vypadat třeba takto:

unsigned long umul16(unsigned short a, unsigned short b)
{
    if (a > b) swap(a,b);
    unsigned long y = 0;
    unsigned long c = b;
    while (a != 0) {
        if (a & 1) y += c;
        a >>= 1;
        c <<= 1;
    }

    return y;    		
}

V průběhu odvození jsem nedefinoval, jakého rozsahu jsou proměnné. Algoritmus samotný funguje obecně pro libovolnou velikost proměnných. Při implementaci se ale musí dát pozor na možné přetečení. Tady zrovna bylo nutné použít dvojnásobnou šířku pro hodnotu proměnné b (nahrazeno za c), protože se bitově posouvá doleva a docházelo by ke ztrátě vysunutých bitů.

Násobení čísel se znaménkem

Samotná absolutní hodnota výsledku násobení čísel se znaménkem je stejná jako výsledek u násobení bez znamének. Výsledné znaménko při násobení dvou čísel se znaménkem je dáno tabulkou:

a
b
y = a * b
+
+
+
+
-
-
-
+
-
-
-
+

Znaménko čísla je v podstatě k číslu přidaný jeden bit informace navíc, nejčastěji je tento bit přímo uložen v nejvyšším bitu čísla jako „1“ pro „-“. Můžu tu tabulku zapsat takto:

znaménkový bit a
znaménkový bit b
znaménkový bit y
0
0
0
0
1
1
1
0
1
1
1
0

Tato tabulka představuje logickou funkci exkluzivní disjunkce (XOR). Jinak se ji v případě dvou vstupů říká také nonekvivalence, protože jednička je na výstupu jen tehdy, jsou-li hodnoty vstupů rozdílné. Proto násobení čísel se znaménkem můžu provést tak, že zjistím zdali mají vstupní čísla rozdílná znaménka, tato znaménka odstraním, provedu násobení čísel bez znamének a nakonec u výsledku změním znaménko na opačné, když vstupní čísla mají znaménka rozdílná. (Také bych mohl použít operátor  ^)

Příklad implementace násobení se znaménkem

long imul16(short a, short b)
{
    unsigned long y = 0;
    unsigned long c = abs(a);
    unsigned long d = abs(b);

    if (c > d) swap(c, d);

    while (c != 0) {
        if (c & 1) y += d;
        c >>= 1;
        d <<= 1;
    }
    
    if ( (a < 0) != (b < 0) ) {
        return - (long) y;
    } else {
        return (long) y;
    }
}

Poznámka:
Miloslav Ponkrác v diskusi pod článkem dobře dodává, že zjištění znaménka se v praxi dělá rychleji než v příkladu předchozího kódu, tedy místo :

  if ( (a < 0) != (b < 0) ) { ...

se spíše používá:

  if ((a ^ b) < 0) { ...

Tím se XORují se všechny bity a, b. Znaménko je jeden z nich a porovnáním s nulou testuje hodnotu znaménkového bitu ve výsledku toho XOR.

Závěr

Z pomalého algoritmu násobení na začátku máme rychlý algoritmus na konci. Mezitím jsem provedl pár ekvivalentních logických úprav. Postup samotný není všespasitelný, ale v nemálo případech může být užitečný a účinný.

Dobré na podobném postupu je také to, že celý průběh řešení je přesně dokumentován. Každý se tak může přesvědčit a snadno pochopit přímo v kontextu jazyka, kterému jako programátor přirozeně rozumí, jak se postupně došlo k výsledku.

Autorem postavičky CMYKa, zdejšího maskota koukajícího v obrázcích, je Zbyněk Molnár.

×Odeslání článku na tvůj Kindle

Zadej svůj Kindle e-mail a my ti pošleme článek na tvůj Kindle.
Musíš mít povolený příjem obsahu do svého Kindle z naší e-mailové adresy kindle@programujte.com.

E-mailová adresa (např. novak@kindle.com):

TIP: Pokud chceš dostávat naše články každé ráno do svého Kindle, koukni do sekce Články do Kindle.

Hlasování bylo ukončeno    
20 hlasů
Google
Programátor amatér.

Nové články

Obrázek ke článku Konference: Moderní informační systémy podporují automatizaci

Konference: Moderní informační systémy podporují automatizaci

Současná situace v šíření onemocnění Covid-19 klade na řadu firem nové nároky a mnohé z nich jsou nyní více než kdy jindy závislé na nejmodernějších informačních technologiích. Proto i v oblasti podnikových informačních systémů vidíme rostoucí důraz na automatizaci nebo na důslednou integraci. Také o těchto trendech se bude mluvit na konferenci Firemní informační systémy, která se koná 24.9.2020 v pražském Kongresovém centru Vavruška na Karlově náměstí.

Reklama
Reklama
Obrázek ke článku Nebezpečí ukrytá v USB: z nuly na škvarek za pět sekund

Nebezpečí ukrytá v USB: z nuly na škvarek za pět sekund

Za cenu šesti dolarů lze celkem bez obtíží koupit nový, líbivě vyhlížející flash disk. Přidaná hodnota, které se vám spolu s ním dostane, už tak moc líbivá není. To, co se před pár sekundami tvářilo jako externí disk, se po připojení k počítači změní v důmyslné elektrické křeslo, které vaše zařízení v onen příslovečný škvarek promění za pár sekund. Cílovou skupinou pro koupi takových zařízení by mohli být záškodníci, kteří by tímto způsobem osnovali pomstu třeba vůči záletnému partnerovi. 

Obrázek ke článku Znalosti, dovednosti i prestižní titul MBA: Jde to i moderně a online

Znalosti, dovednosti i prestižní titul MBA: Jde to i moderně a online

Snad nikdy není špatná příležitost na investici do hodnotného vzdělání. Obzvlášť v případě, že absolvent dovede teoretické poznatky přetavit v praktické dovednosti, využitelné při řešení problémů i v komunikaci. Právě na to se specializuje studijní program MBA Řízení informačních technologií, vyučovaný na Business Institutu.

Obrázek ke článku Coding Bootcamp Praha: Obor IT krize nepoznamenala, žádaní jsou weboví vývojáři

Coding Bootcamp Praha: Obor IT krize nepoznamenala, žádaní jsou weboví vývojáři

Pandemie Covid-19 otřásla trhem práce v základech. Dopady krize pocítilo celkově až 45 % zaměstnanců. Není divu, že čím dál větší jistotu přináší obor IT. Ten zůstal krizí téměř nepoznamenán a při nutnosti začít dělat věci na dálku se ještě více ukázalo, jak moc mnohé firmy kvalitní IT potřebují. Do IT nyní přicházejí začátečníci, kteří v něm vidí lukrativní budoucnost a jistotu, ale i freelanceři a zaměstnanci z oborů zasažených krizí

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032020 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý