Наибольший общий делитель (НОД) двух многочленов

Калькулятор вычисляет наибольший общий делитель (НОД) двух многочленов методом Евклида. Коэффициенты многочлена могут быть целыми, простыми дробями или комплексными числами с целыми или дробными коэффициентами. Результатом является полином, который делит оба исходных полинома без остатка или единица, если такого полинома не нашлось.

Наибольший общий делитель (НОД) двух многочленов

Многочлен 1

Многочлен 2

ПсевдоостаткиОбычные остатки Простые псевдоостатки Сокращенные на НОД коэффициентов Подрезультант Подрезультант, улучшенный

Алгоритм корректировки остатков (псевдо-остатков)

Оценка метода вычисления остатков

Вычисляет НОД коэффициентов на каждом шаге.

Точность вычисления

Точно

Округленно

Знаков после запятой: 2

Рассчитать

Результат

 

Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.

Загрузить 

 Ссылка  Сохранить  Виджет

Проблема взрывного роста коэффициентов остатков

При вычислении НОД для полиномов значительных степеней, коэффициенты остатков довольно быстро растут, это можно увидеть на примере данных по-умолчанию. Поэтому, для сокращения размера коэффициентов используют псевдоделение, что позволяет находить НОД в целых числах и минимизировать коэффициенты. В калькуляторе можно выбрать один из 3-х способов сокращения остатков, не считая тривиального псевдоделения, где просиходит избавление от дробей, но коэффициенты остатков не сокращаются.

Максимальное сокращение коэффициентов можно получить, поделив, коэффициенты остатка на общий НОД коэффициентов, но этот способ может быть вычислительно сложным для полиномов больших степеней со сложными коэффициентами.

В качестве компромиссного варианта используют алгоритмы на основе вычисления субрезультанта псевдоостатков полиномов (Subresultant PRS). Наш калькулятор использует два таких алгоритма (Алгоритм 1 и Алгоритм 3), описанные В.С. Брауном в статье The Subresultant PRS Algorithm¹.
Для оценки работы алгоритма калькулятор выводит таблицу псевдоостатков и вычисляет НОД их коэффициентов. Чем меньше НОД в этой таблице, тем эффективнее работает алгоритм.