Приветствую Вас, уважаемые Читатели! Продолжаем тему занимательной арифметики. В прошлых материалах я рассказывал про древнеиндийский и японский методы умножения. Рассмотренные способы умножения пришли к нам из древности и представляли собой всего лишь взгляд со стороны на привычное нам умножение столбиком.
Советский математик Анатолий Алексеевич Карацуба. В 23-летнем возрасте опроверг идею самого Колмогорова, который утверждал, что сделать умножение быстрее не получится. Источник: http://www.mathnet.ru/ConfLogos/936/_dsc2213_600.jpg
Метод Карацубы же более тридцати дет оставался самым алгоритмически быстрым способом умножения больших чисел. Вместе с тем, он очень легко воспроизводится на бумаге (в отличие от самых современных алгоритмов). Давайте посмотрим! Поехали!
Умножим для примера два двузначных числа
Например, 34 на 45 (три слайда):
Если использовать умножение столбиком, то получим необходимость 4-х операций умножения
Почему я так акцентирую внимание на умножении? А потому, что в схемотехнике — это подлинная боль. Умножителей требуется много и часто, а ресурсы ой как ограничены: здесь метод Карацубы раскрывается во всех красках.
Например, вот пример реализации метода Карацубы на ПЛИС, в результате которого удается выжать все соки из обычной китайской железки за 2000 рублей, а не переплачивать 300 тысяч за оригинальные комплекты.
КАНАЛ "IT. КАК ЭТО РАБОТАЕТ" — много классной информации: что общего у чайки и GPS, почему переменный ток выиграл у постоянного и многое другое!
