Самый быстрый способ умножения, который можно повторить на бумаге. Метод Карацубы

Приветствую Вас, уважаемые Читатели! Продолжаем тему занимательной арифметики. В прошлых материалах я рассказывал про древнеиндийский и японский методы умножения. Рассмотренные способы умножения пришли к нам из древности и представляли собой всего лишь взгляд со стороны на привычное нам умножение столбиком.

Советский математик Анатолий Алексеевич Карацуба. В 23-летнем возрасте опроверг идею самого Колмогорова, который утверждал, что сделать умножение быстрее не получится. Источник: http://www.mathnet.ru/ConfLogos/936/_dsc2213_600.jpg

Метод Карацубы же более тридцати дет оставался самым алгоритмически быстрым способом умножения больших чисел. Вместе с тем, он очень легко воспроизводится на бумаге (в отличие от самых современных алгоритмов). Давайте посмотрим! Поехали!

Умножим для примера два двузначных числа

Например, 34 на 45 (три слайда):

Если использовать умножение столбиком, то получим необходимость 4-х операций умножения

Почему я так акцентирую внимание на умножении? А потому, что в схемотехнике - это подлинная боль. Умножителей требуется много и часто, а ресурсы ой как ограничены: здесь метод Карацубы раскрывается во всех красках.

Например, вот пример реализации метода Карацубы на ПЛИС, в результате которого удается выжать все соки из обычной китайской железки за 2000 рублей, а не переплачивать 300 тысяч за оригинальные комплекты.

КАНАЛ "IT. КАК ЭТО РАБОТАЕТ" - много классной информации: что общего у чайки и GPS, почему переменный ток выиграл у постоянного и многое другое!