Самый быстрый алгоритм умножения

Продолжайте изучать ►
Начните бесплатно в течение 30 дней — и первые 200 человек получат скидку 20% на годовую премиум-подписку! Как умножить два огромных числа? Мы все в школе изучаем подход, требующий n^2 умножений на однозначные числа. Первым усовершенствованием стал алгоритм Карацубы, который использует подход «разделяй и властвуй» и немного алгебраических выкладок для асимптотического сокращения умножения 4 до 3 (в случае 2x2) и, в более общем случае, примерно до n^1,58 умножений. Для компьютера с 32-битным аппаратным умножителем этот подход можно итеративно применять до тех пор, пока числа не окажутся в пределах размера умножителя. Алгоритм Тума-Кука является обобщением алгоритма Карацубы и полезен в различных криптографических приложениях. Однако реальный прорыв произошёл с появлением алгоритма Шёнхаге-Штрассена, который использует дискретные быстрые преобразования Фурье для достижения сложности O(n log n log log n), что используется в таких приложениях, как поиск простого числа Мерсенна в Интернете. Теоретически наилучший результат — это результат Харви и Хувена, которые достигли O(n log n), хотя этот метод становится эффективнее только для непрактично больших чисел. 0:00 Обзор обычного умножения 1:42 Алгоритм Карацубы для 2x2 3:32 Пример Карацубы 4:34 Алгоритм Карацубы для больших чисел 5:45 Сложность алгоритма Карацубы для размера 2^k 7:09 Архитектура компьютера и аппаратные умножители 8:26 Новые алгоритмы (Шёнхаге-Штрассена, Харви и Хувена) 12:46 Brilliant.org/TreforBazett Посмотрите мою линейку MATH MERCH, созданную совместно с Beautiful Equations ► ПЛЕЙЛИСТЫ КУРСА: ►ДИСКРЕТНАЯ МАТЕМАТИКА:    • Discrete Math (Full Course: Sets, Logic, P...   ►ЛИНЕЙНАЯ АЛГЕБРА:    • Linear Algebra (Full Course)   ►ИССЛЕДОВАНИЕ I:    • Calculus I (Limits, Derivative, Integrals)...   ►ИССЛЕДОВАНИЕ II:    • Calculus II (Integration Methods, Series, ...   ►МНОГОПАРАМЕННОЕ ИСЧИСЛЕНИЕ (Расчет III):    • Calculus III: Multivariable Calculus (Vect...   ►ВЕКТОРНОЕ ИСЧИСЛЕНИЕ (Расчет IV)    • Calculus IV: Vector Calculus (Line Integra...   ►ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ:    • Ordinary Differential Equations (ODEs)   ►ПРЕОБРАЗОВАНИЕ ЛАПЛАСА:    • Laplace Transforms and Solving ODEs   ►ТЕОРИЯ ИГР:    • Game Theory   ДРУГИЕ ПЛЕЙЛИСТЫ: ► Изучение математики Серия    • 5 Tips To Make Math Practice Problems Actu...   ►Серия «Классная математика»:    • Cool Math Series   СТАТЬ УЧАСТНИКОМ: ►Присоединяйтесь:    / @drtrefor   МАТЕМАТИЧЕСКИЕ КНИГИ, КОТОРЫЕ Я ЛЮБЛЮ (партнёрская ссылка): ►
СОЦИАЛЬНЫЕ СЕТЯ: ►Twitter (по математике):   / treforbazett   ►Instagram (по фотографии):   / treforphotography