3. Задачи на графах

Как уже было замечено, умножение многоразрядных чисел есть сверка двух массивов с переносом в старшие разряды. Если делать свертку с применением БПФ, то трудоемкость подобного алгоритма T(n) = n logn. Однако в таком случае на вход свертки подаются целочисленные массивы, а на выходе получается массив вещественных чисел, которые нужно округлить до ближайшего целого.

Замечание. При большой погрешности вычислений существует опасность округлить не в ту сторону. Следовательно, для уменьшения вероятности ошибки нужно увеличивать разрядность вычислений.

Тогда трудоемкость алгоритма составит:

T(n) = nlog₂n · log₂(log₂n).

т.к. мы увеличиваем разрядность чисел, с которыми работаем

трудоемкость быстрого перемножения

Домашнее задание №3. Найти произведение 3871 и 9211 по формуле быстрого умножения чисел.

Домашнее задание №4. Найти произведение 8329 и 5631 по формуле быстрого умножения чисел.