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

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

 

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

Google       Google       13. 2. 2012       15 634×

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 Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Touto roční dobou, kdy je zem pokrytá barevným listím a prsty křehnou v mrazivých ránech, se obvykle těšíme na zbrusu novou verzi RAD Studia. Letos si však ale budeme muset počkat na Godzillu a Linux až do jara. Vezměme tedy za vděk alespoň updatem 2 a jelikož dle vyjádření pánů z Embarcadero se budou nové věci objevovat průběžně, pojďme se na to tedy podívat.

Reklama
Reklama
Obrázek ke článku Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Stále rostoucí zájem o cloudové služby i maximální důraz na pružnost, spolehlivost a bezpečnost IT vedou k výrazným inovacím v datových centrech. V infrastruktuře datových center hraje stále významnější roli software a stále častěji se lze setkat s hybridními přístupy k jejich budování i provozu.

Obrázek ke článku Konference: Mobilní technologie mají velký potenciál pro byznys

Konference: Mobilní technologie mají velký potenciál pro byznys

Firmy by se podle analytiků společnosti Gartner měly  rychle přizpůsobit skutečnosti, že mobilní technologie už zdaleka nejsou horkou novinkou, ale standardní součástí byznysu. I přesto - nebo možná právě proto - tu nabízejí velký potenciál. Kde tedy jsou ty největší příležitosti? I tomu se bude věnovat již čtvrtý ročník úspěšné konference Mobilní řešení pro business.

Obrázek ke článku Hackerský kongres přiveze v září do Prahy špičky světové kryptoanarchie

Hackerský kongres přiveze v září do Prahy špičky světové kryptoanarchie

Hackerský kongres HCPP16 pořádá od 30. září do 2. října nezisková organizace Paralelní Polis již potřetí, a to ve stejnojmenném bitcoinovém prostoru v pražských Holešovicích. Letos přiveze na třídenní konferenci přes 40 většinou zahraničních speakerů – lídrů z oblastí technologií, decentralizované ekonomiky, politických umění a aktivismu. Náměty jejich přednášek budou také hacking, kryptoměny, věda, svoboda nebo kryptoanarchie.

loadingtransparent (function() { var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true; po.src = 'https://apis.google.com/js/plusone.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s); })();
Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý