Длинная арифметика (5 сентября 2016)
- FFT (напоминание)
- Общая схема: интерполяция, экстраполяция, вычисление в комплексных числах и по простому модулю
- Рекурсивная реализация FFT
- Разделяй и властвуй
- Перевод из одной системы счисления в другую за logn умножений.
- Вычисление значний в произвольных точках за logn делений.
- Интерполяция за logn экстраполяций.
- Извлечение корня за logn делений.
- Быстрое деление
- Обращение формального ряда за O(nlogn)
- Деление многочленов с остатком за O(nlogn)
- Деление длинных чисел за O(nlogn)
- Где почитать? Лекция от sankowski