Длинная арифметика (5 сентября 2017)

  1. FFT (напоминание)
    1. Общая схема: интерполяция, экстраполяция, вычисление в комплексных корнях из 1.
    2. Рекурсивная реализация FFT
    3. Предподсчёт всех корней.
    4. Оценка точности вычислений, умножение чисел. Умножение многочленов по модулю.
    5. Два вещественных в одном комплексном

  2. Разделяй и властвуй
    1. Перевод из одной системы счисления в другую за logn умножений.
    2. Деление многочленов с остатком за O(nlog2n): подробности реализации
    3. Вычисление значений в произвольных точках за logn делений.
    4. Интерполяция за logn вычислений значений в произвольных точках.
    5. Извлечение корня за logn делений.

  3. Где почитать? Лекция от sankowski