homechevron_rightУчебаchevron_rightМатематикаchevron_rightАлгебра

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

Вычисляет наибольший общий делитель (НОД) двух многочленов методом Евклида с возможн

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

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

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

Алгоритм корректировки остатков (псевдо-остатков)
Вычисляет НОД коэффициентов на каждом шаге.
Результат
 

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

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

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

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


  1. W.S. Brown, Bell Laboratories. ACM Transactions on Mathematical Software, Том 4, N 3, Сентябрь 1978, стр. 237-249 

Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Наибольший общий делитель (НОД) двух многочленов

Комментарии