多项式除法 算法可应用于多精度大数计算吗？
闲逛网络，偶尔发现篇“多项式除法及求模”，用到了“多项式求逆元”及系数反转方法，非常巧妙！现在的问题是：多精度大数计算中的除法或模运算，可以借鉴上述算法吗？ 这个感觉和Montgomery算法的思想很类似呀 它与 Montgomery 算法思想确实有点类似。
可惜，我揣摩了几天，似乎不适合应用于大数计算中。
因为有理代数运算，系数允许负数、分数；而大数运算得到的结果必须为小于进制的非负整数。
两者的鸿沟还是蛮大的。 假设我们要计算 \(123456 \div 789 =？\)
如果将它们看作10进制的代数式，则：PolynomialQuotient
结果为：\[\frac{706}{2401} + \frac{36 x}{343} + \frac{6 x^2}{49} + \frac{x^3}{7}\]
采用先求多项式逆元的算法，流程如下：AR = 1 + 2 x + 3 x^2 + 4 x^3 + 5 x^4 + 6 x^5;
BR = 7 + 8 x + 9 x^2;
1/7
PolynomialMod[% (2 - % BR), x^2]
PolynomialMod[% (2 - % BR), x^4]
PolynomialMod[% AR, x^4]
结果为：
\begin{align*}
&\frac{1}{7} \\
&\frac{1}{7} - \frac{8 x}{49} \\
&\frac{1}{7} - \frac{8 x}{49}+ \frac{x^2}{343} + \frac{496 x^3}{2401} \\
&\frac{1}{7} + \frac{6 x}{49}+ \frac{36 x^2}{343} + \frac{706 x^3}{2401} \\
\end{align*} 注意到分母7、49、343、2401都是\(7^n\)；除式\(7 x^2 + 8 x + 9\)的最高幂项系数
验证确实只与最高幂项系数有关
PolynomialQuotient
那么如何进一步改良，，，，，，
-----------
设想1，调整除数进制使最高幂项系数为1
-----------
设想2，除数被除数均乘上一个整数k，使得除数最高幂项系数为1 单次试验
{200,100}//RandomInteger[{10^#,10^(#+1)-1}]&/@#&//(Print[#];#)&//Ceiling]]+1)/#[]]#&//(Print[#];#)&//FromDigits,x]&/@#&//{#[]/#[],PolynomialQuotient[#[],#[],x]}&//#/.x->10&//{#[]//Round,#[],#[]-#[]//Round//Abs//{#,IntegerLength[#]}&}&
多次试验
Table[{200,100}//RandomInteger[{10^#,10^(#+1)-1}]&/@#&//Ceiling]]+1)/#[]]#&//FromDigits,x]&/@#&//{#[]/#[],PolynomialQuotient[#[],#[],x]}&//#/.x->10&//#[]-#[]&//Round//Abs//IntegerLength,{100}]
误差小于准确值长度一半，需要一次牛顿法修正，，，，
页:
[1]