numlib::reconstructRational
Реконструкция рационального числа
Блокноты MuPAD® будут демонтированы в будущем релизе. Используйте live скрипты MATLAB® вместо этого.
Live скрипты MATLAB поддерживают большую часть функциональности MuPAD, хотя существуют некоторые различия. Для получения дополнительной информации смотрите, Преобразуют Notebook MuPAD в Live скрипты MATLAB.
Синтаксис
numlib::reconstructRational(a,n)
Описание
numlib::reconstructRational(a,n) возвращает два целых числа p,q из абсолютного значения, меньшего, чем sqrt(n/2) с p конгруэнтный a*q n по модулю. Это возвращает FAIL если такой p,q не существовать.
numlib::reconstructRational(a,n) возвращает p,q путем решения
.
Решение p,q удовлетворяет следующим условиям: p строго между -sqrt(n/2) и sqrt(n/2)Q строго между 0 и sqrt(n/2).
Если несколько пар p,q удовлетворите этим условиям, затем их отношения p/q то же самое. В таком случае, numlib::reconstructRational возвращает самую маленькую из этих пар.
Примеры
Пример 1
Решите эту линейную конгруэтность
:.
numlib::reconstructRational(7, 12)
По модулю 98, та же конгруэтность не имеет никакого небольшого решения. Решение p=7, q=1 не мал достаточно как 7 не меньше, чем sqrt(98/2) но только равный.
numlib::reconstructRational(7, 98)
Пример 2
Реконструкция рационального числа в основном используется в качестве последнего шага модульного алгоритма. Например, найдите наибольшие общие делители следующих полиномов.
f:= poly(x^5 + 22/35*x^3 + 3/8*x^2 + 3/35*x + 9/56, [x]):
g:= poly(x^5 + 2/5*x^4 + 22/35*x^3 + 153/280*x^2 + 3/35*x + 9/56,
[x]):Как правило, можно использовать gcd для этой задачи. Однако предположите, что вы знаете, что наибольший общий делитель имеет маленькие коэффициенты с числителем и знаменателем оба меньшие, чем 10. Затем можно использовать модульный алгоритм с меньшим модулем, чем gcd сделал бы: смочь восстановить их от их класса вычетов n по модулю, достаточно что
, например, n=211.
gcd(poly(f, IntMod(211)), poly(g, IntMod(211)))
Реконструкция рационального числа показывает, что постоянным коэффициентом должен быть 3/7:
numlib::reconstructRational(-90, 211)
gcd(f,g)
Параметры
|
Целое число |
|
Положительное целое число |
Возвращаемые значения
Последовательность, состоящая из целого числа и положительного целого числа или FAIL
Ссылки
[1] Давенпорт, J. H., Y.Siret и E.Tournier “Компьютерная Алгебра: Системы и Алгоритмы для Алгебраического Расчета”. Academic Press Inc, 1988, p.142