{"id":7910,"date":"2026-07-15T02:28:58","date_gmt":"2026-07-14T23:28:58","guid":{"rendered":"https:\/\/www.schooler.org.ua\/uk-uamatematiki-dosi-ne-znajut-najshvidshogo-sposobu-mnozhennja\/"},"modified":"2026-07-15T02:28:58","modified_gmt":"2026-07-14T23:28:58","slug":"uk-uamatematiki-dosi-ne-znajut-najshvidshogo-sposobu-mnozhennja","status":"publish","type":"post","link":"https:\/\/www.schooler.org.ua\/cs\/uk-uamatematiki-dosi-ne-znajut-najshvidshogo-sposobu-mnozhennja\/","title":{"rendered":"Matematick\u00e1 h\u00e1danka, kter\u00e1 st\u00e1le nen\u00ed vy\u0159e\u0161ena"},"content":{"rendered":"

Ve \u0161kole se d\u011bti u\u010d\u00ed n\u00e1sobilku. Pamatuj\u00ed si to zpam\u011bti. Hodn\u011b \u0161t\u011bst\u00ed s trojcifern\u00fdmi \u010d\u00edsly! Zde vstupuj\u00ed do hry algoritmy. \u010c\u00edsla se\u0159ad\u00edte do sloupce. N\u00e1sob\u00edte \u0159\u00e1dek po \u0159\u00e1dku. Po tis\u00edce let jsme v\u011b\u0159ili, \u017ee nic nem\u016f\u017ee b\u00fdt lep\u0161\u00ed ne\u017e toto. Je to pomal\u00e9. Stra\u0161n\u011b pomal\u00e9 pro velk\u00e9 mno\u017estv\u00ed dat. V roce 1960 ale 23let\u00fd chlap v\u0161e zm\u011bnil. Z\u00e1hada rychlosti mno\u017een\u00ed z\u016fst\u00e1v\u00e1 st\u00e1le otev\u0159en\u00e1. <\/p>\n

Pro\u010d je to d\u016fle\u017eit\u00e9?<\/h3>\n

N\u00e1soben\u00ed nen\u00ed jen \u0161koln\u00ed \u00fakol. D\u00edky tomu funguje cel\u00fd internet. \u0160ifrov\u00e1n\u00ed, um\u011bl\u00e1 inteligence, zpracov\u00e1n\u00ed zvuku. To v\u0161e z\u00e1vis\u00ed na n\u00e1soben\u00ed. Intenzivn\u00ed mno\u017een\u00ed. Kdy\u017e mus\u00edte n\u00e1sobit obrovsk\u00e1 \u010d\u00edsla milionkr\u00e1t za sekundu, z\u00e1le\u017e\u00ed na ka\u017ed\u00e9m kroku. I mal\u00e9 zv\u00fd\u0161en\u00ed efektivity u\u0161et\u0159\u00ed miliardy. <\/p>\n

Pod\u00edvejte se na \u0161koln\u00ed metodu. Dv\u011b \u010d\u00edslice znamenaj\u00ed \u010dty\u0159i n\u00e1soben\u00ed jednocifern\u00fdch \u010d\u00edsel. T\u0159i stupn\u011b? Dev\u011bt. M\u011b\u0159\u00ed se kvadraticky. Zdvojn\u00e1sobte d\u00e9lku \u010d\u00edsla a pr\u00e1ce se z\u010dty\u0159n\u00e1sob\u00ed. Znovu to zdvojn\u00e1sobte – pr\u00e1ce se zv\u00fd\u0161\u00ed 16kr\u00e1t. Po\u010d\u00edta\u010dov\u00ed v\u011bdci nepo\u010d\u00edtaj\u00ed vte\u0159iny. \u017delezo je ji\u017e rychlej\u0161\u00ed. Po\u010d\u00edtaj\u00ed kroky. Tomu \u0159\u00edk\u00e1me notace Big O. \u0160koln\u00ed metoda je O(n\u00b2). Kvadratick\u00fd. Pokud se d\u00e9lka \u010d\u00edsla zv\u00fd\u0161\u00ed o faktor 1000, mno\u017estv\u00ed pr\u00e1ce exploduje milionkr\u00e1t. <\/p>\n

\n

Z\u00e1t\u011b\u017e se zvy\u0161uje \u00fam\u011brn\u011b druh\u00e9 mocnin\u011b po\u010dtu \u010d\u00edslic. <\/p>\n<\/blockquote>\n

Od starov\u011bku pova\u017eovali matematick\u00ed g\u00e9niov\u00e9 tuto kvadratickou hranici za z\u00e1kon p\u0159\u00edrody. Andrei Kolmogorov, sov\u011btsk\u00e1 legenda, na to uvedl sv\u00e9 jm\u00e9no na p\u0159edn\u00e1\u0161ce v roce 1960. Student\u016fm MSU \u0159ekl: \u201eTo trv\u00e1 O(n\u00b2). To byl form\u00e1ln\u00ed p\u0159edpoklad. V\u00fdzva. Po\u010dkejte, a\u017e to n\u011bkdo potvrd\u00ed nebo vyvr\u00e1t\u00ed.<\/p>\n

Uplynul jen t\u00fdden. Anatoly Karatsuba sed\u011bl v publiku. Bylo mu 23 let. Vr\u00e1til se s d\u016fkazem, \u017ee se Kolmogorov m\u00fdlil. Profesor byl \u0161okov\u00e1n. Kolmogorov doslova s\u00e1m napsal \u010dl\u00e1nek pro presti\u017en\u00ed \u010dasopis, ale jako autora uvedl jm\u00e9no Karatsuba. Mlad\u00edk se o tom dozv\u011bd\u011bl, a\u017e kdy\u017e dotisky dorazily po\u0161tou.<\/p>\n

Trik<\/h3>\n

Karatsuba pochopil jednoduchou, ale hlubokou v\u011bc. N\u00e1soben\u00ed jsou drah\u00e9 operace. Z\u00e1hyby jsou levn\u00e9. Pro\u010d je nevym\u011bnit?<\/p>\n

Vezm\u011bme 12 \u00d7 34.
\nRozbijte je.
\n12 je 10 + 2.
\n34 je 30 + 4.<\/p>\n

Tradi\u010dn\u011b d\u011bl\u00e1te \u010dty\u0159i n\u00e1soben\u00ed:
\n1×3
\n1×4
\n2×3
\n2×4<\/p>\n

Karatsuba na\u0161el zp\u016fsob, jak toho dos\u00e1hnout ve t\u0159ech n\u00e1sobc\u00edch.
\nVypo\u010d\u00edtejte prvn\u00ed \u010d\u00e1st: 1×3 = 3.
\nVypo\u010d\u00edtejte posledn\u00ed \u010d\u00e1st: 2×4 = 8.<\/p>\n

Nyn\u00ed st\u0159ed. Norm\u00e1ln\u011b byste ud\u011blali (1×4) + (2×3). Dv\u011b n\u00e1soben\u00ed. M\u00edsto toho se\u010dt\u011bte prvn\u00ed \u010d\u00edsla: 1+2=3. P\u0159idejte posledn\u00ed: 3+4=7. Vyn\u00e1sobte tyto \u010d\u00e1stky: 3\u00d77=21. Ode\u010dt\u011bte ji\u017e zn\u00e1m\u00e9 \u010d\u00e1sti. 21 – 3 – 8 = 10.
\nVoila. M\u00e1te st\u0159edn\u00ed \u010dlen za jedno n\u00e1soben\u00ed nav\u00edc. <\/p>\n

Vyplat\u00ed se to?
\nPro mal\u00e1 \u010d\u00edsla – ne. Re\u017eijn\u00ed n\u00e1klady na d\u011blen\u00ed a p\u0159id\u00e1v\u00e1n\u00ed v\u00e1s stoj\u00ed v\u00edce.
\nAle pro 1234\u00d75678? Rozd\u011blit na polovinu. Rekurze. Odd\u011blte tyto poloviny. Ud\u011blej to znovu. \u00daspory se s\u010d\u00edtaj\u00ed.
\nSlo\u017eitost algoritmu klesne p\u0159ibli\u017en\u011b na O(n^1,585).
\nD\u0159\u00edve tis\u00edcim\u00edstn\u00e1 \u010d\u00edsla vy\u017eadovala milion n\u00e1soben\u00ed jednocifern\u00fdch \u010d\u00edsel. Nyn\u00ed pot\u0159ebujete m\u00e9n\u011b ne\u017e 57 000 krok\u016f. Obrovsk\u00fd rozd\u00edl. <\/p>\n

To nen\u00ed jen teorie. Python to m\u00e1.
\nPython pou\u017e\u00edv\u00e1 standardn\u00ed st\u0159edo\u0161kolskou matematiku pro mal\u00e9 vstupy. Hladk\u00fd.
\nAle jakmile dos\u00e1hnete asi 63 desetinn\u00fdch m\u00edst (v z\u00e1vislosti na m\u0159\u00ed\u017ece \u010d\u00edslic stroje), Python p\u0159epne p\u0159ep\u00edna\u010d. Karatsuba se zapne. Ty to nevid\u00ed\u0161. Ale je tam. Zvl\u00e1d\u00e1 va\u0161e \u0161ifrov\u00e1n\u00ed. <\/p>\n

Galaktick\u00e9 algoritmy<\/h3>\n

Z\u00e1vod pokra\u010doval po cel\u00e1 desetilet\u00ed. Je mo\u017en\u00e9 jet je\u0161t\u011b rychleji?
\nRok 2019 p\u0159inesl nov\u00e9 p\u0159ekvapen\u00ed. David Harvey a Joris van der Hoeven publikovali algoritmus, kter\u00fd nech\u00e1v\u00e1 Karatsubu daleko za sebou.
\nO(n log n). <\/p>\n

P\u0159e\u010dt\u011bte si to znovu.
\nLogaritmy rostou neuv\u011b\u0159iteln\u011b pomalu.
\nn log n je jen o m\u00e1lo v\u011bt\u0161\u00ed ne\u017e n.
\nVyn\u00e1soben\u00ed dvou obrovsk\u00fdch \u010d\u00edsel nyn\u00ed v podstat\u011b trv\u00e1 p\u0159ibli\u017en\u011b stejn\u011b dlouho jako \u010dten\u00ed samotn\u00fdch \u010d\u00edsel. <\/p>\n

Je to \u00fa\u017easn\u00e9. Zd\u00e1 se, \u017ee teoretick\u00e9 hranice ji\u017e bylo dosa\u017eeno.
\nNebo mo\u017en\u00e1 ne.
\nTady je h\u00e1\u010dek.
\nU \u010d\u00edsel, kter\u00e1 n\u00e1s zaj\u00edmaj\u00ed, to nefunguje. <\/p>\n

Algoritmus Harveyho a van der Hoevena je rychlej\u0161\u00ed ne\u017e algoritmus Karatsuba pouze tehdy, kdy\u017e jsou \u010d\u00edsla velmi<\/em> velk\u00e1. Ne \u201evelk\u00e9 jako \u010d\u00edslo kreditn\u00ed karty\u201c. Galakticky velk\u00fd.
\nV informatice pro to existuje term\u00edn: galaktick\u00fd algoritmus.
\nP\u011bkn\u00e1 teorie. Praktick\u00fd p\u0159\u00ednos nulov\u00fd. Po\u017eadovan\u00e1 \u010d\u00edsla jsou v\u011bt\u0161\u00ed ne\u017e sou\u010det v\u0161ech digit\u00e1ln\u00edch transakc\u00ed v historii lidstva. <\/p>\n

Uv\u00edzli jsme uprost\u0159ed.
\nPro v\u011bt\u0161inu na\u0161ich ka\u017edodenn\u00edch v\u00fdpo\u010dt\u016f pou\u017e\u00edv\u00e1me triky z 60. let.
\nNos\u00edme kost\u00fdmy 21. stolet\u00ed p\u0159es matematiku 20. stolet\u00ed. <\/p>\n

Pou\u017e\u00edv\u00e1me n\u011bkdy O(n log n) v re\u00e1ln\u00e9m sv\u011bt\u011b?
\nMo\u017en\u00e1, \u017ee kdy\u017e zpracov\u00e1v\u00e1me data, nastav\u00ed velikost galaxi\u00ed.
\nDo t\u00e9 doby \u010dek\u00e1me.
\nDal\u0161\u00ed trik.
\nNebo lep\u0161\u00ed vybaven\u00ed, kter\u00e9 skryje na\u0161i lenost. <\/p>\n

Odpov\u011b\u010f m\u016f\u017ee b\u00fdt st\u00e1le kvadratick\u00e1.
\nM\u016f\u017ee b\u00fdt line\u00e1rn\u00ed.
\nTo je\u0161t\u011b nev\u00edme.<\/p>\n","protected":false},"excerpt":{"rendered":"

Ve \u0161kole se d\u011bti u\u010d\u00ed n\u00e1sobilku. Pamatuj\u00ed si to zpam\u011bti. Hodn\u011b \u0161t\u011bst\u00ed s trojcifern\u00fdmi \u010d\u00edsly! Zde vstupuj\u00ed do hry algoritmy. \u010c\u00edsla se\u0159ad\u00edte do sloupce. N\u00e1sob\u00edte \u0159\u00e1dek po \u0159\u00e1dku. Po tis\u00edce let jsme v\u011b\u0159ili, \u017ee nic nem\u016f\u017ee b\u00fdt lep\u0161\u00ed ne\u017e toto. Je to pomal\u00e9. Stra\u0161n\u011b pomal\u00e9 pro velk\u00e9 mno\u017estv\u00ed dat. V roce 1960 ale 23let\u00fd chlap […]<\/p>\n","protected":false},"author":1,"featured_media":7909,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"tdm_status":"","tdm_grid_status":""},"categories":[1],"tags":[],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.schooler.org.ua\/cs\/wp-json\/wp\/v2\/posts\/7910"}],"collection":[{"href":"https:\/\/www.schooler.org.ua\/cs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.schooler.org.ua\/cs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/cs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/cs\/wp-json\/wp\/v2\/comments?post=7910"}],"version-history":[{"count":0,"href":"https:\/\/www.schooler.org.ua\/cs\/wp-json\/wp\/v2\/posts\/7910\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/cs\/wp-json\/wp\/v2\/media\/7909"}],"wp:attachment":[{"href":"https:\/\/www.schooler.org.ua\/cs\/wp-json\/wp\/v2\/media?parent=7910"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.schooler.org.ua\/cs\/wp-json\/wp\/v2\/categories?post=7910"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.schooler.org.ua\/cs\/wp-json\/wp\/v2\/tags?post=7910"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}