Эшу быдлокодит

Forwarded from Архив КС/РФ(Сиона-Футуриста) (Красный)

Познакомился с занятной историей — как оптимизировались алгоритмы умножения чисел.

До ХХ века над вычислительной сложностью умножения математики особо не задумывались. Проблема стала реально актуальна только с появлением электронной вычислительной техники, где операция умножения изначально занимала намного больше времени, чем операция сложения.

Если рассматривать перемножение двух числе одинаковой длины, стандартный алгоритм умножения требует выполнения n^2 (n в квадрате) шагов, где n - число цифр в каждом из них.

В 1960 году советский аспирант Анатолий Карацуба, в рамках спора со своим учителем Андреем Колмогоровым за неделю сообразил новый алгоритм, в котором требуется уже n^1.58 шагов. Вроде бы мелочь, но при перемножении чисел длиной в 1000 цифр выигрыш в производительности уже составит около 18 раз.

Суть алгоритма в разбиении стандартного перемножения на комбинацию из сложений и вычитаний. От этой идеи отталкивались создатели огромного числа алгоритмов, без которых современная техника была бы невозможна, например — быстрого преобразования Фурье, краеугольного камня в обработке сигналов.

К настоящему моменту, в несколько этапов, вроде как достигнут предел производительности умножения: это n × log n шагов, что обладает научной новизной, но на практике пока что бесполезно: производители электроники подтянули скорость перемножения чисел на аппаратном уровне (в т.ч. используя подход Карацубы), и выгадывать лишние копейки производительности ценой перекройки сложившихся технологических процессов никому не интересно.

Eshu Marabo

www.tgoop.com/eshu_coding/104

138 viewsEshu Marabo, Nov 13, 2020 at 07:33

Познакомился с занятной историей — как оптимизировались алгоритмы умножения чисел.

До ХХ века над вычислительной сложностью умножения математики особо не задумывались. Проблема стала реально актуальна только с появлением электронной вычислительной техники, где операция умножения изначально занимала намного больше времени, чем операция сложения.

Если рассматривать перемножение двух числе одинаковой длины, стандартный алгоритм умножения требует выполнения n^2 (n в квадрате) шагов, где n - число цифр в каждом из них.

В 1960 году советский аспирант Анатолий Карацуба, в рамках спора со своим учителем Андреем Колмогоровым за неделю сообразил новый алгоритм, в котором требуется уже n^1.58 шагов. Вроде бы мелочь, но при перемножении чисел длиной в 1000 цифр выигрыш в производительности уже составит около 18 раз.

Суть алгоритма в разбиении стандартного перемножения на комбинацию из сложений и вычитаний. От этой идеи отталкивались создатели огромного числа алгоритмов, без которых современная техника была бы невозможна, например — быстрого преобразования Фурье, краеугольного камня в обработке сигналов.

К настоящему моменту, в несколько этапов, вроде как достигнут предел производительности умножения: это n × log n шагов, что обладает научной новизной, но на практике пока что бесполезно: производители электроники подтянули скорость перемножения чисел на аппаратном уровне (в т.ч. используя подход Карацубы), и выгадывать лишние копейки производительности ценой перекройки сложившихся технологических процессов никому не интересно.

Eshu Marabo

BY Эшу быдлокодит