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

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