Aritmetika včera a dnes Arithmetics: Past and Present

ˇ ˇ ´ ODBORNA ´ CINNOST ˇ STREDO SKOLSK A ˇ 1. Matematika a statistika Obor SOC:

Aritmetika vˇ cera a dnes Arithmetics: Past and Present

Autor: ˇ Skola: Konzultant:

ˇ ek Skarda ˇ Cenˇ Gymn´ azium Uniˇ cov Gymnazijn´ı 257, 783 91 Uniˇ cov Ing. L’ubom´ıra Balkov´ a, Ph.D.

Uniˇ cov 2012

Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem svou pr´ aci vypracoval samostatnˇe, pouˇzil jsem pouze podklady (literaturu, SW atd.) uvedené v pˇriloˇzeném seznamu a postup pˇri zpracov´ an´ı a dalˇs´ım nakl´ ad´ an´ı s prac´ı je v souladu se zákonem ˇc. 121/2000 Sb., o pr´ avu autorském, o pr´ avech souvisej´ıc´ıch s právem autorským a o zmˇenˇe nˇekterých z´ akon˚ u (autorský zákon) v platném znˇen´ı. V Uniˇcovˇe dne 7. kvˇetna 2012

podpis: .........................

Podˇ ekov´ an´ı

Podˇekovat bych chtˇel pˇredevˇs´ım tˇemto lidem. Mé vedouc´ı práce Ing. L’ubom´ıˇre Balkové, Ph.D., za jej´ı ochotu, cenné rady a nápady. Dále bych chtˇel podˇekovat RNDr. Zuzanˇe Kopeˇcné Voglové a Mgr. Milanu Kuxovi za jejich odborné pˇripom´ınky.

ANOTACE Aˇckoliv se na základn´ıch ˇskolách uˇc´ıme vˇsichni stejné algoritmy pro sˇc´ıtán´ı, odˇc´ıtán´ı, násoben´ı a dˇelen´ı pˇrirozen´ ych ˇc´ısel s tuˇzkou a pap´ırem, je takov´ ych algoritm˚ u velké mnoˇzstv´ı a kaˇzd´ y z nich má své v´ yhody a nev´ yhody. Stejnˇe tak kromˇe algoritm˚ u, které pouˇz´ıvá náˇs poˇc´ıtaˇc k provádˇen´ı aritmetick´ ych operac´ı, existuje celá ˇrada algoritm˚ u, které se mohou hodit napˇr´ıklad ve chv´ıli, kdy je naˇs´ı hlavn´ı u ´lohou násobit obrovská ˇc´ısla nebo kdy máme k dispozici poˇc´ıtaˇce zapojené do s´ıt´ı a s v´ yhodou vyuˇzijeme paraleln´ı algoritmy. Tato práce poskytuje obsáhl´ y seznam existuj´ıc´ıch algoritm˚ u pro základn´ı aritmetické operace a jejich srozumitelné vysvˇetlen´ı. Pro zaj´ımavost popisujeme u historick´ ych metod i u ´roveˇ n matematiky, které se na daném u ´zem´ı v dobˇe vzniku algoritmu dosáhlo, a u v´ yznamn´ ych matematik˚ u, kteˇr´ı se o zmiˇ nované algoritmy zaslouˇzili, uvád´ıme jejich medailony. Nen´ı nám známo, ˇze by takov´ y bohat´ y souhrn algoritm˚ u aritmetick´ ych operac´ı byl nˇekde k dispozici, v pˇrehledném shrnut´ı tedy spoˇc´ıvá hlavn´ı pˇr´ınos této práce. V´ ystupem práce je nav´ıc www stránka http://bimbo.fjfi.cvut.cz/∼soc se srozumiteln´ ym popisem algoritm˚ u v mnoha pˇr´ıpadech doplnˇen´ ym programem, kter´ y algoritmus ilustruje. ˇ ast algoritm˚ ˇ Skarda: ˇ C´ u násoben´ı jsme popsali v ˇclánku L’. Balková, C. Násob´ıme chytˇre?, kter´ y je pˇrijat k publikaci v Pokroc´ıch matematiky, fyziky a astronomie. Kl´ıˇcová slova: aritmetické operace; ˇc´ıselné soustavy; ˇcasová sloˇzitost algoritmu; paraleln´ı algoritmy; redundance

ANNOTATION At any primary school, pupils are taught the same algorithms for addition, subtraction, multiplication, and division of natural numbers. Despite this fact, there exist a huge number of such algorithms and each of them has its advantages and disadvantages. Similarly, in addition to algorithms used by our computers for execution of arithmetical operations, there exist other methods that can be more suitable in certain cases, for instance when one wants to operate with huge numbers or in case one may use a network of computers. This work provides a comprehensive summary of existing algorithms for basic arithmetical operations and their comprehensible explanation. We place the described methods into a historical context when depicting the level of mathematical knowledge in the region where the method in question was invented and we add portraits of important mathematicians who influenced arithmetics. To our knowledge, there has not been so far such a rich summary of algorithms for arithmetical operations. Therefore, the main contribution of this work resides in the clearly arranged comprehensive summary. An additional output is a web page http://bimbo.fjfi.cvut.cz/∼soc where a detailed description of algorithms is supplemented with illustrative computer programs. A part of algorithms concerning multiplication has been described in the paper L’. ˇ Skarda: ˇ Balková, C. Do we multiply in a clever way?, to appear in Pokroky matematiky, fyziky a astronomie. Key words: arithmetical operation; numeration systems; time complexity of an algorithm; parallel algorithms; redundancy

Obsah ´ 1 Uvod

6

2 N´ asoben´ı 2.1 Násoben´ı zpamˇeti . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Násoben´ı s tuˇzkou a pap´ırem . . . . . . . . . . . . . . . . . . . . 2.2.1 Egyptské násoben´ı . . . . . . . . . . . . . . . . . . . . . 2.2.2 Ruské (sedlácké) násoben´ı . . . . . . . . . . . . . . . . . 2.2.3 Indické násoben´ı . . . . . . . . . . . . . . . . . . . . . . ˇ ınské grafické násoben´ı . . . . . . . . . . . . . . . . . . 2.2.4 C´ ˇ ınské poˇcetn´ı násoben´ı . . . . . . . . . . . . . . . . . . 2.2.5 C´ 2.2.6 Al-Chwárizm´ıho násoben´ı . . . . . . . . . . . . . . . . . 2.2.7 Cauchyovo komplementárn´ı násoben´ı . . . . . . . . . . . 2.2.8 Pˇrevod násoben´ı na goniometrické a logaritmické funkce 2.3 Mechanické pom˚ ucky a tabulky . . . . . . . . . . . . . . . . . . 2.3.1 Soroban . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.2 Násoben´ı na linách . . . . . . . . . . . . . . . . . . . . . 2.3.3 Napierovy kosti . . . . . . . . . . . . . . . . . . . . . . . 2.3.4 Tabulky kvadrát˚ u . . . . . . . . . . . . . . . . . . . . . . 2.4 Poˇc´ıtaˇcové násoben´ı . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1 Binárn´ı soustava . . . . . . . . . . . . . . . . . . . . . . 2.4.2 Redundantn´ı binárn´ı soustava . . . . . . . . . . . . . . . 2.4.3 Klasické násoben´ı . . . . . . . . . . . . . . . . . . . . . . 2.4.4 Rychlé násoben´ı . . . . . . . . . . . . . . . . . . . . . . . 3 Dˇ elen´ı 3.1 Dˇelen´ı s tuˇzkou a pap´ırem . . . . . . . 3.1.1 Egyptské dˇelen´ı . . . . . . . . . ˇ ınské poˇcetn´ı dˇelen´ı podle Sun 3.1.2 C´ 3.2 Mechanické pom˚ ucky . . . . . . . . . . 3.2.1 Soroban . . . . . . . . . . . . . 3.2.2 Napierovy kosti . . . . . . . . .

. . . . . . Ziho . . . . . . . . .

. . . . . .

4 V´ ypoˇ cet druh´ e odmocniny 4.1 V´ ypoˇcet druhé odmocniny s tuˇzkou a pap´ırem 4.1.1 Numerick´ y v´ ypoˇcet druhé odmocniny . 4.1.2 Indick´ y v´ ypoˇcet druhé odmocniny . . . ˇ ınsk´ 4.1.3 C´ y v´ ypoˇcet druhé odmocniny . . .

5

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . .

. . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . .

. . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . .

. . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . .

. . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . .

. . . .

. . . . . . . . . . . . . . . . . . . .

7 7 8 8 9 10 10 11 11 12 13 14 14 15 16 16 17 17 18 19 21

. . . . . .

26 26 26 27 28 28 28

. . . .

31 31 31 32 34

5 Sˇ c´ıt´ an´ı 5.1 Sˇc´ıtán´ı s tuˇzkou a pap´ırem ˇ ınské sˇc´ıtán´ı . . . 5.1.1 C´ 5.2 Mechanické pom˚ ucky . . . 5.2.1 Soroban . . . . . . 5.2.2 Sˇc´ıtán´ı na linách .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

´ 6 Uroveˇ n matematiky star´ ych kultur 6.1 Poziˇcn´ı a nepoziˇcn´ı soustavy . . . . 6.2 Egypt . . . . . . . . . . . . . . . . 6.3 Mezopotámie . . . . . . . . . . . . 6.4 Idiánské kmeny Ameriky . . . . . . ˇ ına . . . . . . . . . . . . . . . . . 6.5 C´ 6.6 Starovˇeká Indie . . . . . . . . . . . 6.7 Arabsk´ y svˇet . . . . . . . . . . . . 7 V´ yznamn´ı matematikov´ e 7.1 Al-Chwárizm´ı . . . . . 7.2 John Napier . . . . . . 7.3 Augustin Louis Cauchy 7.4 Jakub Filip Kulik . . . 7.5 Anton´ın Svoboda . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

8 Z´ avˇ er

. . . . .

. . . . . . .

. . . . .

. . . . .

. . . . . . .

. . . . .

. . . . .

. . . . . . .

. . . . .

. . . . .

. . . . . . .

. . . . .

. . . . .

. . . . . . .

. . . . .

. . . . .

. . . . . . .

. . . . .

. . . . .

. . . . . . .

. . . . .

. . . . .

. . . . . . .

. . . . .

. . . . .

. . . . . . .

. . . . .

. . . . .

. . . . . . .

. . . . .

. . . . .

. . . . . . .

. . . . .

. . . . .

. . . . . . .

. . . . .

. . . . .

. . . . . . .

. . . . .

. . . . .

. . . . . . .

. . . . .

. . . . .

. . . . . . .

. . . . .

. . . . .

. . . . . . .

. . . . .

. . . . .

. . . . . . .

. . . . .

. . . . .

. . . . . . .

. . . . .

. . . . .

. . . . . . .

. . . . .

. . . . .

. . . . . . .

. . . . .

. . . . .

. . . . . . .

. . . . .

. . . . .

37 37 37 38 38 38

. . . . . . .

40 40 41 42 42 44 45 46

. . . . .

47 47 48 48 49 49 51

6

Kapitola 1 ´ Uvod Poˇc´ıtán´ı je uˇziteˇcné v kaˇzdé ˇcinnosti souvisej´ıc´ı se svˇetskými, védskými nebo jim podobnými náboˇzenskými záleˇzitostmi. Znalost poˇcetn´ı je vysoce cenˇena v znalosti lásky, v poznatc´ıch o bohatstv´ı, v hudbˇe i dramatu, v kuchaˇrském umˇen´ı, v medic´ınˇe, v architektuˇre, v prosodii, ve verˇsotepectv´ı i poesii, v logice a gramatice a v jiných vˇecech... Pouˇz´ıvá se j´ı ve spojitosti s pohyby Slunce a jiných nebeských tˇeles, se zatmˇen´ım a konjunkcemi planet a v souvislosti s hledán´ım smˇeru, polohy, ˇcasu a s pohybem Mˇes´ıce. Poˇcet, pr˚ umˇery a obvody ostrov˚ u, oceán˚ u a hor, rozmˇery s´ıdliˇst’ a lidských obydl´ı, prostory mezi svˇety, svˇet svˇetla, svˇet boh˚ u i svˇet pekelných ˇzivl˚ ua mnoˇzstv´ı jiných nejr˚ uznˇejˇs´ıch mˇeˇren´ı - lze uskuteˇcnit jen s pomoc´ı matematiky. Maháv´ıra, indick´ y bard, 9. stolet´ı n.l. ([2], str. 97) Maháv´ıra ve své oslavné básni hovoˇr´ı o poˇc´ıtán´ı a matematice a má na mysli základn´ı aritmetické operace. Jeho o´da z˚ ustává v platnosti i dnes, stále je tˇreba provádˇet aritmetické operace, a to s ˇc´ım dál t´ım vˇetˇs´ı rychlost´ı a pˇresnost´ı. Proto je téma naˇs´ı práce základn´ı aritmetické operace - stále aktuáln´ı. C´ılem práce je zachytit v´ yvoj základn´ıch aritmetick´ ych operac´ı (násoben´ı, sˇc´ıtán´ı, dˇelen´ı a v´ ypoˇcet druhé odmocniny) od starovˇeku aˇz do dneˇsn´ıch dn˚ u. Je zˇrejmé, ˇze jinak vypadaj´ı algoritmy pro poˇc´ıtán´ı zpamˇeti, s tuˇzkou a pap´ırem, pomoc´ı mechanick´ ych pom˚ ucek a tabulek a algoritmy poˇc´ıtaˇcové. Práce je rozdˇelena do kapitol vˇenovan´ ych jednotliv´ ym aritmetick´ ym operac´ım a kaˇzdá z kapitol je pak ˇclenˇena na sekce, podle toho, zda jsou k v´ ypoˇctu uˇzity pouze prsty nebo pap´ır s tuˇzkou, mechanické pom˚ ucky ˇci dokonce poˇc´ıtaˇc. ´ Pˇripojena je také kapitola Uroveˇ n matematiky star´ ych kultur popisuj´ıc´ı u ´roveˇ n matematiky na u ´zem´ıch, kde se jednotlivé algoritmy rodily, a dále kapitola V´ yznamn´ı matematikové s medailonky matematik˚ u, kteˇr´ı aritmetiku podstatnˇe ovlivnili.

7

Kapitola 2 N´ asoben´ı Na prvn´ı pohled by se mohlo zdát, ˇze u ´loha vynásobit dvˇe pˇrirozená ˇc´ısla je nezaj´ımavá. Známe pˇrece uˇz ze základn´ı ˇskoly algoritmus, u kterého staˇc´ı umˇet malou násobilku a sˇc´ıtat, a u ´loha je vyˇreˇsená. Tato kapitola by mˇela b´ yt d˚ ukazem, ˇze u ´loha zaj´ımavá je, protoˇze metod ˇreˇsen´ı existuje celá ˇrada. Egyptské a ruské násoben´ı je zaloˇzeno na binárn´ım rozvoji násobence. Cauchyovo komplementárn´ı násoben´ı vyuˇz´ıvá zápis ˇc´ısel poˇ ınské násoben´ı je grafické, a tedy pro ˇza´ky s vrozen´ moc´ı záporn´ ych cifer. C´ ym odporem k matematice moˇzná nejpˇr´ıvˇetivˇejˇs´ı. Zjednoduˇsen´ı násoben´ı velk´ ych ˇc´ısel pˇrinesly tabulky kvadrát˚ u, japonsk´ y soroban a Napierovy kosti, vynález Johna Napiera, otce logaritmu. Kromˇe algoritm˚ u, které urychluj´ı násoben´ı zpamˇeti a na pap´ıˇre, si také ukáˇzeme efektivn´ı algoritmy pro poˇc´ıtaˇcové násoben´ı. Pˇri násoben´ı velk´ ych ˇc´ısel se vyplat´ı zapsat ˇc´ısla v tzv. redundantn´ı binárn´ı soustavˇe, kde je dovolena kromˇe cifer 0 a 1 i cifra −1. Modern´ı éru násoben´ı velk´ ych ˇc´ısel odstartovaly ale zejména Karacub˚ uv algoritmus a modulárn´ı násoben´ı, které taktéˇz pˇredstav´ıme. Kapitolu zakonˇc´ıme pˇrehledem v souˇcasnosti nejrychlejˇs´ıch znám´ ych poˇc´ıtaˇcov´ ych algoritm˚ u pro násoben´ı.

2.1

N´ asoben´ı zpamˇ eti

Násoben´ı na prstech pan´ı uˇcitelky na základn´ı ˇskole nevid´ı rády. Chtˇej´ı nás totiˇz nauˇcit násobit do 10 krát 10 zpamˇeti jako kdyˇz biˇcem mrská“. Pˇresto je pouˇzit´ı prst˚ u pˇrirozen´ ym ” zjednoduˇsen´ım, kter´ ym si lidé pomáhaj´ı pˇri v´ ypoˇctech odedávna. Stˇredovˇec´ı obchodn´ıci s oblibou vyuˇz´ıvali tzv. cikánskou násobilku, která umoˇzn ˇuje násobit pomoc´ı prst˚ u ˇc´ısla x × y, kde x, y ∈ {6, 7, 8, 9} (se znalost´ı pouhé násobilky do 5 krát 5). Princip cikánské násobilky pochop´ıte z 1. ˇca´sti obrázku 2.1. Pokud chceme násobit 8 krát 7, zeptáme se: Osm a kolik je deset?“ A dva.“ Skrˇc´ıme ” ” dva prsty na prvn´ı ruce (c = 2). To samé udˇeláme s ˇc´ıslem sedm. Schováme tedy tˇri prsty na druhé ruce (d = 3). Na pozici des´ıtek nap´ıˇseme souˇcet vztyˇcen´ ych prst˚ u (a+b = 3+2 = 5) a na pozici jednotek nap´ıˇseme souˇcin skrˇcen´ ych prst˚ u (c · d = 2 · 3 = 6). A obdrˇz´ıme správn´ y v´ ysledek 56. Bystr´ y ˇctenáˇr si snadno rozmysl´ı, ˇze algoritmus je pouˇziteln´ y jen k násoben´ı ˇc´ısel, která jsou obˇe vˇetˇs´ı neˇz 5, a ˇze funguje d´ıky následuj´ıc´ım rovnostem (10 − c)(10 − d) = 100 − (c + d)10 + cd = 10(10 − c − d) + cd = 10(a + b) + cd. Moˇzná uˇz ˇctenáˇr postˇrehl, ˇze pˇri násoben´ı nˇekter´ ych ˇc´ısel naraz´ıme na u ´skal´ı. Napˇr´ıklad pˇri násoben´ı 7 × 6 je c · d = 3 × 4 = 12, coˇz je v´ıce neˇz 10. V takovém pˇr´ıpadˇe na m´ıstˇe 8

Obrázek 2.1: 1. Cikánská násobilka pro v´ ypoˇcet 8 × 7. 2. V´ ypoˇcet 14 × 9 na prstech.

jednotek necháme ˇc´ıslo 2 a 1 pˇreneseme k des´ıtkám. Násoben´ı dev´ıti nedˇelalo stˇredovˇek´ ym trhovc˚ um problémy ani pro ˇc´ısla od 12 do 19. Jejich postup naznaˇcuje 2. ˇca´st obrázku 2.1. Pokud chceme násobit 14 krát 9, skrˇc´ıme na levé ruce ˇctvrt´ y prst – prsten´ıˇcek. Zleva pak palec reprezentuje stovky (a = 1), zbylé prsty pˇred prsten´ıˇckem reprezentuj´ı des´ıtky (b = 2) a prsty, které následuj´ı za prsten´ıˇckem, reprezentuj´ı jednotky (c = 6). V´ ysledek: 126. Snadno si rozmysl´ıme, ˇze algoritmus funguje d´ıky následuj´ıc´ım rovnostem. Násob´ımeli (10 + d) krát 9, kde d = 2, . . . , 9, plat´ı: (10 + d)9 = 90 + 9d = 100 + 10(d − 2) + (10 − d) = 100a + 10b + c.

2.2

N´ asoben´ı s tuˇ zkou a pap´ırem

Máme-li za u ´kol vynásobit dvˇe pˇrirozená ˇc´ısla a k dispozici tuˇzku a pap´ır, vˇetˇsina z nás pouˇzije algoritmus, kter´ y jsme se uˇcili na základn´ı ˇskole. 4 5 4 5 9

× 1 2 3 2 4

7 3 1 1

Existuje ale celá ˇrada alternativ.

2.2.1

Egyptsk´ e n´ asoben´ı

Egypt’ané pˇrevzali pravdˇepodobnˇe násoben´ı od etiopsk´ ych kmen˚ u. Samotné násoben´ı je zaloˇzeno na binárn´ım zápisu násobence. Chtˇeli-li Egypt’ané vynásobit napˇr. 13 krát 15, sestavili si tabulku, jej´ıˇz prvn´ı sloupec tvoˇrily mocniny dvou menˇs´ı nebo rovné 13 a druh´ y sloupec vznikl postupn´ ym zdvojován´ım 9

15. V prvn´ım sloupci si oznaˇcili mocniny dvou, které se vyskytuj´ı v binárn´ım zápisu 13. Pak jiˇz staˇcilo seˇc´ıst ve druhém sloupci ˇra´dky odpov´ıdaj´ıc´ı oznaˇcen´ ym mocninám dvou (viz obrázek 2.2). V´ ysledek: 195. Binárn´ı zápis pˇrirozeného ˇc´ısla n, tedy zápis tvaru 13 × 15 •1 15 2 30 •4 60 •8 120 195 Obrázek 2.2: V´ ypoˇcet 13 × 15 egyptsk´ ym zp˚ usobem. n = a0 20 + a1 21 + a2 22 + · · · + ak 2k , kde koeficienty a0 , a1 , a2 , . . . , ak ∈ {0, 1}, lze z´ıskat hladov´ ym algoritmem. Pod´ıváme se, jakou nejvyˇsˇs´ı mocninu dvojky ˇc´ıslo 13 obsahuje. To je 23 = 8. Poté od 13 odeˇcteme 8 a pro z´ıskan´ y rozd´ıl 5 opˇet najdeme nejvˇetˇs´ı mocninu dvojky, kterou ˇc´ıslo 5 obsahuje. To je 22 = 4. Na závˇer spoˇc´ıtáme rozd´ıl 5 − 4 = 1, a to je nultá mocnina dvojky. Z´ıskáme 13 = 1 + 4 + 8.

2.2.2

Rusk´ e (sedl´ ack´ e) n´ asoben´ı

Ruské násoben´ı se velmi podobá egyptskému. Jeˇstˇe v 19. stolet´ı se pouˇz´ıvalo na ruském venkovˇe a zˇrejmˇe tak násobila vˇetˇsina Evropan˚ u pˇred prosazen´ım indo-arabského zp˚ usobu násoben´ı, kter´ y se dnes uˇc´ıme na základn´ı ˇskole. Chceme-li rusk´ ym zp˚ usobem vynásobit 13 krát 15, sestav´ıme si tabulku, jej´ıˇz prvn´ı sloupec tvoˇr´ı zbytky po opakovaném celoˇc´ıselném dˇelen´ı násobence dvojkou a druh´ y sloupec vznikne postupn´ ym zdvojován´ım 15. Nyn´ı staˇc´ı seˇc´ıst ve druhém sloupci ˇra´dky odpov´ıdaj´ıc´ı jednotkov´ ym zbytk˚ um (viz obrázek 2.3). V´ ysledek: 195. 13 13 : 2 = 6 6:2=3 3:2=1 1:2=0

× zbytek zbytek zbytek zbytek

1 0 1 1

15 15 30 60 120 195

Obrázek 2.3: V´ ypoˇcet 13 × 15 rusk´ ym zp˚ usobem. Uvˇedomte si, ˇze pokud pˇrirozené ˇc´ıslo n nen´ı dˇelitelné dvojkou, znamená to, ˇze na posledn´ım m´ıstˇe v jeho binárn´ım zápisu je jedniˇcka. Pokud je dˇelitelné dvojkou, pak má v binárn´ım zápisu na posledn´ım m´ıstˇe nulu. Snadno si pak rozmysl´ıte, ˇze binárn´ı zápis ˇc´ısla n lze z´ıskat také následuj´ıc´ım algoritmem: 1. Vydˇel ˇc´ıslo dvˇema. 2. Je-li dˇelitelné, zapamatuj si nulu a ˇc´ıslo n/2. Nen´ı-li dˇelitelné, zapamatuj si jedniˇcku a ˇc´ıslo (n − 1)/2. 10

3. Pokud zapamatované ˇc´ıslo nen´ı nula, opakuj algoritmus. Pokud zapamatované ˇc´ıslo je nula, binárn´ı zápis z´ıskáˇs sepsán´ım nul a jedniˇcek zleva doprava v poˇrad´ı od posledn´ı zapamatované cifry k prvn´ı.

2.2.3

Indick´ e n´ asoben´ı

Zde popsané násoben´ı nen´ı jediné, které se ve staré Indii pouˇz´ıvalo. Existovalo v´ıce neˇz osm rozliˇcn´ ych zp˚ usob˚ u násoben´ı, principem se vˇsak velmi podobaly. Chceme-li indick´ ym zp˚ usobem vynásobit 435 krát 12, namalujeme tabulku se tˇremi sloupci a dvˇema ˇrádky, které oznaˇc´ıme ciframi násobence a násobitele, a kaˇzdé okénko tabulky rozdˇel´ıme u ´hlopˇr´ıˇckou na dva troj´ uheln´ıky. Nyn´ı tabulku vypln´ıme tak, ˇze pro kaˇzdou buˇ nku násob´ıme cifry, které znaˇc´ı, v jakém sloupci a ˇra´dku se buˇ nka nacház´ı. Pokud vyjde ˇc´ıslo menˇs´ı neˇz deset, nap´ıˇseme jej do doln´ıho troj´ uheln´ıku. Pokud je v´ ysledek vˇetˇs´ı nebo roven deseti, nap´ıˇseme des´ıtky do horn´ıho troj´ uheln´ıku a jednotky do doln´ıho troj´ uheln´ıku. Na závˇer vysˇc´ıtáme zprava doleva ˇc´ısla podél u ´hlopˇr´ıˇcek. Jednotky sepisujeme a des´ıtky si pamatujeme a pˇrenáˇs´ıme“ je. V´ ysledek je 5220 (viz obrázek 2.4). ”

Obrázek 2.4: V´ ypoˇcet 435 × 12 pomoc´ı indického násoben´ı.

2.2.4

ˇ ınsk´ C´ e grafick´ e n´ asoben´ı

ˇ ınské grafické násoben´ı se nejsp´ıˇse vyvinulo d´ıky lásce C´ ˇ ıˇ C´ nan˚ u ke kaligrafii a malbˇe a jej´ım následn´ ym uplatnˇen´ım v matematice pˇri násoben´ı menˇs´ıch ˇc´ısel. Chceme-li t´ımto zp˚ usobem násobit napˇr´ıklad 123 krát 21, namalujeme za násobence ve smˇeru z JZ na SV postupnˇe jednu rovnobˇeˇzku za stovky, dvˇe rovnobˇeˇzky za des´ıtky a tˇri rovnobˇeˇzky za jednotky. Poté za násobitele namalujeme ze SZ smˇerem na JV dvˇe rovnobˇeˇzky za des´ıtky a jednu za jednotky. Poté do disjunktn´ıch obdéln´ık˚ u uzavˇreme pr˚ useˇc´ıky odpov´ıdaj´ıc´ı tis´ıcovkám, stovkám, des´ıtkám a jednotkám a zjist´ıme jejich poˇcty. V naˇsem pˇr´ıpadˇe máme v prvn´ım obdéln´ıku 2 pr˚ useˇc´ıky, ve druhém 5, ve tˇret´ım 8 a ve ˇctvrtém 3. V´ ysledek 2583 (viz obrázek 2.5 (a)). T´ımto zp˚ usobem bychom postupovali i pˇri násoben´ı vˇetˇs´ıch ˇc´ısel. Pokud nám souˇcet pr˚ useˇc´ık˚ u v nˇekterém obdéln´ıku vyjde vˇetˇs´ı neˇz 9, tak klasicky pˇriˇcteme cifru des´ıtek k pˇredcházej´ıc´ımu obdéln´ıku. Napˇr´ıklad pro 124 krát 21 nám vyjde v prvn´ım odéln´ıku 2, ve

11

Obrázek 2.5: V´ ypoˇcet (a) 123 × 21 (b) 124 × 21 ˇc´ınsk´ ym grafick´ ym zp˚ usobem.

druhém 5, ve tˇret´ım 10 (jedniˇcku pˇriˇcteme k druhému obdéln´ıku) a ve ˇctvrtém 4. V´ ysledek je tedy 2604 (viz obrázek 2.5 (b)).

2.2.5

ˇ ınsk´ C´ e poˇ cetn´ı n´ asoben´ı

Poˇcetn´ı násoben´ı se liˇs´ı od pˇredchoz´ıch algoritm˚ u zejména t´ım, ˇze prob´ıhá zleva doprava, tedy od cifer u nejvyˇsˇs´ıch mocnin deseti k cifrám u jednotek. Detailnˇe je popsáno je v [2], str. 25. Algoritmus pro v´ ypoˇcet 3142 × 14 je srozumiteln´ y z obrázku 2.6. Zaˇc´ıná se s násoben´ım od nejvyˇsˇs´ı cifry vˇetˇs´ıho z ˇc´ısel a jednotlivé kroky se postupnˇe zapisuj´ı zleva doprava. K zápisu násoben´ı se vˇetˇsinou pouˇz´ıvali dˇrevˇené nebo kostˇené tyˇcinky, my jsme pouˇzili pro zjednoduˇsen´ı arabské ˇc´ıslice.

Obrázek 2.6: V´ ypoˇcet 3142 × 14 ˇc´ınsk´ ym poˇcetn´ım násoben´ım.

2.2.6

Al-Chw´ arizm´ıho n´ asoben´ı

Al-Chwárizm´ıho zp˚ usob násoben´ı se v mnoha ohledech inspiruje nˇekter´ ym z indick´ ych násoben´ı (ne ovˇsem t´ım, které jsme zde popsali my, protoˇze stejnˇe jako ˇc´ınské poˇcetn´ı násoben´ı i Al-Chwárizm´ıho násoben´ı funguje zleva doprava) [2], str. 190-191. Násoben´ı si ukáˇzeme na pˇr´ıkladu 23123 krát 2131 (viz obrázek 2.7). Nejdˇr´ıve si nap´ıˇseme násobence a pod nˇej násobitele tak, aby jednotky násobitele byly pod nejvyˇsˇs´ı cifrou násobence. Poté vezmeme nejvyˇsˇs´ı cifru násobence (v naˇsem pˇr´ıpadˇe 2) a vynásob´ıme násobitele. T´ım dostaneme ˇc´ıslo 4262, které nap´ıˇseme pˇred násobence tak, ˇze jednotkovou cifrou nahrad´ıme nejvyˇsˇs´ı cifru násobence. Nakonec násobitele posuneme o jednu cifru doprava. Dalˇs´ı násoben´ı provedeme ˇc´ıslem 3, vyjde nám 6393 a toto ˇc´ıslo pˇriˇcteme k ˇca´steˇcnému v´ ysledku 4262 tak, ˇze posledn´ı cifrou pˇrep´ıˇseme trojku. Násobitele posuneme o jednu cifru doprava. Dále násob´ıme podobnˇe jedniˇckou a znovu v´ ysledek pˇriˇcteme tak, ˇze posledn´ı 12

3

1

2

3

4 2 6 2| 3 2 1 3 1

1

2

3

4 9 0 2

1 3| 1 1 3 1

2

3

4 9 2

2 2

6 1| 2 1 3 1

3

4 9 2

6

8

7 2| 3

2

1

3

5

1

1 3

2 1 3

2 1

4 9 2 7

1

Obrázek 2.7: Al-Chwárizm´ıho v´ ypoˇcet 23123 × 2131. cifra nahrad´ı jedniˇcku. Násobitele zase posuneme o jednu cifru doprava. Nyn´ı provedeme násoben´ı analogicky i se zbyl´ ymi ciframi násobence. Nakonec nám vyjde ˇc´ıslo 49275113, coˇz je správn´ y v´ ysledek.

2.2.7

Cauchyovo komplement´ arn´ı n´ asoben´ı

Toto násoben´ı vyuˇz´ıvá zápis ˇc´ısel pomoc´ı záporn´ ych cifer. Vˇsimnˇeme si, ˇze pˇri pouˇzit´ı Cauchyova komplementárn´ıho násoben´ı si vystaˇc´ıme s násobilkou do 5 krát 5! Chceme-li násobit 57 krát 17 Cauchyov´ ym algoritmem, zap´ıˇseme nejprve násobence i násobitele pomoc´ı cifer od −4 do 5, tj. 57 = 14 3 = 100 − 40 − 3 a 17 = 23 = 20 − 3. Pruhy nad ciframi tedy znamenaj´ı, ˇze cifry maj´ı znaménko m´ınus. Poté jiˇz násob´ıme analogicky jako v klasické des´ıtkové soustavˇe. Pouze u znamének dáváme pozor: pˇri násoben´ı dvou záporn´ ych cifer nebo dvou kladn´ ych cifer má v´ ysledek znaménko plus, pˇri násoben´ı cifer opaˇcného znaménka má v´ ysledek znaménko m´ınus (viz obrázek 2.8).

2 1

4 1 × 2 −2 2 −8 −6 0 −4 9 6

3 3 9 9 9

Obrázek 2.8: V´ ypoˇcet 57 × 17 Cauchyov´ ym algoritmem. Abychom mohli Cauchyovo komplementárn´ı násoben´ı pouˇz´ıvat, mus´ıme umˇet pˇrevádˇet zápisy ˇc´ısel mezi klasickou des´ıtkovou soustavou a des´ıtkovou soustavou s ciframi od −4 do 5. K takové konverzi slouˇz´ı následuj´ıc´ı jednoduch´ y algoritmus: 13

1. Pˇriˇcteme ˇc´ıslo sestavené z tolika ˇctyˇrek kolik cifer má ˇc´ıslo konvertované. Napˇr´ıklad chceme-li zapsat 57 v des´ıtkové soustavˇe s ciframi od −4 do 5, v prvn´ım kroku pˇriˇcteme 44 57 + 44 = 101, poté odeˇcteme od kaˇzdé z posledn´ıch dvou cifer souˇctu ˇc´ıslo 4 0 − 4 = −4 a 1 − 4 = −3. V´ ysledek: 14 3. 2. Chceme-li naopak pˇrevést ˇc´ıslo do klasické des´ıtkové soustavy, spoˇcteme rozd´ıl kladné a záporné ˇcásti. Napˇr´ıklad zápis 14 3 v klasické des´ıtkové soustavˇe z´ıskáme jako: 100 − 43 = 57. V´ ysledek: 57.

2.2.8

Pˇ revod n´ asoben´ı na goniometrick´ e a logaritmick´ e funkce

Ve stˇredovˇeké Evropˇe bylo bˇeˇzné pˇrevádˇen´ı násoben´ı na sˇc´ıtán´ı, nˇekdy velmi zvláˇstn´ım zp˚ usobem [7]. Napˇr´ıklad se vyuˇz´ıvalo funkce cosinus ve vzorci: cos α × cos β =

1 (cos(α 2

+ β) + cos(α − β))

Pokud jsme j´ım chtˇeli vynásobit dvˇe ˇc´ısla, napˇr. 326 a 931, museli jsme zaˇc´ıt upraven´ım obou ˇc´ısel vytknut´ım mocnin 10 a v´ ypoˇctem pˇr´ısluˇsného u ´hlu. 326 × 10−3 = 0, 326 = cos(70, 97382931◦ ) 931 × 10−3 = 0, 931 = cos(21, 40876293◦ ) Poté dosad´ıme do vzorce: cos(70, 97382931◦ ) × cos(21, 40876293◦ ) = = 21 (cos(70, 97382931◦ + 21, 40876293◦ ) + cos(70, 97382931◦ − 21, 40876293◦ )) = 21 (−0.04157209558 + 0.6485840956) = 21 0.607012 = 0.303506 Nakonec v´ ysledek vynásob´ıme 106 a dostaneme 303506. Dokladem, ˇze se t´ımto zp˚ usobem násoben´ı provádˇelo, jsou obsáhlé, patnáctim´ıstné tabulky goniometrick´ ych funkc´ı z roku 1613. Dalˇs´ım pˇrevodem násoben´ı na sˇc´ıtán´ı je pˇrevod pomoc´ı logaritm˚ u. Tento postup se jeˇstˇe pˇred nedávnem uˇcil i na ˇskolách, dnes bohuˇzel upadá v zapomnˇen´ı. Dekadick´ y logaritmus ˇc´ısla x je exponent, na kter´ y mus´ıme pov´ yˇsit ˇc´ıslo 10, abychom dostali x: 10log x = x. Pˇri násoben´ı mocnin se stejn´ ym základem se exponenty sˇc´ıtaj´ı: am × an = am+n

14

a plat´ı: a = 10log a , b = 10log b , ab = 10log a × 10log b = 10log a+log b = 10log ab . Pokud tedy chceme vynásobit 326 × 931, postupujeme následovnˇe: log(326 × 931) = log 326 + log 931 = 2, 5132176 + 2, 968949681 = 5, 482167281 Nyn´ı v´ ysledek odlogaritmujeme pomoc´ı tabulek a dostáváme 303506.

2.3 2.3.1

Mechanick´ e pom˚ ucky a tabulky Soroban

Soroban je japonská varianta kuliˇckového poˇc´ıtadla. Do Japonska se dostal okolo roku ˇ ıny, kde existuje podobné poˇc´ıtadlo zvané suan pan. 1600 z C´

ˇ Obrázek 2.9: Japonské poˇc´ıtadlo soroban - pap´ırov´ y model od autora SOC.

Násoben´ı dvou ˇc´ısel je totoˇzné s ˇc´ınsk´ ym poˇcetn´ım a Al-Chwárizm´ıho násoben´ım, tedy postupuje opˇet zleva doprava, pouze se jednotlivé kroky nep´ıˇs´ı na pap´ır, ale znaˇc´ı se uspoˇra´dán´ım kuliˇcek na poˇc´ıtadle. Násoben´ı si uvedeme na pˇr´ıkladu 46 krát 235. 1. Zaˇcneme znázornˇen´ım ˇc´ısla 46 na poˇc´ıtadle. Pˇri násoben´ı vˇzdy zaˇc´ınáme v levém krajn´ım sloupci. Kaˇzd´ y sloupec je rozdˇelen na dvˇe ˇcásti. V horn´ı ˇca´sti je jedna kuliˇcka, která má hodnotu ˇc´ısla 5, a v doln´ı ˇca´sti jsou ˇctyˇri kuliˇcky, kaˇzdá o hodnotˇe ˇ ıslo 4 tedy znázorn´ıme posunut´ım 4 kuliˇcek nahoru a ˇc´ıslo 6 v dalˇs´ım sloupci 1. C´ vpravo posunut´ım jedné kuliˇcky o hodnotˇe 5 dol˚ u a jedné kuliˇcky o hodnotˇe 1 nahoru (viz obrázek 2.10 a.). 2. Vynecháme jeden sloupec a znázorn´ıme ˇc´ıslo 235 (viz obrázek 2.10 b.). 3. Vynecháme dva sloupce (obecnˇe tolik sloupc˚ u, kolik je cifer násobence) a zaˇcneme násoben´ım 4 krát 235. 4 krát 2 je 8, osm znázorn´ıme na sorobanu, 4 krát 3 je 12, 2 znázorn´ıme na dalˇs´ım sloupci a 1 pˇriˇcteme k 8 v sloupci pˇredeˇslém. Nakonec 4 krát 5 je dvacet, 2 pˇriˇcteme k pˇredeˇslému sloupci. Mus´ıme si pamatovat, ˇze posledn´ı sloupec je prázdn´ y, ale znázorˇ nuje nulu - abychom pˇri pˇrepisu ˇc´ısla nezmˇenily ˇra´d jej´ım vynechán´ım! (viz obrázek 2.10 c.).

15

4. Pokraˇcujeme obdobn´ ym násoben´ım 6 krát 235, pouze zaˇc´ınáme pˇriˇc´ıtat meziv´ ysledky aˇz o jeden sloupec dál, neˇz pˇri násoben´ı pˇredcházej´ıc´ım, protoˇze násob´ıme ˇc´ıslem menˇs´ım o jeden ˇra´d (viz obrázek 2.10 d.). 5. Pˇreˇcteme ˇc´ıslo na sorobanu. V´ ysledek je 10810.

Obrázek 2.10: Násoben´ı 46 × 235 na sorobanu.

2.3.2

N´ asoben´ı na lin´ ach

V 15. stolet´ı jsou jiˇz v Evropˇe rozˇs´ıˇrené p´ısemné v´ ypoˇcty, ty ale stále nevytlaˇcily poˇcty op´ıraj´ıc´ı se o r˚ uznorodé mechanické pom˚ ucky. Ve 12. - 14. stolet´ı bylo velmi hojnˇe vyuˇz´ıváno kuliˇckové poˇc´ıtadlo abakus, které se ale od 15. stolet´ı ztrác´ı a objevuj´ı se speciáln´ı poˇcetn´ı desky. Samotné poˇcetn´ı desky se od sebe velmi liˇsily. Odráˇzela se v nich nároˇcnost v´ ypoˇct˚ u i bohatstv´ı majitele, takˇze se setkáváme nejen s obyˇcejn´ ymi dˇrevˇen´ ymi, ale i kovov´ ymi deskami. Vˇzdy se vˇsak jednalo o desku rozdˇelenou svisl´ ymi a horizontáln´ımi ˇcarami na jednotlivá okna, na které se jednotlivé cifry znaˇcily kladen´ım kamen˚ u (anglicky countres, francouzsky jetons). Jedna ˇca´st linky a okno nad n´ı slouˇz´ı k zaznamenán´ı jedné cifry. Kameny um´ıstˇené na lince maj´ı hodnotu jedné, mohou zde b´ yt maximálnˇe ˇctyˇri a v oknˇe m˚ uˇze b´ yt poloˇzen jeden kámen o hodnotˇe pˇeti. V jednom sloupci pak znaˇc´ıme jedno ˇc´ıslo, kde na doln´ı lince a v prvn´ım oknˇe jsou naznaˇceny jednotky a na kaˇzdé dalˇs´ı lince a v kaˇzdém dalˇs´ım oknˇe nar˚ ustá hodnota cifry vˇzdy o jeden ˇra´d. Násoben´ı si pˇredvedeme na 73 krát 95. Zaˇcneme zaznaˇcen´ım obou ˇc´ısel v prvn´ıch dvou sloupc´ıch.

Obrázek 2.11: Znázornˇen´ı ˇc´ısla 73 v prvn´ım a 95 v druhém sloupci. Nyn´ı zaˇc´ınáme násoben´ım 3 × 5 a meziv´ ysledek naznaˇc´ıme v tˇret´ım sloupci, protoˇze násob´ıme jednotky s jednotkami zaˇc´ınáme v doln´ım oknˇe (viz obrázek 2.12 a.). 16

Obrázek 2.12: Násoben´ı 73 × 95 na linách.

Pokraˇcujeme násoben´ım 3 × 9 a v´ ysledek vyznaˇc´ıme v dalˇs´ım sloupci, protoˇze uˇz ale násob´ıme jednotky des´ıtkami zaˇc´ınáme o jedno okno v´ yˇse (viz obrázek 2.12 b.). Dále násob´ıme 7 × 5 a v´ ysledek opˇet zaznaˇc´ıme v dalˇs´ım sloupci, tentokrát na stejné u ´rovni jako pˇredeˇslé násoben´ı, protoˇze des´ıtky násob´ıme jednotkami (viz obrázek 2.12 c.). Posledn´ı násoben´ı 7 × 9 naznaˇc´ıme o jedno okno v´ yˇse, protoˇze násob´ıme des´ıtky des´ıtkami. Celé násoben´ı ukonˇc´ıme seˇcten´ım jednotliv´ ych meziv´ ysledk˚ u po ˇradách. Sˇc´ıtáme od nejniˇzˇs´ıho okna (viz obrázek 2.12 d.). V´ ysledek: 6935.

2.3.3

Napierovy kosti

Tuto v´ ypoˇcetn´ı pom˚ ucku, jej´ıˇz pomoc´ı m˚ uˇzeme jednoduˇse pˇrevést násoben´ı, a jak uvid´ıme v následuj´ıc´ı kapitole, také dˇelen´ı na sˇc´ıtán´ı, vymyslel skotsk´ y matematik John Napier na sklonku svého ˇzivota. Základn´ı Napierovy kosti se skládaj´ı z dev´ıti samostatn´ ych sloupk˚ u, rozdˇelen´ ych na deset ˇra´dk˚ u. V prvn´ım ˇrádku je uvedeno ˇc´ıslo 1 aˇz 9 a v následuj´ıc´ıch dev´ıti jsou vzestupnˇe uvedeny jeho násobky ˇc´ısly 1 aˇz 9, v kaˇzdém ˇrádku des´ıtky p´ıˇseme nad diagonálu a jednotky pod n´ı. Název Napierovy kosti má p˚ uvod v materiálu sloupk˚ u, j´ımˇz byla nejˇcastˇeji slonovina. Sloupky proto pˇripom´ınaly kosti. Násoben´ı si vysvˇetl´ıme na pˇr´ıkladu 4732 krát 6. Z Napierov´ ych kost´ı si vezmeme sloupky odpov´ıdaj´ıc´ı cifrám násobence a seˇrad´ıme je tak, aby nám vzniklo ˇza´dané ˇc´ıslo (v naˇsem pˇr´ıpadˇe ˇc´ıslo 4732). Poté si najdeme ˇra´dek odpov´ıdaj´ıc´ı násobiteli (v naˇsem pˇr´ıpadˇe ˇrádek 6). Nyn´ı jiˇz pouze seˇcteme ˇc´ısla v horn´ıch a doln´ıch ˇcástech tohoto ˇra´dku, a to tak, ˇze je vˇzdy sˇc´ıtáme po diagonále (viz obrázek 2.13). Chceme-li násobit v´ıcem´ıstn´ ym ˇc´ıslem, vybereme ˇrádky odpov´ıdaj´ıc´ı cifrám násobitele a uspoˇrádáme je nad sebe od jednotek po cifry u nejvyˇsˇs´ı mocniny deseti. Opˇet sˇc´ıtáme po diagonálách.

2.3.4

Tabulky kvadr´ at˚ u

Uˇz staˇr´ı Babyloˇ nané znali vzorce: ab =

1 (a + b)2 − a2 − b2 , 2

ab =

1 (a + b)2 − (a − b)2 . 4 17

Obrázek 2.13: V´ ypoˇcet 4732 × 6 a 4732 × 13 pomoc´ı Napierov´ ych kost´ı.

V roce 1690 uvád´ı Johann Hiob Ludolf ve svém d´ıle Tetragonometrie návod, jak pomoc´ı tabulek kvadrát˚ u násobit pˇrirozená ˇc´ısla. Vˇsimnˇete si, ˇze právˇe z babylonsk´ ych vzorc˚ u je zˇrejmé, ˇze pro v´ ypoˇcet souˇcinu jak´ ychkoliv pˇrirozen´ ych ˇc´ısel staˇc´ı m´ıt k dispozici dost velkou tabulku kvadrát˚ u pˇrirozen´ ych ˇc´ısel. V roce 1817 Antoine Voisin vydává prvn´ı takové multiplikaˇcn´ı tabulky. A poté v roce 1833 vycház´ı Kulikovy tabulky násoben´ı a tabulky kvadrát˚ u, které necituj´ı Ludolfa a Voisina, protoˇze Jakub Filip Kulik o práci sv´ ych pˇredch˚ udc˚ u zˇrejmˇe nevˇedˇel. Kulik vytvoˇril tabulky souˇcin˚ u dvojcifern´ ych pˇrirozen´ ych ˇc´ısel. Násoben´ı pˇrirozen´ ych ˇc´ısel se pak d´ıky nim zjednoduˇsilo na pouhé sˇc´ıtán´ı, viz následuj´ıc´ı ilustrace. Chceme-li násobit 1743 krát 37, staˇc´ı naj´ıt v tabulce souˇcin 43 × 37 a 17 × 37 a v´ ysledky správnˇe seˇc´ıst. 43 × 37 = 1 5 9 1 17 × 37 = 6 2 9 6 4 4 9 1

2.4

Poˇ c´ıtaˇ cov´ e n´ asoben´ı

Násoben´ı v binárn´ı soustavˇe a redundantn´ı binárn´ı soustavˇe nen´ı pro ˇclovˇeka bˇeˇzné. Lidé totiˇz d´ıky deseti prst˚ um provádˇej´ı v´ ypoˇcty v soustavˇe des´ıtkové, tj. ˇc´ısla zapisuj´ı pomoc´ı mocnin des´ıtky a cifer od 0 do 9. Se soustavou binárn´ı ovˇsem pracuje valná vˇetˇsina poˇc´ıtaˇc˚ u.

2.4.1

Bin´ arn´ı soustava

Kaˇzdé pˇrirozené ˇc´ıslo n lze právˇe jedn´ım zp˚ usobem vyjádˇrit ve tvaru: n = 2k + ak−1 2k−1 + ... + a1 21 + a0 20 , 18

kde koeficienty ak−1 , ..., a1 , a0 nab´ yvaj´ı hodnot nula nebo jedna. Tomuto ˇretˇezci koeficient˚ u ˇr´ıkáme binárn´ı zápis ˇc´ısla n. Pˇripomeˇ nme, ˇze binárn´ı zápis se z´ıská hladov´ ym algoritmem: 1. Chceme-li naj´ıt binárn´ı zápis ˇc´ısla 13, pod´ıváme se, jakou nejvyˇsˇs´ı mocninu dvojky ˇc´ıslo 13 obsahuje. To je 23 = 8. 2. Poté od 13 odeˇcteme 8 a pro z´ıskan´ y rozd´ıl 5 opˇet najdeme nejvˇetˇs´ı mocninu dvojky, kterou ˇc´ıslo 5 obsahuje. To je 22 = 4. 3. Na závˇer spoˇcteme rozd´ıl 5 − 4 = 1, a to je nultá mocnina dvojky. 4. Z´ıskáme 13 = 23 + 22 + 20 , a tedy ˇc´ıslo 13 má v binárn´ı soustavˇe zápis 1101. Násoben´ı v binárn´ı soustavˇe je velmi podobné nám známému klasickému násoben´ı v des´ıtkové soustavˇe. Napˇr´ıklad ˇc´ıslo jedenáct s binárn´ım zápisem 1011 a ˇc´ıslo pˇet s binárn´ım zápisem 101 se vynásob´ı následuj´ıc´ım zp˚ usobem: 1 0 1 1 0 0 0 0 1 0 1 1 1 1 0 1

1 1 0 1 1 1 0 1 1

V´ ysledek je 32+16+4+2+1 = 55. Vˇsimnˇeme si, ˇze rychlost násoben´ı odpov´ıdá poˇctu jedniˇcek v binárn´ım zápisu násobitele (v naˇsem pˇr´ıpadˇe jsou dvˇe jedniˇcky v binárn´ım zápisu 5), právˇe tolik sˇc´ıtán´ı totiˇz mus´ıme provést.

2.4.2

Redundantn´ı bin´ arn´ı soustava

Pˇripust’me nyn´ı v binárn´ı soustavˇe cifry −1, 0 a 1. Zápisy ˇc´ısel uˇz nejsou jediné moˇzné, soustava je redundantn´ı. Napˇr´ıklad 15 = 8+4+2+1 a taky 15 = 16−1, tedy jak 1111 tak i 10001 jsou zápisy 15 v redundantn´ı binárn´ı soustavˇe. Vyberme zápis s maximáln´ım poˇctem nul. K tomu staˇc´ı aplikovat následuj´ıc´ı pˇrepisovac´ı pravidla, dokud je co pˇrepisovat: 01111 01111 11 11

→ → → →

10001 10001 01 01

Zat´ımco pr˚ umˇern´ y poˇcet nul ve standardn´ım binárn´ım zápisu je 1/2, v redundantn´ım binárn´ım zápisu s maximáln´ım moˇzn´ ym poˇctem nul jsou to 2/3. Jelikoˇz je rychlost násoben´ı u ´mˇerná poˇctu nul, je jasné, ˇze redundantn´ı binárn´ı soustava je pro násoben´ı velk´ ych ˇc´ısel v´ yhodnˇejˇs´ı. Na závˇer jeˇstˇe poznamenejme, ˇze násob´ıme analogicky jako v klasické binárn´ı soustavˇe. Pouze u znamének dáváme pozor: pˇri násoben´ı cifer stejného znaménka má v´ ysledek znaménko plus, pˇri násoben´ı cifer opaˇcného znaménka má v´ ysledek znaménko m´ınus. Tedy napˇr´ıklad násoben´ı 11 a 5 probˇehne následovnˇe:

19

1 0 1 1 1 0 1 0 0 0 0 1 0 1 0 1 1 0 0 1 0

0 1 0 1 0 1 0 0 1

V´ ysledek je tedy 64 − 8 − 1 = 55.

2.4.3

Klasick´ e n´ asoben´ı

Oznaˇcuje násoben´ı dvou pˇrirozen´ ych ˇc´ısel zadan´ ych pomoc´ı zápis˚ u v bázi b, kde b je pˇrirozené ˇc´ıslo vˇetˇs´ı nebo rovno 2. Binárn´ı zápis (b = 2) a des´ıtkov´ y zápis (b = 10) jsou speciáln´ı pˇr´ıpady zápisu ˇc´ısel v bázi b s ciframi 0, 1, ..., b − 1. Soustava s pˇ rirozen´ ym z´ akladem Kaˇzdé pˇrirozené ˇc´ıslo n lze právˇe jedn´ım zp˚ usobem vyjádˇrit ve tvaru: n = ak bk + ak−1 bk−1 + ... + a1 b1 + a0 b0 , ˇ ezci kde koeficienty ak , ak−1 , ..., a1 , a0 nab´ yvaj´ı hodnot 0, 1, ..., b − 1 a ak 6= 0. Retˇ ak ak−1 ...a1 a0 ˇr´ıkáme zápis ˇc´ısla n v soustavˇe s báz´ı (se základem) b. Podobnˇe jako ve speciáln´ım pˇr´ıpadˇe binárn´ı soustavy lze takov´ y zápis z´ıskat hladov´ ym algoritmem: 1. Chceme-li naj´ıt zápis ˇc´ısla n v bázi b, pod´ıváme se, jakou nejvyˇsˇs´ı mocninu bk ˇc´ıslo n obsahuje a kolikrát ji obsahuje. To bude koeficient ak , kter´ y je jistˇe menˇs´ı neˇz b k+1 (jinak by n obsahovalo b ). 2. Poté od n odeˇcteme ak bk a pro z´ıskan´ y rozd´ıl opˇet najdeme nejvˇetˇs´ı mocninu bj , kterou obsahuje, a jako aj oznaˇc´ıme poˇcet v´ yskyt˚ u bj v rozd´ılu. 3. Vˇsechny koeficienty mezi aj a ak (pokud nˇejaké takové jsou, tj. pokud je j menˇs´ı neˇz k − 1) jsou nulové. Analogicky pokraˇcujeme dále. Popiˇsme nejprve algoritmus klasického násoben´ı tak, jak by jej provedl poˇc´ıtaˇc, a poté jej porovnejme s algoritmem tuˇzky a pap´ıru“ [6]. ” Algoritmus M (multiplication) Násob´ıme pˇrirozená ˇc´ısla U, V , kde un−1 ...u1 u0 je zápis U v bázi b a vm−1 ...v1 v0 je zápis V v bázi b. Oznaˇcme W = U × V . Snadno si rozmysl´ıme, ˇze délka zápisu W v bázi b bude maximálnˇe m + n. Oznaˇcme wm+n−1 ...w1 w0 zápis W . 1. Inicializace W a i, j Poloˇz wn−1 = ... = w1 = w0 = 0 a i = 0 a j = 0. 2. Násoben´ı nulou Pokud vj = 0, pak poloˇz wi+j = 0 a jdi na krok 6. 3. Inicializace i Poloˇz i = 0, k = 0.

20

4. Násob a seˇcti Poloˇz t = ui · vj + wi+j + k. Pak poloˇz wi+j = t mod b a k = [t/b], kde [x] je nejvˇetˇs´ı celé ˇc´ıslo, které je menˇs´ı nebo rovno x a t mod b = t − b[t/b] (zbytek po celoˇc´ıselném dˇelen´ı). 5. Cyklus na i Poloˇz i := i + 1. Pokud i < n, jdi na krok 4. Jinak poloˇz wi+j = k. 6. Cyklus na j

Poloˇz j := j + 1. Pokud j < m, jdi na krok 2. Jinak konec.

Ilustrujme algoritmus M pro b = 10 a W = U × V , kde U = 914 = u2 u1 u0 a V = 84 = v1 v0 : • 1. bod w2 = w1 = w0 := 0 a i := 0 a j := 0. • 3. bod k := 0. • 4.+5. bod t := u0 · v0 + w0 + k = 4 · 4 = 16, w0 := 6, k := 1, i := 1. • 4.+5. bod t := u1 · v0 + w1 + k = 1 · 4 + 0 + 1 = 5, w1 := 5, k := 0, i := 2. • 4.+5. bod t := u2 · v0 + w2 + k = 9 · 4 = 36, w2 := 6, k := 3, i := 3, w3 := 3 (aˇz sem shodn´ y postup s násoben´ım v ruce). • 6.+3. bod j := 1, i := 0, k := 0. • 4.+5. bod t := u0 · v1 + w1 + k = 4 · 8 + 5 = 37, w1 := 7, k := 3, i := 1. • 4.+5. bod t := u1 · v1 + w2 + k = 1 · 8 + 6 + 3 = 17, w2 := 7, k := 1, i := 2. • 4.+5. bod t := u2 · v1 + w3 + k = 9 · 8 + 3 + 1 = 76, w3 := 6, k := 7, i := 3, w4 := 7. • 6.+3. bod j := 2 a konec. V´ ysledek: W = w4 w3 w2 w1 w0 = 76776. Algoritmus M versus n´ asoben´ı s tuˇ zkou a pap´ırem Pˇri násoben´ı na pap´ıˇre tvoˇr´ıme ˇcásteˇcné souˇciny, které pˇr´ısluˇsnˇe posunuté vlevo sepisujeme pod sebe a na závˇer vysˇc´ıtáme. Na poˇc´ıtaˇci je v´ yhodnˇejˇs´ı provádˇet násoben´ı a sˇc´ıtán´ı souˇcasnˇe - tak postupuje algoritmus M. Nen´ı tˇeˇzké si rozmyslet, ˇze t nab´ yvá hodnot 2 0, 1, . . . , b − 1 a pˇrenos (carry) k nab´ yvá hodnot 0, 1, . . . , b − 1, proto v´ıme, jak velké registry potˇrebujeme pro implementaci. Poˇc´ıtaˇce nav´ıc pracuj´ı s báz´ı 2, bod 2. tedy uˇsetˇr´ı práci, nastává pr˚ umˇernˇe v polovinˇe pˇr´ıpad˚ u. (Uˇz z pˇredchoz´ı sekce v´ıme, ˇze v binárn´ı soustavˇe je rychlost násoben´ı u ´mˇerná poˇctu nul v binárn´ım zápisu násobitele.) Nev´ yhodou klasického algoritmu je jeho pomalost. Uˇz pro m = n = 4 je moˇzné násobit U ×V rychleji. Sloˇ zitost algoritmu M Definujme nejprve elementárn´ı operace: 1. souˇcet a rozd´ıl 1-m´ıstn´ ych ˇc´ısel a pˇr´ıpadnˇe pˇrenos, 2. souˇcin dvou 1-m´ıstn´ ych ˇc´ısel s 2-m´ıstn´ ym v´ ysledkem, 3. celoˇc´ıselné dˇelen´ı 2-m´ıstného ˇc´ısla 1-m´ıstn´ ym za pˇredpokladu, ˇze kvocient i zbytek v´ ysledku jsou 1-m´ıstné. 21

Poˇcet takov´ ych operac´ı udává sloˇzitost algoritmu. V pˇr´ıpadˇe algoritmu M lze dokázat, ˇze sloˇzitost násoben´ı ˇc´ısel, jejichˇz rozvoje v bázi b maj´ı délky m a n, je O(m · n), tj. existuje kladná konstanta K taková, ˇze pro libovolná dvˇe pˇrirozená ˇc´ısla je sloˇzitost jejich násoben´ı algoritmem M menˇs´ı neˇz K · m · n.

2.4.4

Rychl´ e n´ asoben´ı

Rychlé násoben´ı je násoben´ı se sloˇzitost´ı menˇs´ı neˇz násoben´ı klasické. Snaha o zrychlen´ı algoritm˚ u se zesiluje ruku v ruce s rozvojem poˇc´ıtaˇc˚ u a speciálnˇe snaha o maximáln´ı zrychlen´ı násoben´ı je dána potˇrebami kryptografie, kde je nutné násobit v pˇrijatelném ˇcase ohromná ˇc´ısla (ˇrádovˇe 10100 ). My pop´ıˇseme dvˇe rychlá násoben´ı - Karacubovo násoben´ı a Schönhageovo násoben´ı v modulárn´ı aritmetice - zaloˇzená na d˚ uvtipn´ ych myˇslenkách a pomˇernˇe jednoduˇse popsatelná. Mezi rychl´ ymi algoritmy patˇr´ı k tˇem nejstarˇs´ım, ovˇsem algoritmy jeˇstˇe rychlejˇs´ı uˇz jsou pˇr´ıliˇs technické. Zmiˇ nme proto jen struˇcnˇe, jaké jsou v dneˇsn´ı dobˇe nejrychlejˇs´ı algoritmy pro násoben´ı pˇrirozen´ ych ˇc´ısel. V praxi se vyuˇz´ıvá Schönhage˚ uv–Strassen˚ uv algoritmus (zaloˇzen´ y na rychlé Fourierovˇe transformaci) z roku 1971. Tento algoritmus je rychlejˇs´ı neˇz Karacub˚ uv 4 pro ˇc´ısla maj´ıc´ı ˇra´d alespoˇ n 10 . V roce 2007 pˇrevzal teoretické prvenstv´ı v rychlosti F¨ urer˚ uv algoritmus. V praxi se ale F¨ urer˚ uv algoritmus nevyuˇz´ıvá, protoˇze zaˇc´ıná b´ yt rychlejˇs´ı neˇz Schönhage˚ uv–Strassen˚ uv algoritmus aˇz pro astronomicky velká ˇc´ısla. Podobnˇe je to s algoritmem autor˚ u De, Saha, Kurur a Saptharishi z roku 2008. Zájemce si dohledá podrobnosti na internetu a v knize Donalda E. Knutha [6]. Poznamenejme, ˇze jde o jednu z nejrespektovanˇejˇs´ıch publikac´ı v oboru programován´ı. Donald E. Knuth je pr˚ ukopn´ıkem oboru matematické algoritmické anal´ yzy a v´ yznamnou osobnost´ı v mnoha dalˇs´ıch oborech teoretické poˇc´ıtaˇcové vˇedy. Karacubovo n´ asoben´ı Karacubovo násoben´ı vyvrátilo domnˇenku, ˇze sloˇzitost násoben´ı dvou pˇrirozen´ ych ˇc´ısel 2 s binárn´ım rozvojem délky n je O(n ). Tento názor razil jeˇstˇe v roce 1960 na semináˇri moskevské univerzity zakladatel teorie sloˇzitosti algoritm˚ u Andrej N. Kolmogorov. Semináˇre se u ´ˇcastnil i jeho student Anatolij A. Karacuba, kter´ y navrhl d˚ uvtipn´ y algoritmus s niˇzˇs´ı sloˇzitost´ı [4, 3]. Pop´ıˇseme algoritmus, kter´ y je zaloˇzen na stejné myˇslence jako p˚ uvodn´ı Karacub˚ uv, ale je jeˇstˇe trochu jednoduˇsˇs´ı. Chceme násobit dvˇe 2n-bitová ˇc´ısla U s binárn´ım zápisem u2n−1 . . . u1 u0 a V s binárn´ım zápisem v2n−1 . . . v1 v0 . Zap´ıˇseme U, V následuj´ıc´ım zp˚ usobem U = 2n U1 + U0 a V = 2n V1 + V0 . Plat´ı tedy, ˇze U1 má binárn´ı zápis u2n−1 . . . un a U0 má zápis un−1 . . . u1 u0 , podobnˇe V1 má binárn´ı zápis v2n−1 . . . vn a V0 má zápis vn−1 . . . v1 v0 . Následuj´ıc´ı formule redukuje problém na 3 násoben´ı n-bitov´ ych ˇc´ısel, nˇekolik sˇc´ıtán´ı, resp. odeˇc´ıtán´ı a posouván´ı binárn´ı ˇcárky: U × V = 2n (2 + 2n )U1 V1 + 2n (U1 − U0 )(V0 − V1 ) + (2n + 1)U0 V0 . Ilustrujme Karacub˚ uv algoritmus pro U × V , kde U = 210 a V = 119. Binárn´ı zápis U je 11010010 a binárn´ı zápis V je 01110111. 210 = U = 24 U1 + U0 = 24 · 13 + 2, 119 = V = 24 V1 + V0 = 24 · 7 + 7, kde U1 = 13 má binárn´ı zápis 1101 a U0 = 2 má binárn´ı zápis 0010, V1 = V0 = 7 maj´ı zápis 0111.

22

Nyn´ı urˇc´ıme 3 souˇciny nejv´ yˇse 4-bitov´ ych ˇc´ısel: U1 V1 , (U1 − U0 )(V0 − V1 ), U0 V0 . V tomto konkrétn´ım pˇr´ıpadˇe je V0 = V1 , a tedy prostˇredn´ı souˇcin je nulov´ y. 1 U1 V1 : 1

1 1 1 1 1 0 0 1 1

1 1 1 0 1 0

0 1 1 1 0 1 1 1

1

1 1 1 0 1 1 0

U0 V0 : 1

1

Na závˇer zb´ yvá provést násoben´ı 28 a 24 , coˇz znamená pˇridán´ı osmi, resp. ˇctyˇr nul na konec zápisu ˇc´ısla, a sˇc´ıtán´ı. U × V = 28 U1 V1 + 24 U1 V1 + 24 U0 V0 + U0 V0 . 1

0

1

1

1

0

U ×V :

1

0 1 1 0 0 0 0 0 1 0 1 1 0 1 1 0 1 1 1 0 0 1 0 0 0 1 1 0 0 1 1

0 0 0 1 1

0 0 0 1 1

0 0 0 0 0

Po konverzi do des´ıtkové soustavy máme správn´ y v´ ysledek 210 × 119 = 214 + 213 + 28 + 27 + 24 + 23 + 22 + 21 = 24990. ˇ ıslo log2 3 je pˇribliˇznˇe Nen´ı tˇeˇzké dokázat, ˇze sloˇzitost Karacubova násoben´ı je O(nlog2 3 ). C´ rovno 1, 585, coˇz je ˇc´ıslo menˇs´ı neˇz 2, a tedy jde skuteˇcnˇe o rychlé násoben´ı podle naˇs´ı definice. Adaptac´ı na des´ıtkovou soustavu lze pˇrevést násoben´ı 8-m´ıstn´ ych ˇc´ısel na násoben´ı ˇc´ısel 4-m´ıstn´ ych, které uˇz dobˇr´ı poˇctáˇri zvládnou zpamˇeti. Nezdá se vˇsak, ˇze by takovou metodu pouˇz´ıvali zázraˇcn´ı poˇctáˇri“, kteˇr´ı v minulosti bavili obecenstvo násoben´ım ” obrovsk´ ych ˇc´ısel zpamˇeti. Sch¨ onhageovo n´ asoben´ı v modul´ arn´ı aritmetice Schönhageovo násoben´ı v modulárn´ı aritmetice sice nen´ı rychlejˇs´ı neˇz Karacub˚ uv algoritmus, ale je zaloˇzeno na odliˇsn´ ych myˇslenkách a na neobvyklé reprezentaci ˇc´ısel, takˇze je rozhodnˇe zaj´ımavé do jeho taj˚ u proniknout. Jeho základn´ım stavebn´ım kamenem je modulárn´ı aritmetika, u jej´ıhoˇz zrodu stáli ˇceˇst´ı vˇedci Anton´ın Svoboda (tv˚ urce prvn´ıho ˇceskoslovenského poˇc´ıtaˇce SAPO a velmi v´ yznamn´ y pr˚ ukopn´ık informatiky nejen u nás) a Miroslav Valach. Nezávisle na nich pˇriˇsel se stejnou myˇslenkou také L. H. Garner. Modul´ arn´ı z´ apis Dosud jsme se seznámili jen se zápisy pˇrirozen´ ych ˇc´ısel v poziˇcn´ıch soustavách s pˇrirozenou báz´ı (pˇr´ıpadnˇe jsme pˇripustili záporné cifry). Nyn´ı pˇrijde naprosto odliˇsn´ y zápis pˇrirozen´ ych ˇc´ısel. Necht’ jsou dána pˇrirozená ˇc´ısla m1 , m2 , . . . , mr . Pak modulárn´ım zápisem nezáporného celého ˇc´ısla U nazveme (u1 , u2 , . . . , ur ), kde ui je rovno U mod mi pro kaˇzdé i od 1 do r. Pˇripomeˇ nme, ˇze mod k znamená zbytek po celoˇc´ıselném dˇelen´ı ˇc´ıslem k a nab´ yvá hodnot od 0 do k − 1. Napˇr´ıklad 13 = 3 · 4 + 1, a tedy 13 mod 4 = 1. Ukaˇzme si na pˇr´ıkladu takovou modulárn´ı reprezentaci. 23

Necht’ U = 26, r = 3 a m1 = 2, m2 = 3, m3 = 5. Pak u1 = 26

mod 2 = 0,

u2 = 26

mod 3 = 2,

u3 = 26

mod 5 = 1.

Proto (0, 2, 1) je modulárn´ım zápisem ˇc´ısla 26. Aby takov´ y zápis mˇel smysl, mˇelo by b´ yt moˇzné p˚ uvodn´ı ˇc´ıslo ze znalosti modulárn´ı reprezentace zrekonstruovat. To bez dodateˇcn´ ych podm´ınek moˇzné nen´ı. Vˇsimnˇeme si, ˇze ˇ ınská ˇc´ısla 56 a 26 maj´ı stejn´ y modulárn´ı zápis (0, 2, 1). Naˇstˇest´ı plat´ı následuj´ıc´ı známá C´ zbytková vˇeta: Necht’ a, u1 , u2 , . . . , ur jsou nezáporná celá ˇc´ısla a necht’ m1 , m2 , . . . , mr jsou pˇrirozená po dvou nesoudˇelná ˇc´ısla. Pak existuje právˇe jedno U , které splˇ nuje: 1. a ≤ U < a + m = a + m1 · m2 · · · · · mr , 2. (u1 , u2 , . . . , ur ) je modulárn´ı reprezentace U . Z této vˇety plyne, ˇze kdyˇz se omez´ıme na ˇc´ısla od 0 do 2 · 3 · 5 = 30, pak mezi nimi právˇe jen ˇc´ıslo 26 má modulárn´ı reprezentaci (0, 2, 1). Modul´ arn´ı aritmetika V modulárn´ı aritmetice je moˇzné paralelizovat sˇc´ıtán´ı a násoben´ı. 1 Plat´ı totiˇz, ˇze pokud U a V jsou pˇrirozená ˇc´ısla s modulárn´ımi reprezentacemi (u1 , u2 , . . . , ur ) a (v1 , v2 , . . . , vr ) a obˇe leˇz´ı mezi 0 a m = m1 · m2 · · · · · mr , pak U + V má modulárn´ı reprezentaci ((u1 + v1 ) mod m1 , (u2 + v2 ) mod m2 , . . . , (ur + vr ) mod mr ), U × V má modulárn´ı reprezentaci ((u1 ·v1 ) mod m1 , (u2 ·v2 ) mod m2 , . . . , (ur ·vr ) mod mr ). Nev´ yhodou je, ˇze nepoznáme, zda v´ ysledek operace nevypadl z intervalu 0 aˇz m. Nav´ıc pˇri pohledu na modulárn´ı reprezentace nepoznáme, které z ˇc´ısel je vˇetˇs´ı. Proto potˇrebujeme rychlou konverzi, která ˇc´ısl˚ um pˇriˇrazuje modulárn´ı zápis a zejména z modulárn´ıho zápisu rychle vyráb´ı zpˇet reprezentovaná ˇc´ısla. Bin´ arn´ı modul´ arn´ı aritmetika Jak uvid´ıme, takovou rychlou konverzi poskytuje vhodná volba modul m1 , m2 , . . . , mr . Následuj´ıc´ı nápad se zrodil v hlavˇe A. S. Fraenkela. Volme modula mi = 2ei − 1, kde e1 < e2 < · · · < er jsou po dvou nesoudˇelná. Nesoudˇelnost takov´ ych modul´ı je zaruˇcena e ’ následuj´ıc´ı vˇetou: Necht e, f jsou pˇrirozená ˇc´ısla. Pak 2 − 1 a 2f − 1 jsou nesoudˇelná, právˇe kdyˇz e a f jsou nesoudˇelná. Konverze U na (u1 , u2 , . . . , ur ) Zapiˇsme U ve tvaru U = at At + at−1 At−1 + · · · + a1 A + a0 , kde A = 2ei . Uvˇedomme si, ˇze binárn´ı zápis a0 z´ıskáme tak, ˇze vezmeme posledn´ıch ei bit˚ u v binárn´ım zápisu U , pro z´ıskán´ı a1 vezmeme pˇredposledn´ıch ei bit˚ u atd. Vlastnˇe jen nasekáme binárn´ı zápis U od konce po ei bitech. Protoˇze A = 1 mod (2ei − 1), dostaneme ui = (at + at−1 + · · · + a0 ) 1

To znamen´ a, ˇze m´ ame-li k dispozici dostatek poˇc´ıtaˇcov´ ych jednotek, m˚ uˇzeme v´ ypoˇcty provádˇet pro kaˇzdou pozici modul´ arn´ı reprezentace na jedné z tˇechto jednotek, aniˇz bychom potˇrebovali informaci od ostatn´ıch jednotek. Uvˇedomte si, ˇze toto u klasického sˇc´ıtán´ı a násoben´ı nejde, docház´ı totiˇz k pˇrenosu.

24

mod (2ei − 1). V des´ıtkové soustavˇe máme analogii - tzv. casting out nines - vylouˇcen´ı dev´ıtek. Napˇr´ıklad 789 mod 9 = 7 + 8 + 9 mod 9 = 6, coˇz skuteˇcnˇe plat´ı, protoˇze 789 = 87 · 9 + 6. Ilustrujme tento algoritmus opˇet na pˇr´ıkladu. Necht’ U = 437, r = 3 a m1 = 22 − 1 = 3, m2 = 23 − 1 = 7, m3 = 25 − 1 = 31. Zˇrejmˇe tedy e1 = 2, e2 = 3, e3 = 5. Snadno ovˇeˇr´ıte, ˇze binárn´ı zápis U je 110110101. 1. Pro z´ıskán´ı u1 rozsekáme binárn´ı zápis U po bloc´ıch délky 2 (mus´ıme jej vpˇredu doplnit nulou, aby mˇel sudou délku), tj. 01, 10, 11, 01, 01. To znamená, ˇze a4 = 1, a3 = 2, a2 = 3, a1 = 1, a0 = 1. Dostáváme, ˇze u1 = 1 + 2 + 3 + 1 + 1 mod 3 = 2. 2. Pro z´ıskán´ı u2 rozsekáme binárn´ı zápis U po bloc´ıch délky 3, tj. 110, 110, 101. To znamená, ˇze a2 = 6, a1 = 6, a0 = 5. Dostáváme, ˇze u2 = 6 + 6 + 5 mod 7 = 3. 3. Pro z´ıskán´ı u3 rozsekáme binárn´ı zápis U po bloc´ıch délky 5 (mus´ıme jej vpˇredu doplnit nulou, aby mˇel délku 10), tj. 01101, 10101. To znamená, ˇze a1 = 13, a0 = 21. Dostáváme, ˇze u3 = 13 + 21 mod 31 = 3. Modulárn´ı reprezentace 437 je tedy (2, 3, 3). (Samozˇrejmˇe, ˇze poˇc´ıtaˇc sˇc´ıtá binárn´ı, nikoliv des´ıtkové, zápisy ˇc´ısel at , at−1 , . . . , a0 .) Konverze (u1 , u2 , . . . , ur ) na U Je o nˇeco sloˇzitˇejˇs´ı. Prob´ıhá ve dvou kroc´ıch: Nejprve je tˇreba naj´ıt r(r − 1)/2 konstant cij , kde indexy i, j nab´ yvaj´ı hodnot od 1 do r, i < j a plat´ı cij mi = 1 mod mj . K tomu vyuˇzijeme následuj´ıc´ı algoritmus. Pokud b · ei mod ej = 1, pak (1 + 2ei + 22ei + · · · + 2(b−1)ei ) (2ei − 1) = 1 {z } | {z } | cij

mi

mod (2ej − 1) . | {z } mj

Poté poloˇz´ıme U = vr mr−1 . . . m2 m1 + · · · + v3 m2 m1 + v2 m1 + v1 , kde v1 = u1 mod m1 v2 = (u2 − v1 )c12 mod m2 v3 = ((u3 − v1 )c13 − v2 )c23 mod m3 .. .. .. . . . vr = (((ur − v1 )c1r − v2 )c2r − . . . )c(r−1)r

mod mr

Snadno se pˇresvˇedˇc´ıme, ˇze takto spoˇctené U splˇ nuje: 1. U je nezáporné ˇc´ıslo menˇs´ı neˇz m, 2. U mod mi = ui pro kaˇzdé i od 1 do r. Ilustrujme i tento algoritmus na pˇr´ıkladu. Necht’ jsou dána modula m1 = 22 − 1 = 3, m2 = 23 − 1 = 7, m3 = 25 − 1 = 31. Hledáme U s modulárn´ı reprezentac´ı (2, 3, 3) takové, ˇze 0 ≤ U < 3 · 7 · 31 = 651. 1. Nejprve najdeme konstanty c12 , c13 , c23 takové, ˇze (a) c12 · 3 = 1 mod 7, (b) c13 · 3 = 1 mod 31, 25

(c) c23 · 7 = 1 mod 31. K tomu potˇrebujeme urˇcit b ∈ N splˇ nuj´ıc´ı: (a) b · 2 mod 3 = 1 ⇒ b = 2, (b) b · 2 mod 5 = 1 ⇒ b = 3, (c) b · 3 mod 5 = 1 ⇒ b = 2. Z algoritmu pro v´ ypoˇcet cij pak v´ıme, ˇze c12 = 1 + 22 = 5, c13 = 1 + 22 + 24 = 21, c23 = 1 + 23 = 9. 2. Odtud jiˇz snadno spoˇcteme v1 = 2

mod 3 = 2, v2 = (3−2)5

mod 7 = 5, v3 = ((3−2)21−5)9

mod 31 = 20.

A na závˇer U = 20 · 7 · 3 + 5 · 3 + 2 = 437. Sch¨ onhageovo n´ asoben´ı Nyn´ı máme vˇse pˇripraveno k tomu, abychom pochopili fungován´ı algoritmu, kter´ y Arnold Schönhage v roce 1966 navrhl. Nejprve si vˇsimnˇeme, jak ˇsikovnˇe vol´ı 6 modul´ı, která budou v jeho algoritmu vystupovat. m1 m2 m3 m4 m5 m6

= = = = = =

26qk −1 − 1 26qk +1 − 1 26qk +2 − 1 26qk +3 − 1 26qk +5 − 1 26qk +7 − 1.

Pro posloupnost q0 = 1 a qk = 3qk−1 − 1, tj. qk = (3k + 1)/2 pro kaˇzdé k pˇrirozené, jsou modula po dvou nesoudˇelná. Nav´ıc plat´ı, ˇze pˇri násoben´ı pk = (18qk + 8)-bitov´ ych ˇc´ısel nedojde k pˇreteˇcen´ı, tj. z˚ ustaneme mezi 0 a m = m1 · m2 · · · · · m6 , protoˇze m je vˇetˇs´ı neˇz 22pk . Ted’ jiˇz samotn´ y Schönhage˚ uv algoritmus. Chceme násobit pˇrirozená ˇc´ısla U a V , oznaˇcme W = U × V . Najdeme nejmenˇs´ı pk tak, ˇze násobená ˇc´ısla jsou nejv´ yˇse pk -bitová. K pk najdeme pˇr´ısluˇsná modula. 1. Spoˇcti u1 = U mod m1 , . . . , u6 = U mod m6 , v1 = V mod m1 , . . . , v6 = V mod m6 . 2. Vynásob u1 v1 , . . . , u6 v6 . 3. Spoˇcti w1 = u1 v1 mod m1 , . . . , w6 = u6 v6 mod m6 . 4. Najdi 0 ≤ W < m takové, ˇze W = w1 mod m1 , . . . , W = w6 mod m6 . Vˇsimnˇeme si, ˇze kaˇzdé z ˇc´ısel ui , vi má maximálnˇe 6qk + 7 = 18qk−1 + 1 < pk−1 bit˚ u, a tedy ˇze algoritmus pˇrevád´ı u ´lohu násobit pk -bitová ˇc´ısla na násoben´ı pk−1 -bitov´ ych ˇc´ısel. To je podobná myˇslenka jako v Karacubovˇe násoben´ı vedouc´ı ke sn´ıˇzen´ı sloˇzitosti. Tentokrát je moˇzné - i kdyˇz pracné - dokázat, ˇze sloˇzitost Schönhageova násoben´ı je O(nlog3 6 ). Jelikoˇz log3 6 je pˇribliˇznˇe 1, 63 < 2, jde opˇet o rychlé násoben´ı, tj. se sloˇzitost´ı menˇs´ı neˇz O(n2 ). 26

Kapitola 3 Dˇ elen´ı 3.1 3.1.1

Dˇ elen´ı s tuˇ zkou a pap´ırem Egyptsk´ e dˇ elen´ı

Je stejnˇe jako egyptské násoben´ı zaloˇzené na binárn´ım zápisu, tentokrát ale pod´ılu. Dˇel´ıme-li napˇr. ˇc´ıslo 187 ˇc´ıslem 24, zaˇcneme vytvoˇren´ım tabulky. V levém sloupci vypisujeme mocniny dvojky a v pravém jim náleˇzej´ıc´ı hodnoty vzniklé zdvojován´ım dˇelitele, neˇz najdeme ˇc´ıslo nejbliˇzˇs´ı k dˇelenci, které je zároveˇ n menˇs´ı neˇz dˇelenec. V naˇsem pˇr´ıpadˇe je to ˇc´ıslo 96. Dál nav´ıc v tabulce vypisujeme pˇrevrácené hodnoty mocnin dvojky a jim náleˇzej´ıc´ı hodnoty dˇelitele. Nyn´ı se d´ıváme na nejbliˇzˇs´ı násobek dˇelitele k ˇc´ıslu 187 a odeˇcteme ho od nˇej. Zároveˇ n mocninu dvojky jemu náleˇzej´ıc´ı vyznaˇc´ıme. S ˇc´ıslem vznikl´ ym odeˇcten´ım postupujeme stejnˇe. Na závˇer seˇcteme vˇsechny zakrouˇzkované násobky dvojky a seˇcteme je. 187 : 24 1 24 2 48 4 96 1/2 12 1/4 6 1/8 3 1/16 1, 5 1/32 0, 75

187-96=91 + zakrouˇzkujeme 4 91-48=43 + zakrouˇzkujeme 2 43-24=19 + zakrouˇzkujeme 1 19-12=7 + zakrouˇzkujeme 1/2 7-6=1 + zakrouˇzkujeme 1/4 1-0,75=0,25 + zakrouˇzkujeme 1/32

Nyn´ı zakrouˇzkované mocniny dvojky seˇcteme a t´ım z´ıskáme pˇribliˇzn´ y pod´ıl: 4 + 2 + 1 + 1/2 + 1/4 + 1/32 = 7 + 25/32. U ˇc´ısel s omezen´ ym rozvojem nakonec ˇc´ıslo zjist´ıme pˇresnˇe. U ˇc´ısel s neomezen´ ym rozvojem ho m˚ uˇzeme jen upˇresˇ novat t´ım, ˇze budeme pokraˇcovat v algoritmu. Pro poˇc´ıtán´ı v bˇeˇzném ˇzivotˇe vˇsak zaokrouhlujeme a nepotˇrebujeme stoprocentnˇe pˇresné ˇc´ıslo. Egypt’ané si obl´ıbili poˇc´ıtán´ı s tzv. kmenov´ ymi zlomky, coˇz jsou zlomky s jedniˇckou v ˇcitateli. Z v´ yˇse popsaného zp˚ usobu dˇelen´ı je jasné, ˇze pod´ıl z´ıskávali ve tvaru celého ˇc´ısla a souˇctu kmenov´ ych zlomk˚ u.

27

3.1.2

ˇ ınsk´ C´ e poˇ cetn´ı dˇ elen´ı podle Sun Ziho

Tento zp˚ usob dˇelen´ı popisuje ve své tvorbˇe ˇc´ınk´ y matematik Sun Zi, ˇzij´ıc´ı okolo 400 n. l. Velmi se podobá zp˚ usobu dˇelen´ı, které se dnes uˇc´ıme ve ˇskolách. Dˇelen´ı, stejnˇe jako ˇc´ınské poˇcetn´ı násoben´ı, je zaloˇzeno na postupném dˇelen´ı a stálém pˇrepisován´ı jednotliv´ ych krok˚ u. Na ukázku budeme dˇelit ˇc´ıslo 47978 sedmi (uvád´ıme v ˇc´ınsk´ ych a arabsk´ ych ˇc´ıslic´ıch). 1. Zaˇcneme zapsán´ım dˇelence v jednom ˇrádku a dˇelitele o ˇrádek n´ıˇze pod nejvyˇsˇs´ı cifru dˇelence. Pokud nem˚ uˇzeme cifru, pod kterou máme napsaného dˇelitelej´ım dˇelit, posuneme ho o jednu cifru vpravo. To dˇeláme, dokud nem˚ uˇzeme danou skupinu cifer dˇelit. V naˇsem pˇr´ıpadˇe posuneme 7 o jedno m´ısto a naznaˇc´ıme t´ım dˇelen´ı 47/7 (viz obrázek 3.1 a.). 2. Celoˇc´ıselnˇe vydˇel´ıme 47/7 a v´ ysledek nap´ıˇseme o ˇrádek nad dˇelence v u ´rovni dˇelitele (viz obrázek 3.1 b.). 3. Od 47 odeteˇcme 6 × 7 a dˇelitele posuneme o dalˇs´ı cifru vpravo (viz obrázek 3.1 c.). 4. Pokraˇcujeme dˇelen´ım 59/7 a v´ ysledek nap´ıˇseme do horn´ıho ˇra´dku za 6, poté opˇet zjist´ıme zbytek po dˇelen´ı a dˇelitele posuneme o dalˇs´ı cifru vpravo (viz obrázek 3.1 d.). 5. Takto pokraˇcujeme aˇz do ukonˇcen´ı dˇelen´ı (viz obrázek 3.1 e., f.). V naˇsem pˇr´ıpadˇe bylo dˇelen´ı celoˇc´ıselné, pokud by nebylo, zapsal by se zbytek a dˇelen´ı se ukonˇcilo.

ˇ ınské poˇcetn´ı dˇelen´ı 47978 : 7. Obrázek 3.1: C´

28

3.2 3.2.1

Mechanick´ e pom˚ ucky Soroban

Pˇri dˇelen´ı na sorobanu mus´ıme zaˇc´ıt znázornˇen´ım dˇelence a dˇelitele. Z levé strany nejdˇr´ıve znázorn´ıme dˇelitele, necháme alespoˇ n 2 sloupce volné a poté znázorn´ıme dˇelence (viz sekce 2.3.1). Pokud tedy chceme dˇelit napˇr´ıklad 68947 ˇc´ıslem 73, mˇel by soroban vypadat, jak je znázornˇeno na obrázku 3.2.

Obrázek 3.2: Znázornˇen´ı ˇc´ısel 73 a 68947 pˇred dˇelen´ım.

Nyn´ı jiˇz pˇrejdeme k samotnému dˇelen´ı. 1. Zaˇcneme celoˇc´ıseln´ ym dˇelen´ım 68 dˇeleno 7, coˇz je 9. Dev´ıtku znázorn´ıme na sloupci pˇred dˇelencem (viz obrázek 3.3 a.). 2. Nyn´ı vynásob´ıme 7 krát 9 a v´ ysledek odeˇcteme od 68 (viz obrázek 3.3 b.). 3. Nakonec vynásob´ıme 3 krát 9, tj. 27, a odeˇcteme od 59. Odeˇc´ıtáme o jednu cifru n´ıˇze, neˇz u pˇredeˇslého, protoˇze nyn´ı odeˇc´ıtáme násobek jednotek (viz obrázek 3.3 c.). 4. Pokraˇcujeme stejn´ ym zp˚ usobem dál, takˇze za 9 nap´ıˇseme 4 a poté odeˇcteme 7 krát 4, tj. 28, od dˇelence (viz obrázek 3.3 d.). 5. Vynásob´ıme 3 krát 4 a odeˇcteme od 44 (viz obrázek 3.3 e.). 6. Nyn´ı opakujeme tento postup, dokud se nedostaneme na ˇc´ıslo, které uˇz dále nem˚ uˇzeme dˇelit, tj. na zbytek, kter´ y je menˇs´ı neˇz dˇelitel. V naˇsem pˇr´ıpadˇe je v´ ysledek 944 a zbytek 35, neboli 944 a 35/73 (viz obrázek 3.3 f.). Existuje jisté u ´skal´ı. Napˇr´ıklad pˇri dˇelen´ı 64947 ˇc´ıslem 73 bychom v 1. kroku dostali, ˇze 1. cifra pod´ılu je 9, po odeˇcten´ı 7×9 od 64 by zbyla jedniˇcka, tj. v dalˇs´ım kroku bychom ˇ sen´ı problému ale nen´ı sloˇzité. Ve 3 × 9 odeˇc´ıtali od 19 a dostali bychom záporné ˇc´ıslo! Reˇ chv´ıli, kdy by vyˇsla záporná cifra, bychom se vrátili o krok zpˇet a m´ısto 9 zvolili ˇc´ıslo o jedniˇcku menˇs´ı, tj. 8.

3.2.2

Napierovy kosti

Dˇelen´ı pomoc´ı Napierov´ ych kost´ı (popsány v sekci 2.3.3) je v mnoha ohledech velmi podobné naˇsemu dˇelen´ı. Pokud napˇr´ıklad chceme vydˇelit ˇc´ıslo 256436 ˇc´ıslem 47, vybereme si z Napierov´ ych kost´ı kosti násobk˚ u ˇctyˇr a sedmi.

29

Obrázek 3.3: Dˇelen´ı 68947 : 73 na sorobanu.

Obrázek 3.4: Dˇelen´ı 256436 : 47 pomoc´ı Napierov´ ych kost´ı.

30

2 5 6 2 3 5 2 1 1 8 2 2

4 3 6 4 8 6 3 2 2

: 47 = 5456 + 4/47

3 6 3 6 5 8 6 8 2 4

1. Vedle tabulky si vyp´ıˇseme násobky 47. 2. Od nejvyˇsˇs´ıch cifer vˇzdy odeˇc´ıtáme co nejvˇetˇs´ı násobek 47, koeficient násobku zap´ıˇseme do v´ ysledku. 3. Opakujeme tento postup, dokud se nedostaneme na ˇc´ıslo menˇs´ı neˇz dˇelitel. Zbytek zap´ıˇseme jako zlomek.

31

Kapitola 4 V´ ypoˇ cet druh´ e odmocniny 4.1

V´ ypoˇ cet druh´ e odmocniny s tuˇ zkou a pap´ırem

4.1.1

Numerick´ y v´ ypoˇ cet druh´ e odmocniny

V´ ypoˇcet druhé odmocniny byl pˇred nˇekolika lety souˇcást´ı základn´ıho vzdˇelán´ı na ˇskolách. Nyn´ı se vˇsak v´ıce neˇz na svou hlavu spoléháme na kalkulaˇcku a tento jednoduch´ y numerick´ y v´ ypoˇcet zaloˇzen´ y na násoben´ı a odeˇc´ıtán´ı upadá v zapomnˇen´ı. V´ ypoˇcet si ukáˇzeme na odmocnˇen´ı ˇc´ısla 35217261. 1. Zaˇcneme rozdˇelen´ım ˇc´ısla na dvojice cifer. 2. Pod´ıváme se na prvn´ı dvojici a pˇrem´ yˇsl´ıme, jaká nejvˇetˇs´ı druhá mocnina nˇejakého ˇc´ısla se do n´ı vejde. V naˇsem pˇr´ıpadˇe je to 52 . 3. 25 odeˇcteme od 35 a ˇc´ıslo 5 nap´ıˇseme do meziv´ ysledku. 4. Pokraˇcujeme opsán´ım dalˇs´ı dvojice. Za toto ˇc´ıslo nap´ıˇseme oddˇeluj´ıc´ı znaˇcku : a dvojnásobek naˇseho meziv´ ysledku. 5. Druhou cifru odmocniny hledáme jako maximáln´ı z splˇ nuj´ıc´ı (5z)2 = (50 + z)2 ≤ 3521, coˇz zjednoduˇs´ıme na tvar 100 × z + z 2 = 10z × z ≤ 1021. ˇ ıslo 9 tedy nap´ıˇseme za 5 do me6. V naˇsem pˇr´ıpadˇe je maximáln´ı takové z = 9. C´ ziv´ ysledku a za naˇse ˇc´ıslo po znaménku dˇelen´ı. 7. Dále vynásob´ıme 109 × 9 a odeˇcteme od 1021. 8. Pokraˇcujeme opˇet opsán´ım dalˇs´ı dvojice, tedy za 40 p´ıˇseme 72. Za toto ˇc´ıslo nap´ıˇseme oddˇeluj´ıc´ı znaˇcku a dvojnásobek naˇseho meziv´ ysledku, tedy 118. 9. Tˇret´ı cifru odmocninu dostaneme jako maximáln´ı z splˇ nuj´ıc´ı (59z)2 = (590 + z)2 ≤ 352172, coˇz zjednoduˇs´ıme na tvar 1180 × z + z 2 = 118z × z ≤ 4072. 32

ˇ ıslo 3 tedy nap´ıˇseme za 59 do meziv´ 10. V tomto pˇr´ıpadˇe je maximáln´ı z = 3. C´ ysledku a za ˇc´ıslo za oddˇelovac´ım znaménkem. 11. Pokraˇcujeme stejnˇe jako v minul´ ych kroc´ıch. 12. Pokud bychom chtˇeli dostat jeˇstˇe pˇresnˇejˇs´ı hodnotu odmocniny, nic nám nebrán´ı pokraˇcovat dál. Za meziv´ ysledek by se napsala desetinná ˇca´rka a za zbytek dvˇe nuly, tj. 490500, a pokraˇcovali bychom analogicky dále. 3 −2 1 −

5 2 1 5 0 2 1 9 8 1 4 0 − 3 5 5 − 4

7 2 6 1

7 4 2 7 4

2 9 3 6 1 4 5 6 9 0 5

√

=

5

9 3 4

:

109 × 9

:

1183 × 3

: 11864 × 4

Tento algoritmus si jeˇstˇe pˇredvedeme na v´ ypoˇctu druhé odmocniny ze 3. √ 0 3 = 1 , 7 3 2 − 1 2 0 0 : 27 × 7 − 1 8 9 1 1 0 0 : 343 × 3 − 1 0 2 9 7 1 0 0 : 3462 × 2 − 6 9 2 4 1 7 6 T´ımto algoritmem m˚ uˇzeme teoreticky pokraˇcovat aˇz do nekoneˇcna, pokud se jedná o odmocniny s neomezen´ ym desetinn´ ym rozvojem.

4.1.2

Indick´ y v´ ypoˇ cet druh´ e odmocniny

Vˇetˇsina indick´ ych matematick´ ych pravidel a návod˚ u je velmi struˇcná, u v´ ypoˇctu odmocˇ niny je vˇsak návod velmi krátk´ y i na indickou u ´roveˇ n. Pouˇcka podle Sr´ıdhary zn´ı (originál je bez doplˇ nuj´ıc´ıho textu v závorkách): Odeˇcti (nejvˇetˇs´ı moˇzn´ y) ˇctverec od (posledn´ıho) lichého m´ısta, vydˇel zbytek zdvojnásobenou (pod nejbliˇzˇs´ı m´ısto) posunutou odmocninou; pod´ıl um´ısti na ˇrádce (zdvojnásobené odmocniny) a po odeˇcten´ı jeho ˇctverce zdvojnásob (pod´ıl). Potom posuˇ n obdrˇzené (v ˇra´dku zdvojnásobené odmocniny) ˇc´ıslo o jedno m´ısto kupˇredu a dˇel j´ım jako dˇr´ıve. (Po opakován´ı operace do konce) vezmi polovinu zdvojnásobeného ˇc´ısla. ([2], str. 119). √ My si v´ ypoˇcet odmocniny pˇredvedeme na v´ ypoˇctu 325142.

33

1. − | − | − | 3 2 5 1 4 2 2.

− | − | 7 5 1 4 2 1 0

3.

− | − | 5 1 4 2 1 0 7

4.

| − | 2 4 2 1 4

1 5.

| − | 2 4 2 1 1 4

6.

| − | 2 4 2 1 1 4 0

1. Zaˇcneme znázornˇen´ım lich´ ych a sud´ ych ˇc´ısel pomoc´ı ”−”a ”|”. 2. Hledáme nejvˇetˇs´ı druhou mocninu menˇs´ı neˇz 32, v naˇsem pˇr´ıpadˇe to je 25. 25 odeˇcteme od 32 a zdvojnásobenou odmocninu (tedy 10) zap´ıˇseme pod zbytek hned zkraje, v naˇsem pˇr´ıpadˇe pod 75. 3. Nyn´ı 75 vydˇel´ıme 10, v´ ysledek zap´ıˇseme za 10 a 75 nahrad´ıme 5, tj. zbytkem po dˇelen´ı. 4. Od 51 odeˇcteme mocninu pod´ılu, tj. 49, a samotn´ y pod´ıl zdvojnásob´ıme na 14. 5. Meziv´ ysledek posuneme o jedno m´ısto doprava. 6. Dˇel´ıme 24 ˇc´ıslem 114, coˇz je 0. Nulu nap´ıˇseme za 114. Nyn´ı bychom mˇeli opakovat body 4. a 5., vyˇsla nám ale nula, a tak bychom posunuli meziv´ ysledek o dalˇs´ı m´ısto doprava. T´ım bychom se ale dostali za desetinnou ˇcárku, coˇz Indové nedˇelali, n´ ybrˇz ukonˇcili v´ ypoˇcet odmocniny vydˇelen´ım meziv´ ysledku dvˇema. V´ ysledek: 570. Ukonˇcen´ı v´ ypoˇctu pˇred desetinnou ˇca´rkou neznamená, ˇze tento postup nadále neplat´ı. Pokraˇcovali bychom totoˇzn´ ym postupem teoreticky do nekoneˇcna nebo do ukonˇceného rozvoje, pozor pouze na desetinnou ˇcárku:

34

2 4 2 1 1 4

0 0

1 4 0 1 1 4 0,

0 2

1 4 9 1 1 4 0,

6 4

1 4 1 1

9 6 0 4 0, 4

Dostáváme tedy lepˇs´ı odhad odmocniny 570, 2 atd. Vˇsimnˇeme si drobného u ´skal´ı indického postupu. Pˇri hledán´ı druhé cifry z (a podobnˇe i dalˇs´ıch cifer) odmocniny Indové nevycház´ı z podm´ınky 10z × z √ ≤ 751, ale ze slabˇs´ı podm´ınky 10 × z ≤ 75. Proto jejich postup selˇze napˇr. pˇri v´ ypoˇctu 324142. 1. − | − 3 2 4

| − | 1 4 2

2.

− 7 4 1 0

| − | 1 4 2

3.

− 4 1 0

| − | 1 4 2 7

4. 1

| − | −8 4 2 1 4

Nápravu ale zjednáme snadno, vrát´ıme se do pˇredchoz´ıho 3. kroku a m´ısto 7 zvol´ıme ˇc´ıslo o jedniˇcku menˇs´ı, tedy 6.

4.1.3

ˇ ınsk´ C´ y v´ ypoˇ cet druh´ e odmocniny

ˇ ınˇe podobal numerickému v´ V´ ypoˇcet pro zjiˇstˇen´ı druhé odmocniny se v C´ ypoˇctu druhé odmocniny. P˚ uvodn´ı ˇc´ınské pravidlo zn´ı (bez doplˇ nuj´ıc´ıho textu v závorkách): Stanov obsah (ˇctverce) jako dˇelenec. Vezmi jednu poˇc´ıtac´ı tyˇcinku a jdi pˇres jeden (sloupec). Posuˇ n suo-te. Prvn´ı (vybranou ˇc´ıslici odmocniny) násob ˇc´ıslem t’ien-suan, to je dˇelitel. Rozdˇel (j´ım). Po dˇelen´ı zdvojnásob dˇelitel, to je stál´ y ’ dˇelitel. Vrat ho (o jeden d´ılek, dostaneˇs) pˇr´ısluˇsn´ y (pevn´ y) dˇelitel. Dále vrat’ um´ıstˇenou poˇc´ıtac´ı tyˇcinku o krok. (Pokraˇcuj) jako dˇr´ıve. Jednu vybranou (cifru) t´ım násob. Suo-te pˇriˇcti k (pˇr´ısluˇsnému) pevnému dˇeliteli jako dˇr´ıve. Jednu vybranou (cifru) t´ım násob. Suo-te pˇriˇcti k (pˇr´ısluˇsnému) pevnému dˇeliteli a dˇel. Dále jako dˇr´ıve. ([2], str. 51)

35

√ ˇ Nyn´ı si cel´ y algoritmus pˇredvedeme podrobnˇeji na pˇr´ıkladu 173212. Reknˇ eme si jeˇstˇe, ˇze vˇsechny v´ ypoˇcty byly provádˇeny na tzv. poˇc´ıtac´ı desce (viz sekce 6.5). f ang 1 7 3 2 1 2 ˇs fa 1 0 0 0 0 t’ien − suan 4 f ang 1 7 3 2 1 2 ˇs 4 0 0 0 0 fa 1 0 0 0 0 t’ien − suan 4 f ang 1 3 2 1 2 ˇs 8 0 0 0 fa 1 0 0 t’ien − suan 4 1 f ang 1 3 2 1 2 ˇs 8 1 0 0 fa 1 0 0 t’ien − suan 4 1 f ang 5 1 1 2 ˇs 8 2 0 fa ’ 1 t ien − suan 4 1 6 f ang 5 1 1 2 ˇs 8 2 6 fa ’ 1 t ien − suan 4 1 6 f ang 1 5 6 ˇs 8 3 2 fa ’ 1 t ien − suan 1. Nap´ıˇseme odmocˇ nované ˇc´ıslo do ˇrádku ˇs. Na ˇrádku t’ien − suan zaznaˇc´ıme ˇc´ıslo 10000, kter´ ym naznaˇc´ıme nejvˇetˇs´ı lichou cifru dˇelence a které nám pouze ukazuje aktuáln´ı pozici ve v´ ypoˇctu, jinak je k v´ ypoˇctu nepotˇrebujeme. 2. Nyn´ı hledáme nejvˇetˇs´ı moˇzné ˇc´ıslo, jehoˇz mocnina je menˇs´ı nebo rovna 17, coˇz je 4. 4 nap´ıˇseme do ˇrádku f ang a f a na u ´roveˇ n t’ien − suan. 3. Dále vydˇel´ıme 173212 ˇc´ıslem f a (tj. 40000) a na ˇra´dek ˇs nap´ıˇseme zbytek po dˇelen´ı. Nakonec f a zdvojnásob´ıme a posuneme o jedno m´ısto doprava. Posuneme t’ien − suan o dvˇe m´ısta doprava.

36

4. Dˇel´ıme ˇs ˇc´ıslem fa. V´ ysledek, tj. jedniˇcka, nap´ıˇseme do ˇrádku f a za ˇctyˇrku a do ˇra´dku f ang za osmiˇcku. 5. Vydˇel´ıme ˇs ˇc´ıslem f a a zbytek po dˇelen´ı nap´ıˇseme do ˇra´dku ˇs. F a posuneme o jedno m´ısto a t’ien − suan o dvˇe m´ısta doprava. Nakonec jedniˇcku v ˇra´dku f a zdvojnásob´ıme. ˇ vydˇel´ıme f a a dostáváme ˇsestku. Tu 6. Postupujeme totoˇznˇe podle krok˚ u 4. a 5. S nap´ıˇseme do ˇra´dku f ang a f a. 7. Nakonec znovu vydˇel´ıme ˇs ˇc´ıslem f a a zbytek po dˇelen´ı nap´ıˇseme do ˇra´dku f a. 8. Teoreticky bychom mohli pokraˇcovat ve v´ ypoˇctu posunut´ım f a o jedno m´ısto a ˇ ıˇ t’ien − suan o dvˇe m´ısta doprava. To vˇsak C´ nané nedˇelali a ukonˇcili v´ ypoˇcet zaokrouhlen´ım.

37

Kapitola 5 Sˇ c´ıt´ an´ı 5.1 5.1.1

Sˇ c´ıt´ an´ı s tuˇ zkou a pap´ırem ˇ ınsk´ C´ e sˇ c´ıt´ an´ı

ˇ ıˇ Pˇri sˇc´ıtán´ı si C´ nané nejprve poskládali obˇe ˇc´ısla vedle sebe a poté postupnˇe sˇc´ıtali ˇc´ısla od nejvyˇsˇs´ıch cifer po nejmenˇs´ı tak, ˇze od jednoho ˇc´ısla cifry odeˇc´ıtali a k druhému je pˇriˇc´ıtali. Sˇc´ıtán´ı zapisovali zdola nahoru a v nejvyˇsˇs´ım ˇrádku mˇeli koneˇcn´ y v´ ysledek. Tento postup si pˇredvedeme na seˇcten´ı ˇc´ısel 9762 a 8423. Uvád´ıme ho v ˇc´ınsk´ ych ˇc´ıslic´ıch poskládan´ ych z jednotliv´ ych tyˇcinek a v pˇrepisu pomoc´ı arabsk´ ych ˇc´ıslic ([2], str. 25). V´ ysledek: 18185.

Obrázek 5.1: V´ ypoˇcet 9762 + 8423 ˇc´ınsk´ ym zp˚ usobem.

38

5.2 5.2.1

Mechanick´ e pom˚ ucky Soroban

Pokud chceme pomoc´ı sorobanu seˇc´ıst dvˇe ˇc´ısla, mus´ıme si nejdˇr´ıve jedno z nich na sorobanu znázornit. Chceme-li seˇc´ıst 4862 a 8359, znázorn´ıme na sorobanu 4862 (viz obrázek 5.2 a.).

Obrázek 5.2: Sˇc´ıtán´ı 4862 + 8359 na sorobanu. Nyn´ı chceme k 4862 pˇriˇc´ıst ˇc´ıslo 8359. 1. Pˇriˇcteme 8 k 4 a z´ıskáme 12. Na m´ısto 4 dáme 2 a ve sloupci nalevo znázorn´ıme 1 (viz obrázek 5.2 b.). 2. Pokraˇcujeme pˇriˇcten´ım 3 k 8, z´ıskáme 11. Jednu jedniˇcku dáme na m´ısto 8 a druhou pˇriˇcteme ke dvojce ve sloupci nalevo, takˇze z´ıskáme 3 (viz obrázek 5.2 c.). 3. T´ımto zp˚ usobem pokraˇcujeme u zbyl´ ych cifer. V´ ysledek: 13221 (viz obrázek 5.2 d.). Takto m˚ uˇzeme sˇc´ıtat ˇc´ısla aˇz do 1018 . Soroban je v Japonsku stále velmi obl´ıben a uˇc´ı se na nˇem poˇc´ıtat vˇetˇsina dˇet´ı na základn´ıch ˇskolách. Pouˇz´ıvá jej ale i dost dospˇel´ ych, kteˇr´ı na nˇem ˇcasto poˇc´ıtaj´ı rychleji neˇz na kalkulaˇcce ([18], [16]).

5.2.2

Sˇ c´ıt´ an´ı na lin´ ach

Je totoˇzné s naˇs´ım nynˇejˇs´ım, bˇeˇznˇe pouˇz´ıvan´ ym sˇc´ıtán´ım pod sebou, pouze pap´ır a tuˇzka jsou nahrazeny deskou a kameny (viz popis lin v sekci 2.3.2). Sˇc´ıtán´ı zaháj´ıme znázornˇen´ım ˇc´ısel v jednotliv´ ych sloupc´ıch. Napˇr´ıklad seˇcteme ˇc´ısla 457, 236 a 7512 (viz obrázek 5.3). Sˇc´ıtán´ı zaˇcneme od jednotek. Seˇcteme 7 + 6 + 2 = 15. Pˇetku znázorn´ıme v oknˇe jednotek a jedniˇcku si zapamatujeme (viz obrázek 5.3 a.). Poté sˇc´ıtáme dalˇs´ı ˇrádek, nyn´ı des´ıtek, a nezapomeneme na jedniˇcku z pˇredchoz´ıho meziv´ ysledku. Z´ıskáme 10, druhé pol´ıˇcko tedy z˚ ustane prázdné a jedniˇcku si zapamatujeme. T´ımto zp˚ usobem pokraˇcujeme aˇz k v´ ysledku: 8205 (viz obrázek 5.3 b.).

39

Obrázek 5.3: V horn´ı ˇcásti je zaznaˇcen´ı ˇc´ısel 457, 236 a 7512 na poˇcetn´ı desce. V doln´ı ˇca´sti je sˇc´ıtán´ı 457 + 236 + 7512 na linách.

40

Kapitola 6 ´ Uroveˇ n matematiky star´ ych kultur Jiˇz od dob, kdy ˇclovˇek zaˇcal vn´ımat sám sebe a zaˇcal pˇrem´ yˇslet o tom, co je kolem nˇej, musel neodmyslitelnˇe doj´ıt k potˇrebˇe ˇr´ıci, kolik ˇceho je, kolik co váˇz´ı a mˇeˇr´ı. A kdyˇz poprvé nˇekdo vyˇskrabal na zed’ tˇri mamuty, jiˇz m˚ uˇzeme ˇr´ıci: Ano, tady jsou zaˇcátky ” matematiky, tedy snahy zachytit nˇejakou skuteˇcnost pomoc´ı ˇc´ısel.“ Rozvoj matematiky prob´ıhal nerovnomˇernˇe po celé Zemi. Matematika vˇzdy ˇsla ruku v ruce s pokrokem a ˇzádná velká civilizace se bez n´ı neobeˇsla. Od 6. tis´ıcilet´ı pˇr.n.l. se ˇ ınu rozpadá prvotnˇe pospolná spoleˇcnost. na u ´zem´ı od Egypta pˇres Mezopotámii aˇz po C´ Vznikaj´ı zde otrokáˇrské spoleˇcnosti, které m˚ uˇzeme pozdˇeji pozorovat v Americe u Ink˚ u, Azték˚ u a May˚ u. Tato novˇejˇs´ı forma vlády vznikala tam, kde byly lepˇs´ı klimatické a pˇr´ırodn´ı podm´ınky, tedy tam, kde je moˇznost produkce v´ıce j´ıdla neˇz pro zemˇedˇelce saˇ motné. Remesln´ a v´ yroba se oddˇeluje od zemˇedˇelstv´ı, p˚ uda je rozdˇelována do soukromého vlastnictv´ı, obchod stoupá na d˚ uleˇzitosti. Celá spoleˇcnost se stává od tohoto obdob´ı závislá na matematice a na ˇc´ım dál sloˇzitˇejˇs´ıch v´ ypoˇctech. Mus´ı se pˇrece vˇedˇet, kolik je tˇreba odvést na dan´ıch, kolik co stoj´ı a kolik si ˇceho kupuji nebo mám.

6.1

Poziˇ cn´ı a nepoziˇ cn´ı soustavy

V celé práci byly pouˇz´ıvány vˇsechny zápisy v´ ypoˇct˚ u v des´ıtkové poziˇcn´ı soustavˇe, tj. v námi nejpouˇz´ıvanˇejˇs´ı soustavˇe. Málokdo si dnes pˇripust´ı práci ˇci v˚ ubec existenci jiné soustavy neˇz naˇs´ı des´ıtkové poziˇcn´ı nebo pˇrinejhorˇs´ım dvojkové pouˇz´ıvané ve v´ ypoˇcetn´ı technice. Právˇe nepˇripouˇstˇen´ı si jiné soustavy souvis´ı s naˇs´ı v´ yukou, ve které se o jin´ ych soustavách nic nedozv´ıdáme. Trvalo ale dlouhou, ˇcasto pˇreruˇsovanou dobu, neˇz naˇse ˇc´ıselná soustava spatˇrila svˇetlo svˇeta. V nepoziˇcn´ıch soustavách musel existovat speciáln´ı znak pro kaˇzdou mocninu des´ıti, tedy za pˇredpokladu, ˇze byla vyuˇz´ıvána des´ıtková soustava. Pouˇz´ıvaly se napˇr´ıklad i ˇctyˇrkové, pˇetkové nebo ˇsedesátkové soustavy. V tˇechto soustavách také chybˇel symbol pro nulu, jednotlivá ˇc´ısla pak vznikala kladen´ım jednotliv´ ych symbol˚ u za sebe, aniˇz by bylo nutné dbát na jejich vzájemné poˇrad´ı. Základn´ım pˇredpokladem pro poziˇcn´ı soustavy byl objev nuly. K tomu docház´ı kolem roku 628 indick´ ym uˇcencem Brahmaguptou. S poziˇcn´ı nulou má v zápisu ˇc´ısla kaˇzdá ˇc´ıslice specifické postaven´ı k ostatn´ım ˇc´ıslic´ım, protoˇze na pozici ˇc´ıslice závis´ı jej´ı násobek s mocninami des´ıtek, tj. jedna cifra znamená jednotky (tedy cifra × 100 ), dalˇs´ı v poˇrad´ı des´ıtky (cifra ×101 ), dalˇs´ı tis´ıce (cifra ×102 ), atd. Pokud nˇekterá mocnina chyb´ı, vypln´ı se jej´ı m´ısto v zápisu nulou. Poziˇcn´ı zápis ˇc´ısel má obrovskou v´ yhodu: staˇc´ı nám deset 41

symbol˚ u (vˇcetnˇe nuly) pro zápis libovolnˇe velkého ˇc´ısla a práce v této soustavˇe je mnohem snazˇs´ı neˇz v nepoziˇcn´ıch soustavách.

6.2

Egypt

Pyramidy, postavené jiˇz okolo let 3600-2700 pˇr.n.l., jsou pomn´ıky a nesporn´ ymi d˚ ukazy u ´rovnˇe egyptské matematiky. Ke stavbˇe takov´ ych objekt˚ u bylo zapotˇreb´ı poˇct˚ u s velk´ ymi“ ” ˇc´ısly a jednoduˇsˇs´ıch geometrick´ ych operac´ı. V Egyptˇe se tyto znalosti vyuˇz´ıvaly také pˇri stavbˇe zavlaˇzovac´ıch kanál˚ u, mˇest, pˇrehrad a vodn´ıch nádrˇz´ı. Také bylo tˇreba sˇc´ıtat obyvatelstvo, polnosti a veˇsker´ y majetek, protoˇze zde existovala centralizovaná vláda pod záˇstitou faraona, které se odvádˇely danˇe. Velkou roli hrál také pˇresn´ y kalendáˇr, podle kterého se urˇcovalo obdob´ı rozvodˇ nován´ı Nilu.

Obrázek 6.1: Symbolick´ y zápis ˇc´ısla 21623.

Egypt’ané jiˇz znali nepoziˇcn´ı des´ıtkovou ˇc´ıselnou soustavu. Mˇeli speciáln´ı symbol pro ˇc´ıslo 1 a pro mocniny 10 aˇz po 107 (napˇr. milión se znaˇcil symbolem praboha Hh, kter´ y nese oblohu nad zem´ı). Ostatn´ı ˇc´ısla se znaˇcila opakován´ım znak˚ u pro mocniny deseti ’ a jejich kladen´ım za sebe. Egypt ané psali zprava doleva, stejné symboly kladli za sebe maximálnˇe ˇctyˇri, poté udˇelali mezeru. Uˇcenci Egypta byli p´ısaˇri, kteˇr´ı zastávali vˇetˇsinu d˚ uleˇzit´ ych svˇetsk´ ych funkc´ı. Právˇe proto to bylo jedno z nejlukrativnˇejˇs´ıch zamˇestnán´ı. Nauˇcen´ı Chetiho P´ısaˇrskému umˇen´ı se vˇenuj s láskou! Vˇez, ˇze nen´ı nad p´ısaˇrské umˇen´ı. P´ısaˇrské umˇen´ı mus´ıˇs milovat v´ıc neˇz svou matku. Pˇred tv´ ym pohledem bude krása. Toto umˇen´ı je vˇetˇs´ı neˇz kaˇzd´ y jin´ yu ´ˇrad a v zemi nemá obdoby. Vˇez, kaˇzdé povolán´ı má pˇredstaveného. Jen p´ısaˇr je pˇredstaven´ y sám sobˇe. Vˇez, ˇze nen´ı p´ısaˇre, kterému by se nedostávalo j´ıdla, statk˚ u z královského domu, ˇzivota, blahobytu, zdrav´ı ... Jeho otec a matka veleb´ı boha, ˇze ho postavil na cestu ˇzivota ([1], str. 171). Egypt’ané jistˇe znali základn´ı ˇctyˇri aritmetické operace, které si ulehˇcovali skládán´ım kam´ınk˚ u. Kromˇe toho byli zbˇehl´ı v poˇc´ıtán´ı se zlomky. Jejich rozvoj si vynutila potˇreba poˇc´ıtán´ı kalendáˇre. Mˇes´ıc rozdˇelili na tˇricet tˇricetin - dn˚ u. Sloˇzitˇejˇs´ı zlomky skládali z tzv. kmenov´ ych zlomk˚ u (zlomk˚ u s ˇcitatelem rovn´ ym jedné), z nichˇz nejstarˇs´ı byly zlomky 1/2, 1/4, 1/8, 1/16, . . . , tedy zlomky, v jejichˇz jmenovateli byly mocniny dvou. Egyptská a stejnˇe tak i vˇsechny ostatn´ı starovˇeké civilizace neznaly symboliku. Egypt’ané sice ˇreˇsili mnohé u ´lohy podobné tˇem naˇsim, mˇeli ale zadán´ı i v´ ypoˇcet ve slovn´ı podobˇe. Vu ´lohách hospodáˇrského charakteru se objevovaly objemy i povrchy tˇeles a mnohé geometrické otázky. Celkovˇe byla egyptská matematika na obstojné u ´rovni. Neexistovaly sice ˇza´dné obecné vzorce a k mnoh´ ym v´ ysledk˚ um se docházelo ˇcistˇe empirickou cestou, pro nejˇcastˇejˇs´ı typy 42

pˇr´ıklad˚ u ale existovaly vzory ˇreˇsen´ı. Ty by se mohly povaˇzovat za prap˚ uvodn´ı poˇca´tky algebraick´ ych metod. Egyptská matematika pouˇz´ıvala podobné v´ ypoˇcetn´ı metody jako matematika babylonská, z ˇcehoˇz lze usuzovat, ˇze spolu mˇely obˇe kultury styky. Pozdˇeji mˇela egyptská matematika vliv na formován´ı matematiky ˇrecké ([5]).

6.3

Mezopot´ amie

Jiˇz okolo 4. tis´ıcilet´ı pˇr.n.l. se na u ´zem´ı n´ıˇzin ˇrek Eufrat a Tigris nacházely dva silné otrokáˇrské státy s rozvinut´ ym zemˇedˇelstv´ım a ˇremeslnou v´ yrobou. Zemˇedˇelstv´ı se op´ıralo o umˇelé zavlaˇzován´ı a o pluh. Pˇri v´ ystavbˇe mˇest se pouˇz´ıvaly pˇr´ımé, na sebe kolmé ulice. Stupˇ novité chrámy vzdálenˇe pˇripom´ınaly pyramidy. Kolem 2. tis´ıcilet´ı pˇr.n.l. byly národy na tomto u ´zem´ı podmanˇeny Babyloˇ nany. Nov´ ym kulturn´ım, obchodn´ım a administrativn´ım centrem se stal Babylon. Administrativn´ı oporou Babylonu byli opˇet p´ısaˇri, nejvˇetˇs´ı svˇetˇst´ı vzdˇelanci. Psali na hlinˇené tabulky vymaˇckáván´ım jednotliv´ ych symbol˚ u. Poté se tabulky vysuˇsily na slunci. Babyloˇ nané vˇetˇsinou vyuˇz´ıvali ˇsedesátkovou soustavu, znali ale i soustavu des´ıtkovou. Psali kl´ınov´ ym p´ısmem. Jednotlivé znaky se ˇcasto liˇsily pouze velikost´ı symbolu ˇci podle okoln´ıch znak˚ u. Celkovˇe platila nejednotnost zápisu, coˇz nám nyn´ı velmi ztˇeˇzuje práci pˇri pˇrekladu tabulek s matematick´ ymi ˇci astronomick´ ymi texty. Matematika Babylonu byla pokroˇcilejˇs´ı neˇz matematika egyptská. Dochovaly se tis´ıce tabulek s matematick´ ymi texty, bohuˇzel je zat´ım pˇreloˇzena jen nepatrná ˇcást z nich. V´ıme, ˇze znali ˇctyˇri základn´ı aritmetické operace, ˇreˇsili kvadratické rovnice, vyuˇz´ıvali zlomky. Pro zlomky mˇeli speciáln´ı pomocné tabulky se základn´ımi násobky zlomk˚ u. Právˇe pˇri poˇctech se zlomky dávali pˇrednost soustavˇe ˇsedesátkové. Taktéˇz se poˇc´ıtalo s procenty a dochovaly se tabulky s pˇr´ıklady, které bychom nyn´ı ˇreˇsili pomoc´ı algoritm˚ u, Babyloˇ nané je ale nejsp´ıˇse neznali a ˇreˇsili je postupn´ ym zkouˇsen´ım a pˇribliˇzován´ım se k v´ ysledku. Zpoˇca´tku se zdálo, ˇze geometrie nebyla v Mezopotámii na vysoké u ´rovni. To se vˇsak zmˇenilo v roce 1939, kdy byly v Suzách objeveny nové kl´ınopisné tabulky. Z nich se dozv´ıdáme, ˇze geometrie v Babylonu rozvinutá byla. Poˇc´ıtaly se polomˇery opsan´ ych a vepsan´ ych kruˇznic, napˇr´ıklad do troj´ uheln´ık˚ u. Hodnota π byla urˇcena jako 3 + 7/60 + 30/602 = 3, 125 (tj. s odchylkou menˇs´ı neˇz 1, 7%) Mezi matematikou Egypta a Babylonu m˚ uˇzeme naj´ıt mnoho spoleˇcného ze dvou d˚ uvod˚ u. Prvn´ım je, jak jiˇz jsme zmiˇ novali, ˇze spolu byly nejsp´ıˇse obˇe zemˇe v kontaktu, druh´ ym je podobná forma vlády, která poˇzadovala ˇreˇsen´ı stejn´ ych u ´loh - tvorba kalendáˇre, vymˇeˇrován´ı pozemk˚ u, dan´ı apod. Dá se také pˇredpokládat, ˇze mnohé matematické prinˇ ˇ ıˇ cipy Babylonu a Egypta pˇrevzali i Indové a Rekov´ e, moˇzná i C´ nané, pozdˇeji pak Arabové a Evropané ([5]).

6.4

Idi´ ansk´ e kmeny Ameriky

Populace na americkém kontinentu byla dlouho oddˇelena od v´ yvoje Asie a Evropy. Prvn´ı otrokáˇrské státy zde vznikaj´ı aˇz na poˇcátku naˇseho letopoˇctu. Nejvˇetˇs´ıho rozkvˇetu pak dosáhly okolo 4.-6. stol. n.l. Vládu ˇr´ıˇs´ı drˇzeli ve sv´ ych rukou veleknˇeˇz´ı. Mayov´ e jiˇz od 4. stol. pˇr. n. l. pouˇz´ıvaj´ı poziˇcn´ı ˇc´ıselnou soustavu se znaky pro ˇc´ısla ˇ ısla psali jako ostatn´ı text do sloupc˚ 0 − 19 a se základem 20. C´ u.

43

Obrázek 6.2: Mayská ˇc´ıselná soustava.

ˇ Vˇetˇsina matematick´ ych text˚ u May˚ u se nedochovala v d˚ usledku kolonizace Spanˇ ely, kteˇr´ı spálili vˇsechny p˚ uvodn´ı spisy. M˚ uˇzeme se ale domn´ıvat, ˇze matematika byla na vysoké u ´rovni. Poˇc´ıtali velmi pˇresnˇe kalendáˇr. Rok byl tvoˇren z 18 × 20 = 360 dn´ı a 5 závˇereˇcn´ ych dn´ı. Rozd´ıl poté dorovnávali pˇrestupn´ ymi roky jako dnes my. Znali také mnohá souhvˇezd´ı, Polárku, poˇc´ıtali budouc´ı zatmˇen´ı slunce, velmi pˇresnˇe popsali pohyby Venuˇse ([5]). Azt´ ekov´ e a Inkov´ e na u ´zem´ı Mexika a Peru mˇeli podobné znalosti matematiky jako Mayové. Aztékové vyuˇz´ıvali dvac´ıtkovou nepoziˇcn´ı soustavu.

Obrázek 6.3: Aztécká ˇc´ıselná soustava.

44

Inkové mˇeli uzlové p´ısmo zvané kipu“. T´ım zapisovali jak kalendáˇr, tak i u ´ˇcetnictv´ı ” a danˇe. Po Aztéc´ıch a Inc´ıch se dochovaly pouze hmotné památky, pozoruhodná architektura, ˇ zavlaˇzovac´ı systémy, silnice. Spanˇ elé poˇca´tkem 16. stolet´ı zniˇcili vˇse, co se dalo.

6.5

ˇ ına C´

Prvn´ı zm´ınky o ˇc´ınské matematice t´ ykaj´ıc´ı se pˇredevˇs´ım sestavován´ı kalendáˇre máme uˇz z obdob´ı kolem poloviny 2. tis´ıcilet´ı pˇr. n. l. Jiˇz v tomto obdob´ı bylo hlavn´ı obˇzivou obyvatelstva zemˇedˇelstv´ı a s n´ım spojená potˇreba kalendáˇre. V´ ypoˇcty pˇri tvorbˇe kalendáˇr˚ u ˇ dokazuj´ı dobré aritmetické znalosti C´ıˇ nan˚ u, pˇresto nemáme ˇza´dné hmatatelné d˚ ukazy o v´ yvoji matematiky témˇeˇr do poˇca´tku naˇseho letopoˇctu. Prvn´ı dochované d´ılo Matematika v dev´ıti kapitolách jiˇz obsahuje souhrn mnoha znalost´ı. ˇ ına nejvˇetˇs´ı ˇr´ıˇs´ı. Astronomická Kolem roku 800 n. l. za vlády dynastie Tchang byla C´ pozorován´ı v té dobˇe dosahuj´ı vysoké pˇresnosti. Napˇr´ıklad obˇeh planety Saturn kolem Slunce byl urˇcen na 28,51 let, coˇz je jen o 0,05 roku vˇetˇs´ı hodnota neˇz skuteˇcná. V 7. stolet´ı byl vynalezen knihtisk a ve stejném stolet´ı je také zahájena stavba velkého kanálu spojuj´ıc´ıho sever zemˇe s jihem. Tento kanál byl dokonˇcen aˇz v 18. stol. v délce 1700 ˇ ınˇe pˇrikládal velk´ km. Vyuˇcován´ı matematiky se v C´ y v´ yznam. Jiˇz od 10 stol. pˇr. n. l. se vyuˇcovala matematika u dˇet´ı od 6 let. Obt´ıˇzné matematické vzdˇelán´ı a s n´ım spojené státn´ı zkouˇsky z´ıskaly na váˇznosti od 5. stol. n. l. Od 10. stol. pˇr. n. l. se objevuj´ı ˇc´ıslice na keramick´ ych a bronzov´ ych pˇredmˇetech ˇci ˇ na minc´ıch. Jiˇz v této dobˇe se pouˇz´ıvá des´ıtková poziˇcn´ı soustava. C´ıslice znamenaj´ıc´ı hodnotu jednotek byly psány svisle, des´ıtky poté horizontálnˇe. Cifry stovek se psaly jako cifry jednotek a cifry tis´ıc˚ u opˇet jako cifry des´ıtek.

ˇ ınská ˇc´ıselná soustava. Obrázek 6.4: C´

45

ˇ ıˇ Matematické u ´kony C´ nané vˇetˇsinou zaznamenávali kladen´ım tyˇcinek na poˇc´ıtac´ı desku. ˇ ınské ˇc´ıslice Tyˇcinky byly velké do 15 centimetr˚ u, vyrábˇely se ze dˇreva, kovu ˇci slonoviny. C´ maj´ı p˚ uvod právˇe v kladen´ı tyˇcinek. Poˇc´ıtac´ı deska nebyla niˇc´ım v´ yjimeˇcná, jednalo se pouze o dostateˇcnˇe velkou rovnou plochu. Znalost malé násobilky se stala souˇca´st´ı základn´ıho matematického vzdˇelán´ı. Byla ˇ ınˇe také bylo hojnˇe objevena ˇrada tabulek, které obsahovaly jednotlivé souˇciny. V C´ vyuˇz´ıváno kuliˇckové poˇc´ıtadlo suan-pchan podobné evropskému abaku, které nejsp´ıˇse poslouˇzilo za pˇredlohu japonskému sorobanu. Právˇe obliba poˇc´ıtadla nejsp´ıˇse zapˇr´ıˇcinila pozdn´ı zaveden´ı znaku pro nulu, která se poprvé objevuje aˇz ve 13. stolet´ı. ˇ ınská matematika na pˇrelomu tis´ıcilet´ı jiˇz poˇc´ıtala celou ˇradu u C´ ´loh. V knize Matematika v dev´ıti kapitolách nalézáme u ´lohy s pomˇery, lineárn´ımi rovnicemi a jejich soustavami, zlomky, v´ ypoˇcty objem˚ u a obsah˚ u ([2], od str. 18).

6.6

Starovˇ ek´ a Indie

Jiˇz ve 3. tis´ıcilet´ı pˇr.n.l. nacház´ıme v okol´ı Indu památky o rozvinuté spoleˇcnosti. V bl´ızkosti vrchoviny Mohendˇzo-daro se nacházelo na svou dobu pˇrekvapivˇe velké a dobˇre ˇreˇsené mˇesto. Kolmé ulice, kanalizace, zavlaˇzovac´ı systémy, to vˇse nasvˇedˇcuje tomu, ˇze tehedejˇs´ı spoleˇcnost mˇela dobré znalosti matematiky a nejsp´ıˇse i astronomie. Bohuˇzel se vˇsak ˇzádné matematické texty nenaˇsly a objevené piktografické nápisy na pˇredmˇetech nejsou doposud vyluˇstˇeny. Celé mˇesto bylo z nám neznám´ ych d˚ uvod˚ u opuˇstˇeno kolem poloviny 2. tis´ıcilet´ı pˇr.n.l. a na uvolnˇená u ´zem´ı pˇricház´ı kmeny a´rijc˚ u (v jejich jazyce urozen´ı“). Poˇcátkem 1. tis´ıcilet´ı ” pˇr.n.l. bylo hlavn´ı obˇzivou obyvatel zemˇedˇelstv´ı s ˇc´ımˇz souvis´ı v´ ystavba zavlaˇzovac´ıch systém˚ u a astronomie pro urˇcen´ı kaˇzdoroˇcnˇe se opakuj´ıc´ıch záplav. O stolet´ı pozdˇeji nacház´ıme prvn´ı zm´ınky o styc´ıch s Asyri´ı a Babyloni´ı. Pozdˇeji pak kolem 6. stolet´ı pˇr.n.l. i s rychle se rozv´ıjej´ıc´ı antickou Evropou. ˇ ıma a C´ ˇ ıny, v této dobˇe Kolem 1. stolet´ı pˇr. n. l. se indiˇct´ı vyslanci dostávaj´ı do R´ ˇ ıny. Nejvˇetˇs´ı rozkvˇet vˇedy nastává od se také nejsp´ıˇse dostává buddhismus z Indie do C´ 4. stolet´ı, kdy jiˇz funguj´ı v nˇekolika mˇestech univerzity a ˇrada niˇzˇs´ıch ˇskol. Vzniká celá ˇrada anstronimick´ ych dˇel, které se ˇca´steˇcnˇe zmiˇ nuj´ı i o matematick´ ych v´ ypoˇctech. Mimo to jsou proslulé ˇskoly humanitn´ıch vˇed, teologie, filozofie i pˇr´ırodn´ıch vˇed. Matematika mˇela v Indii vˇzdy velkou váˇznost, dokonce se ji podle povˇest´ı zaˇcal uˇcit Buddha v osmi letech. Dochoval se nám dokonce chvalozpˇev na matematiku z 9. stolet´ı od barda“ Maháv´ıra. ” Matematické texty nalézáme pˇribliˇznˇe od 6. stolet´ı. n.l. Kromˇe základn´ıch operac´ı bˇeˇznˇe pouˇz´ıvali zlomky, znaly v´ ypoˇcet druhé odmocniny a pˇribliˇzn´ y v´ ypoˇcet tˇret´ı odmocniny. Také se ˇreˇsily r˚ uzné druhy rovnic, jejichˇz zadán´ı vˇetˇsinou vycházelo z geometrick´ ych u ´loh. Napˇr´ıklad byla známa i Pythagorova vˇeta. Nejvˇetˇs´ım pˇr´ınosem indické matematiky nejsp´ıˇse bylo zaveden´ı des´ıtkové poziˇcn´ı soustavy a jej´ı pozdˇejˇs´ı rozˇs´ıˇren´ı do svˇeta. Jiˇz od 2. stolet´ı pˇr.n.l. existovaly speciáln´ı symboly pro ˇc´ıslice 1 − 9. Prozat´ım ale stále existovaly speciáln´ı symboly pro ˇc´ısla 10, 20, 30, 40 . . . a ˇc´ısla se vˇetˇsinou tvoˇrila souˇctem jednotliv´ ych ˇc´ısel napsan´ ych za sebou (stejnˇe jako v ˇr´ımském zápisu ˇc´ısel). V tomto obdob´ı vedle sebe existovalo nˇekolik typ˚ u zápis˚ u ˇc´ısel, ve kter´ ych byla velká nesourodost, ˇcemuˇz napomáhalo i ˇca´steˇcné prol´ınán´ı jednotliv´ ych zápis˚ u. Napˇr´ıklad ze zápisu indick´ ych ˇc´ıslic kharóˇsth´ı (nepoziˇcn´ı des´ıtková soustava) si lze uvˇedomit, ˇze p˚ uvodn´ı ˇc´ıselné soustavy v Indii musely b´ yt ˇctverkové.

46

Obrázek 6.5: Indická ˇc´ıselná soustava kharóˇsth´ı.

Kolem 6. stolet´ı n.l. se objevuj´ı prvn´ı zápisy nuly v matematick´ ych textech, coˇz je jeden z nejd˚ uleˇzitˇejˇs´ıch okamˇzik˚ u ve v´ yvoji matematiky, protoˇze objeven´ı nuly pˇr´ımo vede k poziˇcn´ım soustavám. Ta se v Indii objevuje kolem 9. stolet´ı, kdy docház´ı k dovrˇsen´ı v´ yvoje des´ıtkové poziˇcn´ı soustavy.

6.7

Arabsk´ y svˇ et

ˇ ımské ˇr´ıˇse a nástupem nové, netolerantn´ı kˇrest’anské v´ıry hledaj´ı ˇreˇct´ı i S rozpadem R´ ˇr´ımˇst´ı uˇcenci azyl mimo Evropu. Ten nejdˇr´ıve nacházej´ı v Byzantské ˇr´ıˇsi, ovˇsem i zde ˇcasem posiluje kˇrest’ansntv´ı a nepˇra´telstv´ı proti jin´ ym v´ırám a myˇslenkov´ ym proud˚ um. V roce 529 nechává byzantsk´ y c´ısaˇr Justinián zavˇr´ıt athénskou ˇskolu platonik˚ u, kteˇr´ı nacházej´ı azyl v rychle se rozv´ıjej´ıc´ı Arabské ˇr´ıˇsi. Do 8. stolet´ı n.l. Arabové ovládli Malou Asii, Kavkaz, Stˇredn´ı Asii, Severn´ı Afriku a Pyrenejsk´ y poloostrov. Ke konci 8. stolet´ı se mnoho evropsk´ ych, ale i indick´ ych ˇci ’ babylonsk´ ych uˇcenc˚ u soustˇred uje do Bagdádu. Právˇe na znalostech tˇechto zahraniˇcn´ıch uˇcenc˚ u se tvoˇr´ı základy a dalˇs´ı rozvoj arabské vˇedy. V Bagdádu se zakládá velká knihovna obsahuj´ıc´ı opisy dˇel aˇz z Byzance, kam byla pod záˇstitou chal´ıfa poslána skupina p´ısaˇr˚ u. V dobˇe nejvˇetˇs´ıho rozkvˇetu obsahovala okolo 400 000 svazk˚ u. Ve mˇestˇe také existovala celá ˇrada menˇs´ıch knihoven a kniˇzn´ıch obchod˚ u. Zat´ımco Evropa proˇz´ıvala dobu temna, arabsk´ y svˇet prohluboval vˇedomosti ve vˇsech rovinách. Nejinak tomu bylo i u matematiky. Je ironi´ı, ˇze mnoho dˇel se dostalo do arabské ˇr´ıˇse po pˇrekladu z ˇreˇctiny ˇci latiny a znovu se do Evropy vrac´ı jako pˇreklady z arabˇstiny do latiny. Dlouhou dobu byla vyuˇz´ıvána ˇsedesátková soustava, která se zde udrˇzela aˇz do 9. stolet´ı. Prvn´ı d´ılo, které popisovalo des´ıtkovou soustavu a operace v n´ı, byl Al-Chwárizm´ıho aritmetick´ y traktát. Ten se bohuˇzel dochoval pouze v ne´ uplném latinském pˇrekladu z poloviny 12. stolet´ı. Pˇrepis také obsahuje mnohé chyby a nové ˇc´ıslice jsou prostˇe vynechány. Spis je uloˇzen v univerzitn´ı knihovnˇe v Cambridge, a aˇckoli nen´ı pojmenován, d´ıky Ka” talogu vˇed“, soupisu knih nˇekdejˇs´ı bagdádské knihovny, se podaˇrilo naj´ıt p˚ uvodn´ı název knihy - Kniha o sˇc´ıtán´ı a odeˇc´ıtán´ı podle indického zp˚ usobu. Z tohoto názvu je zˇrejmé, ˇze pˇredlohou arabské des´ıtkové soustavy byla ˇc´ıselná soustava indická. Arabské matematice se jiˇz pˇred 1. tis´ıcilet´ım n.l. podaˇrilo nˇeco do té doby nev´ıdaného. D´ıky své otevˇrenosti uˇcenc˚ um a vˇedˇen´ı bez rozd´ıl˚ u v´ıry nebo p˚ uvodu se zde poprvé za dobu existence lidstva propojilo vˇedˇen´ı celého tehdy známého svˇeta a pozdˇeji poslouˇzila jako pokladnice vˇedomost´ı pro nadcházej´ıc´ı zlat´ y vˇek objev˚ u a rozvoje Evropy ([2], od str. 177). 47

Kapitola 7 V´ yznamn´ı matematikov´ e 7.1

Al-Chw´ arizm´ı

Al-Chwárizm´ı byl matematik arabského p˚ uvodu ˇzij´ıc´ı okolo let 780–850. Na obrázku 7.1 je známka vydaná v SSSR u pˇr´ıleˇzitosti 1200. v´ yroˇc´ı narozen´ı Al-Chwárizm´ıho, aˇckoliv datum narozen´ı ani u ´mrt´ı nen´ı pˇresnˇe známo.

Obrázek 7.1: Al-Chwárizm´ı na ruské známce. Z jeho d´ıla se dochovalo pˇet ˇca´steˇcnˇe pˇrepracovan´ ych opis˚ u, které jsou vˇenovány algebˇre, astronomii, geografii a v´ ypoˇct˚ um kalendáˇre. Jeho práce v oblasti aritmetiky a algeˇ asti jeho práce byly pozdˇeji pˇreb´ırány bry mˇely velk´ y vliv na dalˇs´ı rozvoj matematiky. C´ a komentovány v prac´ıch následuj´ıc´ıch des´ıtek generac´ı. Al-Chwárizm´ıho aritmetick´ y traktát je prvn´ı známou arabskou prac´ı, v n´ıˇz je vyloˇzena indická des´ıtková poziˇcn´ı soustava a objasnˇeny matematické u ´kony v této soustavˇe. Tato jeho práce se dochovala pouze v jediném latinském pˇrekladu z poloviny 13. stolet´ı, kter´ y vˇsak nen´ı plnˇe dokonˇcen´ y a zaˇc´ıná slovy: Algorizmi pravil...“. Právˇe z této zkomole” niny Al-Chwárizm´ıho jména pocház´ı slovo algoritmus. Z Al-Chwárizm´ıho algebraického traktátu zase pocház´ı slovo al-dˇzebr, v nˇemˇz má p˚ uvod dneˇsn´ı term´ın algebra, které oznaˇcovalo seˇcten´ı dvou rovnic s c´ılem zbavit se neznámé. Dalˇs´ı latinské spisy jako napˇr. Algorizmova kniha o praxi aritmetiky (1135–1153) nebo Kniha uveden´ı Algorizma do umˇen´ı astronomického, sestavená mistrem A. (kolem r. 1143) se ˇcásteˇcnˇe odvolávaj´ı na Al-Chwárizm´ıho a jeho d´ıla ([2]).

48

7.2

John Napier

John Napier z Merchistonu (1550–1617) byl skotsk´ y matematik, fyzik, astronom a astrolog. Do pamˇeti se zapsal jako vynálezce logaritmu, proto se na jeho poˇcest pˇrirozenému logaritmu (tedy logaritmu o základu e) ˇr´ıká Napier˚ uv logaritmus.

Obrázek 7.2: John Napier.

Jeho otec byl biskupem v Orkney a silná v´ıra se pˇrenesla i na syna. Napier ovˇsem pojal v´ıru po svém a na základˇe studia Zjeven´ı Janova, posledn´ı knihy Nového zákona, pˇredpovˇedˇel apokalypsu a dokázal, ˇze papeˇz je antikrist. Odtud je jiˇz jen kr˚ uˇcek k jeho dalˇs´ımu zájmu - okultn´ım vˇedám (alchymii a astrologii). Nen´ı divu, ˇze byl sv´ ymi sousedy povaˇzován za ˇcarodˇeje. Traduje se historka, ˇze Napier˚ uv ˇcern´ y kohout umˇel odhalit mezi sluhy zlodˇeje. Zˇrejmˇe to ale bylo tak, ˇze kaˇzd´ y ze sluh˚ u byl Napierem vyzván, aby se kohouta dotkl. A jelikoˇz byl kohout pomazán sazemi, mˇeli pak nevinn´ı sluhové ˇcerné ruce, zat´ımco vin´ık se dotknout bál, a jeho ruce tedy z˚ ustaly ˇcisté.

7.3

Augustin Louis Cauchy

Augustin Louis Cauchy (1789–1857) byl matematik francouzského p˚ uvodu, pr˚ ukopn´ık matematické anal´ yzy a Napoleon˚ uv inˇzen´ yr. Byl siln´ y katol´ık a pˇr´ıvrˇzenec královské rodiny, coˇz ho pˇrivedlo do nˇekolika konflikt˚ u po Francouzské revoluci. ´ Nejdˇr´ıve studoval na Ecole Centrale du Panthéon, kde se nauˇcil hlavnˇe latinu. Poté v ´ roce 1804 vstoupil na ˇskolu Ecole Polytechnique se zamˇeˇren´ım na stavbu most˚ u a cest. Jiˇz po dvou letech studia patˇril k nejlepˇs´ım student˚ um. Po roce 1810 byl nejdˇr´ıve povolán ´ na stavbu Port Napoléon v Cherbourg, po pádu Napoleona se stal profesorem na Ecole Polytechnique. Po dalˇs´ım pˇrevratu ve Francii roku 1830, kdy byl sesazen Karel X. a na tr˚ un usedl král Louis Philippe, odeˇsel Cauchy jako uˇcitel vnuka Karla X. do exilu a pob´ yval chv´ıli i v Praze. Roku 1839 se Cauchy znovu vrac´ı do Paˇr´ıˇze, protoˇze vˇsak nesloˇzil pˇr´ısahu nové vládˇe, byl sice profesorem, ale nedostával plat. Posledn´ı dny doˇzil v rodinném kruhu ve vesniˇcce Sceaux bl´ızko Paˇr´ıˇze. Od roku 1839 do roku 1848 vydal pˇres 300 odborn´ ych stat´ı, tj. témˇeˇr jednu za t´ yden. Spolu s Leonhardem Eulerem, Arthurem Cayleym a Paulem Erd˝osem patˇr´ı mezi nejplodnˇejˇs´ı autory matematick´ ych ˇclánk˚ u vˇsech dob.

49

Obrázek 7.3: Augustin Louis Cauchy.

7.4

Jakub Filip Kulik

Jelikoˇz je Kulikovo jméno v dˇejinách ˇceské matematiky v´ yznamné, ˇrekneme si o nˇem alespoˇ n pár základn´ıch informac´ı. Jakub Filip Kulik (1793–1863) se narodil ve Lvovˇe a studoval filozofii a práva na tamn´ı univerzitˇe, brzy vˇsak zaˇcal t´ıhnout k matematice. V roce 1914 se pˇrihlásil do konkurzu na m´ısto profesora olomouckého lycea a téhoˇz roku tam byl jmenován ˇra´dn´ ym profesorem. O dva roky pozdˇeji byl jmenován profesorem fyziky ˇ na univerzitˇe ve St´ yrském Hradci. Na této univerzitˇe sloˇzil roku 1822 doktorské zkouˇsky a o rok pozdˇeji byl zvolen jej´ım rektorem. V roce 1826 byl jmenován profesorem vyˇsˇs´ı matematiky na univerzitˇe v Praze. Vedle podrobn´ ych uˇcebnic vyˇsˇs´ı anal´ yzy a mechaniky jsou nejv´ yznamnˇejˇs´ı jeho d´ıla tabulková (tabulky násoben´ı, druh´ ych a tˇret´ıch mocnin, logaritmické, trigonometrick´ ych a hyperbolick´ ych funkc´ı a jejich logaritm˚ u, tabulky k v´ ypoˇctu obsahu válcov´ ych a kuˇzelov´ ych nádob, dˇelitel˚ u ˇc´ısel, primitivn´ıch koˇren˚ u). Kromˇe toho Kulik sestavil známé Kulikovy tabulky dˇelitel˚ u ˇc´ısel od 3 do 100 milion˚ u, které byly uloˇzeny do knihovny V´ıdeˇ nské c´ısaˇrské akademie vˇed a na kter´ ych Kulik pracoval dvacet let. Poznamenejme, ˇze pˇri ruˇcn´ım sestavován´ı tak obsáhl´ ych tabulek se Kulik samozˇrejmˇe nevyhnul chybám. Nav´ıc v dneˇsn´ı dobˇe poˇc´ıtaˇc˚ u jeho d´ılo pˇrirozenˇe upadlo v zapomnˇen´ı.

7.5

Anton´ın Svoboda

Anton´ın Svoboda (1907–1980) byl jeden z nejv´ yznamˇejˇs´ıch novodob´ ych ˇcesk´ ych matematik˚ u a pr˚ ukopn´ık˚ u v´ ypoˇcetn´ı techniky. Narodil se v Praze jako syn profesora ˇceského jazyka. Vystudoval dvˇe vysoké ˇskoly, nejdˇr´ıve elektrotechnické a strojn´ı inˇzen´ yrstv´ı na ˇ ˇ CVUT, poté fyziku na Karlovˇe Univerzitˇe. Po obsazen´ı Ceskoslovenska nacisty ut´ıká i se svou manˇzelkou a kolegou Vladim´ırem Vandem ze zemˇe nejdˇr´ıve do Francie odkud se jim pozdˇeji po témˇeˇr neuvˇeˇriteln´ ych cestách podaˇr´ı vycestovat do USA. V Americe spolupracoval na v´ yvoji samoˇcinn´ ych poˇc´ıtaˇc˚ u pro vojensk´ y projekt protiletadlového zamˇeˇrovac´ıho systému MARK 46, kter´ y se pouˇz´ıval na letadlov´ ych lod´ıch dalˇs´ıch 50 let. ˇ V roce 1946 se vrac´ı zpátky do Ceskoslovenska a vydává knihu o mechanick´ ych poˇc´ıtac´ıch zaˇr´ızen´ıch, která o dva roky pozdˇeji vycház´ı i v USA, kde ve stejn´ y rok obdrˇz´ı ocenˇen´ı Naval Ordance Development Award. I proto mˇel v následuj´ıc´ıch letech problematiˇctˇejˇs´ı 50

pozici v komunistickém reˇzimu. Roku 1950 zaloˇzil Oddˇelen´ı matematick´ ych stroj˚ u. Pod záˇstitou této instituce zaˇcal od roku 1951 pracovat na prvn´ım ˇceskoslovenském samoˇcinném poˇc´ıtaˇci, zkrácenˇe SAPO, jehoˇz základn´ı souˇcástkou byla elektromagnetická relé. SAPO byl poprvé slavnostnˇe spuˇstˇen v roce 1958, ale bohuˇzel jiˇz roku 1960 vyhoˇrel. Dalˇs´ım Svobodov´ ym projektem byl poˇc´ıtaˇc EPOS, Elektronkov´ y POˇc´ıtaˇc Stroj. Zaj´ımavost´ı je, ˇze EPOS pracoval v des´ıtkové soustavˇe a hardwarovˇe sd´ılel ˇcas aˇz pro pˇet program˚ u. ’ Byl spuˇstˇen v roce 1960, mˇel pamˇet 40 tis´ıc slov a rychlost pˇribliˇznˇe 35 tis´ıc operac´ı za sekundu. Následuj´ıc´ı upravená tranzistorová verze byla spuˇstˇena roku 1962. Roku 1964 Svoboda opˇet emigroval do Ameriky, kde z˚ ustal aˇz do své smrti, která ho zastihla pˇri pozorován´ı v´ ybuchu sopky Mount St Helen roku 1980 ([17]).

51

Kapitola 8 Z´ avˇ er C´ılem práce bylo zachytit v´ yvoj základn´ıch aritmetick´ ych operac´ı od starovˇeku aˇz do dneˇsn´ıch dn˚ u. Podaˇrilo se nám sesb´ırat z nejr˚ uznˇejˇs´ıch zdroj˚ u bohatou ˇskálu algoritm˚ u násoben´ı, dˇelen´ı, v´ ypoˇctu druhé odmocniny a sˇc´ıtán´ı. Pˇr´ınos práce spoˇc´ıvá tedy zˇcásti v reˇserˇsn´ı ˇcinnosti - hledán´ı algoritm˚ u. Jeˇstˇe vˇetˇs´ım pˇr´ınosem je ovˇsem srozumiteln´ y popis algoritm˚ u, které byly v mnoha pˇr´ıpadech v p˚ uvodn´ıch zdroj´ıch pouze zbˇeˇznˇe naznaˇceny a nikoliv podrobnˇe vysvˇetleny a ilustrovány na pˇr´ıkladech. ˇ aˇr drˇz´ı v ruce pˇrehledn´ Cten´ y souhrn algoritm˚ u aritmetick´ ych operac´ı od tˇech nejstarˇs´ıch aˇz po dneˇsn´ı. Vˇeˇr´ıme, ˇze by tato práce mohla b´ yt uˇziteˇcnou v knihovnˇe stˇredoˇskolsk´ ych profesor˚ u matematiky, kteˇr´ı by mohli nˇekteré z algoritm˚ u vysvˇetlovat v rámci matematick´ ych semináˇr˚ u. Nen´ı n´ am zn´ amo, ˇ ze by byl nˇ ekde v literatuˇ re ˇ ci na internetu podobnˇ e bohat´ y souhrn popsan´ ych a ilustrovan´ ych algoritm˚ u k dispozici, v pˇ rehledn´ em shrnut´ı tedy spoˇ c´ıv´ a hlavn´ı v´ yznam t´ eto pr´ ace. ˇ má jeˇstˇe dva dalˇs´ı v´ Tato SOC yznamné v´ ystupy. • Jedn´ım je www stránka http://bimbo.fjfi.cvut.cz/∼soc se srozumiteln´ ym popisem algoritm˚ u v mnoha pˇr´ıpadech doplnˇen´ ym programem, kter´ y algoritmus ilustruje. ˇ Skarda: ˇ • Druh´ ym je ˇclánek L’. Balková, C. Násob´ıme chytˇre?, kter´ y je pˇrijat k publikaci v Pokroc´ıch matematiky, fyziky a astronomie a v nˇemˇz je popsána ˇcást algoritm˚ u násoben´ı.

52

Literatura [1] J. Beˇcváˇr, M. Beˇcváˇrová, H. Vymazalová, Matematika ve starovˇeku: Egypt a Mezopotámie, 1.vydán´ı, Prometheus, 2003 [2] A. P. Juˇskeviˇc, Dˇejiny matematiky ve stˇredovˇeku, 1.vydán´ı, Academia, Praha 1978. [3] A. A. Karacuba, The Complexity of Computation (v angliˇctinˇe), Proc. Steklov Inst. Math. 211 (1995), 169–183 [4] A. A. Karacuba, Yu. Ofman, Multiplication of Many-Digital Numbers by Automatic Computers (v ruˇstinˇe), Proceedings of the USSR Academy of Sciences 145 (1962), 293–294 [5] A. Kolman, Dˇejiny matematiky ve starovˇeku, 1.vydán´ı, Academia, 1969 [6] D. E. Knuth, The Art of Computer Programming volume 2: Seminumerical Algorithms, 3rd ed, Addison-Wesley Boston etc., 1998 [7] F. Kuˇrina, Matematika a kalkuly, Matematika - fyzika - informatika 18 (2008/2009), 1–20 [8] M. Mareˇs, Pˇr´ıbˇehy matematiky, Pistorius & Olˇsanská, Pˇr´ıbram, 2008 ˇ Porubsk´ [9] S. y, Ako rýchlo vieme a moˇzeme násobit’, sborn´ık 30. mezinárodn´ı konference Historie matematiky, editoˇri J. Beˇcváˇr, M. Beˇcváˇrová, matfyzpress, 2009 [10] I. S´ ykorová, Násoben´ı ve stˇredovˇeké Indii, sborn´ık 29. mezinárodn´ı konference Historie matematiky, editoˇri J. Beˇcváˇr, M. Beˇcváˇrová, Matfyzpress, 2008. [11] H. Vymazalová, Staroegyptská matematika, Dˇejiny matematiky, svazek 31, Praha 2006. [12] Biografie ˇcesk´ ych matematik˚ u, inserv.math.muni.cz/biografie [13] http://cs.wikipedia.org/wiki/Augustin Louis Cauchy, 3.1.2012 [14] http://webhome.idirect.com/ totton/abacus/pages.htm#Division1, 15.2.2012 [15] http://webhome.idirect.com/ totton/soroban/Div Rev, 25.11.2011 [16] http://en.wikipedia.org/wiki/Soroban, 5.11.2011 [17] http://cs.wikipedia.org/wiki/Anton´ın Svoboda, 2.3.2012 [18] http://www.youtube.com/watch?v=bEvwSlA88fU&feature=related, 5.11.2011

53

Aritmetika včera a dnes Arithmetics: Past and Present

Recommend Documents