Быстрые вычисления с целыми числами и полиномами

  • Просмотров 2307
  • Скачиваний 33
  • Размер файла 75
    Кб

Министерство образования Российской Федерации Ярославский Государственный Университет им. П.Г. Демидова Курсовая работа По дисциплине «Алгебра» Быстрые вычисления с целыми числами и полиномами Выполнил: Студент группы КБ-11 Сбоев А.В. Проверил: Дурнев В.Г. Ярославль, 2003 Содержание Введение. Сложность теоретико-числовых алгоритмов. Полиномиальные алгоритмы Алгоритм вычисления ad mod m Дихотомический алгоритм возведения в

степень Алгоритм Евклида Алгоритм решения уравнения ax + by = 1 Полиномиальная арифметика Алгоритм нахождения делителей многочлена f(x) в кольце Fp[x] Произведение и возведение в степень многочленов, заданных массивами Небольшие оптимизации для произведения многочленов Вычисление полиномов Схема Горнера Интерполяционная формула Ньютона и табулирование значений многочлена Дискретное логарифмирование 1. Введение. Сложность

теоретико-числовых алгоритмов Сложность алгоритмов теории чисел обычно принято измерять количеством арифметических операций (сложений, вычитаний, умножений и делений с остатком), необходимых для выполнения всех действий, предписанных алгоритмом. Впрочем, это определение не учитывает величины чисел, участвующих в вычислениях. Ясно, что перемножить два стозначных числа значительно сложнее, чем два однозначных, хотя при этом и

в том, и в другом случае выполняется лишь одна арифметическая операция. Поэтому иногда учитывают ещё и величину чисел, сводя дело к так называемым побитовым операциям, т. е. Оценивая количество необходимых операций с цифрами 0 и 1, в двоичной записи чисел. Это зависит от рассматриваемой задачи, целей автора и т. д. На первый взгляд странным также кажется, что операции умножения и деления приравниваются по сложности к операциям

сложения и вычитания. Житейский опыт подсказывает, что умножать числа значительно сложнее, чем складывать их. В действительности же, вычисления можно организовать так, что на умножение или деление больших чисел понадобится не намного меньше битовых операций, чем на сложение. Существует алгоритм Шенхаге – Штрассена, основанный на так называемом быстром преобразовании Фурье, и требующий O(n ln n lnln n) битовых операций для умножения