Zdravim, mam za ulohu naprogramovat jeden z algoritmov, ktory riesi problem diskretneho algoritmu. Samotny algoritmus uz viacmenej mam naprorgramovany, no potrebujem implementovat este rychle nasobenie, a neviem uplne presne, aky algoritmus mam nato pouzit. V zadani sa pise len, ze je potrebne naimplementovat rychle nasobenie v grupe, nic viac. Neviete mi poradit, o co by mohlo ist? Dakujem.

Ahoj, "rychlim nasobenim" sa vacsinou mysli Karatsubov algoritmus. Pogoogli

Ak máš náhodou problém s angličtinou, tak Karatsubovi je venovaná celá kapitola v knihe Prúvodce labyrintem algoritmú. Tá kniha je naozaj super

Ahoj, dakujem za odpoved. Mrknem na to. Chcem sa vsak spytat, ma to nejak limit cifier, kedy to uz prestava byt ucinne? Mam cisla taketo velke 316912650057057350374175801441, tak ci to pomoze aj mne.

No to cislo, ktore si sem dal ma 30 cifier. Staci ti obycajne, skolske nasobenie "pod seba".

Long story: Skolsky algoritmus na nasobenie ma kvadraticku casovu zlozitost O(n^2) kde n je pocet cifier. Ten Karatsubov algoritmus ma lepsiu casovu zlozitost, konkretne O(n^log_2(3)) ~ O(n^1.58). Pri tak malom pocte cifier ako je 30 ale bude mozno karatsubov alg. v praxi pomalsi, pretoze je okolo neho vacsia rezia ako pri obycajnom nasobeni. Ze je naozaj rychlejsi preto mozno vidiet az od vacsich vstupov. Ak ta to zaujima viac, pozri si nieco o casovej zlozitosti.

Ahoj, dakujem za odpoved. Uvedene cislo este zacinam mocnit pomocou metody square and multiply. To cislo, ktore som uviedol, sa v konecnom dosledku prenasobi samo so sebou 90x. Pri pusteni toho algoritmu sa mi to po prenasobeni 15x zasekne resp. trva uz dlho. Takze nejak to urychlit musim.

Ano, 316912650057057350374175801441 ^ 90 ma 2700 cifier, takze tam uz by si rozdiel vidiet mal

Ak ti ide moc o vykon, mozes si zmerat na tvojich implementaciach pokial je este skolsky algoritmus rychlejsi ako karatsuba a kedy uz je karatsuba rychlejsi. Potom mozes z toho spravit hybridni algoritmus, ktory pre male vstupy pouzije skolsky alg. a pre vacsie karatsubu.