как работает этот способ умножения. объясните дураку

4 года назад от Михаил Горшенев

1 ответ

0 голосов
а где рассказ-то?

в ролике идет рассказ, что обычный способ имет трудоемкость n^2, а есть такой метод Штрассена (может и до него знали) с трудоемкостью n*log n

если интересно, суть быстрого умножения в том, что если каждое число представить как массив из отдельных чисел типа по цифрам, умножение по сути сводится к кореляции между двумя этими массивами. А кореляцию мы умем считать быстро через быстрое преобразование Фурье. Именно оно и занимает те самые n*log n операций, потом быстренько перемножаем за n операций, и преобразуем назад.

но вручную тут делать нечего.

именно так работает все шифрование
4 года назад от g-man1991

Связанные вопросы