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
возвращает самую маленькую из этих пар.
Решите эту линейную конгруэтность:.
numlib::reconstructRational(7, 12)
По модулю 98, та же конгруэтность не имеет никакого небольшого решения. Решение p=7, q=1
не является достаточно маленьким как 7
, не меньше, чем sqrt(98/2)
, но только равняйтесь.
numlib::reconstructRational(7, 98)
Реконструкция рационального числа в основном используется в качестве последнего шага модульного алгоритма. Например, найдите наибольшие общие делители следующих полиномов.
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