Combinatorical and Algebraic Structures Seminar

Session details

Date: 6.10.2009
Speaker: Ľubomíra Balková, FJFI, České vysoké učení technické v Praze
Title: Násobíme chytře?
Abstract: Máme-li úkol vynásobit dvě přirozená čísla a k dispozici tužku a papír, většina z nás použije algoritmus, který jsme se učili už na základní škole. Přesto ale algoritmů pro násobení existuje velké množství. Na semináři si ukážeme jak algoritmy pro násobení na papíře či z hlavy: přehledné indické násobení, egyptské a ruské násobení založené na binárním rozvoji násobitele, Cauchyovo komplementární násobení využívající zápis čísel pomocí záporných cifer, tak i algoritmy, které zefektivnily počítačové násobení a jeho časovou náročnost snížily z $\mathcal{O}(n^2)$ až na $\mathcal{O}(n(\log n)(\log\log n))$. Tuto moderní éru v násobení velkých čísel odstartovaly zejména Karacubův algoritmus a modulární násobení.

Return to index.