{"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\/pl\/uk-uamatematiki-dosi-ne-znajut-najshvidshogo-sposobu-mnozhennja\/","title":{"rendered":"Zagadka matematyczna, kt\u00f3ra wci\u0105\u017c jest nierozwi\u0105zana"},"content":{"rendered":"

W szkole dzieci ucz\u0105 si\u0119 tabliczki mno\u017cenia. Pami\u0119taj\u0105 to na pami\u0119\u0107. Powodzenia z liczbami trzycyfrowymi! Tutaj w gr\u0119 wchodz\u0105 algorytmy. Ustawiamy liczby w kolumnie. Mno\u017cysz linia po linii. Przez tysi\u0105ce lat wierzyli\u015bmy, \u017ce nie ma nic lepszego od tego. To jest powolne. Strasznie wolno przy du\u017cych ilo\u015bciach danych. Ale w 1960 roku 23-letni facet zmieni\u0142 wszystko. Tajemnica szybko\u015bci mno\u017cenia pozostaje wci\u0105\u017c otwarta. <\/p>\n

Dlaczego to jest wa\u017cne?<\/h3>\n

Mno\u017cenie to nie tylko zadanie szkolne. Dzi\u0119ki niemu ca\u0142y Internet dzia\u0142a. Szyfrowanie, sztuczna inteligencja, przetwarzanie d\u017awi\u0119ku. Wszystko to opiera si\u0119 na mno\u017ceniu. Intensywne rozmna\u017canie. Kiedy musisz pomno\u017cy\u0107 ogromne liczby miliony razy na sekund\u0119, ka\u017cdy krok ma znaczenie. Nawet niewielki wzrost wydajno\u015bci pozwala zaoszcz\u0119dzi\u0107 miliardy. <\/p>\n

Sp\u00f3jrz na metod\u0119 szkoln\u0105. Dwie cyfry oznaczaj\u0105 cztery mno\u017cenia liczb jednocyfrowych. Trzy stopnie? Dziewi\u0119\u0107. Skaluje si\u0119 kwadratowo. Podw\u00f3j d\u0142ugo\u015b\u0107 liczby, a praca wzro\u015bnie czterokrotnie. Podw\u00f3j to jeszcze raz – praca wzro\u015bnie 16 razy. Informatycy nie licz\u0105 sekund. \u017belazo jest ju\u017c coraz szybsze. Licz\u0105 kroki. Nazywamy to notacj\u0105 Wielkiego O. Metoda szkolna to O(n\u00b2). Kwadratowy. Je\u015bli d\u0142ugo\u015b\u0107 liczby wzro\u015bnie 1000 razy, ilo\u015b\u0107 pracy eksploduje milion razy. <\/p>\n

\n

Obci\u0105\u017cenie wzrasta proporcjonalnie do kwadratu liczby cyfr. <\/p>\n<\/blockquote>\n

Od czas\u00f3w staro\u017cytnych matematyczni geniusze uwa\u017cali t\u0119 kwadratow\u0105 granic\u0119 za prawo natury. Andriej Ko\u0142mogorow, radziecka legenda, umie\u015bci\u0142 swoje nazwisko na wyk\u0142adzie w 1960 roku. Powiedzia\u0142 studentom MSU: \u201eTo wymaga O(n\u00b2)\u201d. By\u0142o to za\u0142o\u017cenie formalne. Wyzwanie. Poczekaj a\u017c kto\u015b to potwierdzi lub obali. <\/p>\n

Min\u0105\u0142 dopiero tydzie\u0144. Na widowni siedzia\u0142 Anatolij Karatsuba. Mia\u0142 23 lata. Wr\u00f3ci\u0142 z dowodem na to, \u017ce Ko\u0142mogorow si\u0119 myli\u0142. Profesor by\u0142 zszokowany. Ko\u0142mogorow dos\u0142ownie sam napisa\u0142 artyku\u0142 dla presti\u017cowego magazynu, ale jako autora poda\u0142 Karatsub\u0119. M\u0142ody cz\u0142owiek dowiedzia\u0142 si\u0119 o tym dopiero, gdy przedruki dotar\u0142y poczt\u0105. <\/p>\n

Sztuczka<\/h3>\n

Karatsuba zrozumia\u0142 prost\u0105, ale g\u0142\u0119bok\u0105 rzecz. Mno\u017cenie to kosztowna operacja. Fa\u0142dy s\u0105 tanie. Dlaczego ich nie zamieni\u0107? <\/p>\n

We\u017amy 12\u00d734.
\nRozbij je.
\n12 to 10 + 2.
\n34 to 30 + 4.<\/p>\n

Tradycyjnie wykonujesz cztery mno\u017cenia:
\n1×3
\n1×4
\n2×3
\n2×4<\/p>\n

Karatsuba znalaz\u0142 spos\u00f3b, aby to zrobi\u0107 w trzech mno\u017ceniach.
\nOblicz pierwsz\u0105 cz\u0119\u015b\u0107: 1×3 = 3.
\nOblicz ostatni\u0105 cz\u0119\u015b\u0107: 2×4 = 8.<\/p>\n

Teraz \u015brodek. Zwykle zrobi\u0142by\u015b (1×4) + (2×3). Dwa mno\u017cenia. Zamiast tego dodaj pierwsze liczby: 1+2=3. Dodaj ostatnie: 3+4=7. Pomn\u00f3\u017c te kwoty: 3\u00d77=21. Odejmij ju\u017c znane cz\u0119\u015bci. 21 – 3 – 8 = 10.
\nVoila. Masz \u015bredni termin na jedno dodatkowe mno\u017cenie. <\/p>\n

Czy to si\u0119 op\u0142aca?
\nDla ma\u0142ych liczb – nie. Koszty dzielenia i dodawania kosztuj\u0105 wi\u0119cej.
\nAle dla 1234\u00d75678? Podziel na p\u00f3\u0142. Rekurencja. Oddziel te po\u0142\u00f3wki. Zr\u00f3b to jeszcze raz. Oszcz\u0119dno\u015bci sumuj\u0105 si\u0119.
\nZ\u0142o\u017cono\u015b\u0107 algorytmu spada do oko\u0142o O(n^1,585).
\nLiczby tysi\u0105ccyfrowe wymaga\u0142y kiedy\u015b miliona mno\u017ce\u0144 liczb jednocyfrowych. Teraz potrzebujesz mniej ni\u017c 57 000 krok\u00f3w. Ogromna r\u00f3\u017cnica. <\/p>\n

To nie jest tylko teoria. Python to ma.
\nPython u\u017cywa standardowej matematyki szkolnej dla ma\u0142ych danych wej\u015bciowych. G\u0142adki.
\nAle gdy osi\u0105gniesz oko\u0142o 63 miejsca po przecinku (w zale\u017cno\u015bci od siatki cyfr maszyny), Python prze\u0142\u0105cza prze\u0142\u0105cznik. W\u0142\u0105cza si\u0119 Karatsuba. Nie widzisz tego. Ale on tam jest. Obs\u0142uguje Twoje szyfrowanie. <\/p>\n

Algorytmy galaktyczne<\/h3>\n

Wy\u015bcig trwa\u0142 przez dziesi\u0119ciolecia. Czy mo\u017cna jecha\u0107 jeszcze szybciej?
\nRok 2019 przyni\u00f3s\u0142 now\u0105 niespodziank\u0119. David Harvey i Joris van der Hoeven opublikowali algorytm, kt\u00f3ry pozostawia Karatsub\u0119 daleko w tyle.
\nO(n log n). <\/p>\n

Przeczytaj to jeszcze raz.
\nLogarytmy rosn\u0105 niewiarygodnie wolno.
\nn log n jest tylko nieznacznie wi\u0119ksze ni\u017c n.
\nZasadniczo mno\u017cenie dw\u00f3ch ogromnych liczb zajmuje teraz mniej wi\u0119cej tyle samo czasu, co czytanie samych liczb. <\/p>\n

To osza\u0142amiaj\u0105ce. Wydaje si\u0119, \u017ce teoretyczny limit zosta\u0142 ju\u017c osi\u0105gni\u0119ty.
\nA mo\u017ce nie.
\nOto haczyk.
\nNie dzia\u0142a to w przypadku liczb, kt\u00f3re nas interesuj\u0105. <\/p>\n

Algorytm Harveya i van der Hoeven\u00f3w staje si\u0119 szybszy ni\u017c algorytm Karatsuby tylko wtedy, gdy liczby staj\u0105 si\u0119 bardzo<\/em> du\u017ce. Nie \u201edu\u017cy jak numer karty kredytowej\u201d. Galaktycznie du\u017cy.
\nW informatyce istnieje na to okre\u015blenie: algorytm galaktyczny.
\nNiez\u0142a teoria. Zero praktycznych korzy\u015bci. Wymagane liczby s\u0105 wi\u0119ksze ni\u017c suma wszystkich transakcji cyfrowych w historii ludzko\u015bci. <\/p>\n

Utkn\u0119li\u015bmy po\u015brodku.
\nW wi\u0119kszo\u015bci naszych codziennych oblicze\u0144 u\u017cywamy trik\u00f3w z lat 60.
\nNosimy kostiumy XXI wieku ponad matematyk\u0105 XX wieku. <\/p>\n

Czy kiedykolwiek u\u017cywamy O(n log n) w prawdziwym \u015bwiecie?
\nBy\u0107 mo\u017ce, gdy przetwarzamy dane, ustalamy wielko\u015b\u0107 galaktyk.
\nDo tego czasu czekamy.
\nNast\u0119pna sztuczka.
\nAlbo lepszy sprz\u0119t, kt\u00f3ry ukryje nasze lenistwo. <\/p>\n

Odpowied\u017a mo\u017ce nadal by\u0107 kwadratowa.
\nMo\u017ce mie\u0107 charakter liniowy.
\nJeszcze nie wiemy.<\/p>\n","protected":false},"excerpt":{"rendered":"

W szkole dzieci ucz\u0105 si\u0119 tabliczki mno\u017cenia. Pami\u0119taj\u0105 to na pami\u0119\u0107. Powodzenia z liczbami trzycyfrowymi! Tutaj w gr\u0119 wchodz\u0105 algorytmy. Ustawiamy liczby w kolumnie. Mno\u017cysz linia po linii. Przez tysi\u0105ce lat wierzyli\u015bmy, \u017ce nie ma nic lepszego od tego. To jest powolne. Strasznie wolno przy du\u017cych ilo\u015bciach danych. Ale w 1960 roku 23-letni facet zmieni\u0142 […]<\/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\/pl\/wp-json\/wp\/v2\/posts\/7910"}],"collection":[{"href":"https:\/\/www.schooler.org.ua\/pl\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.schooler.org.ua\/pl\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/pl\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/pl\/wp-json\/wp\/v2\/comments?post=7910"}],"version-history":[{"count":0,"href":"https:\/\/www.schooler.org.ua\/pl\/wp-json\/wp\/v2\/posts\/7910\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/pl\/wp-json\/wp\/v2\/media\/7909"}],"wp:attachment":[{"href":"https:\/\/www.schooler.org.ua\/pl\/wp-json\/wp\/v2\/media?parent=7910"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.schooler.org.ua\/pl\/wp-json\/wp\/v2\/categories?post=7910"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.schooler.org.ua\/pl\/wp-json\/wp\/v2\/tags?post=7910"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}