这是一个采用相当古老的语言标准ML实现的算法。我难以理解这个算法：
fun polyquotremd ts ((n,b) :: us) =
let fun quo [] qs = (rev qs, [])
| quo ((m,a) :: ts) qs =
if m < n then (rev qs, (m,a) :: ts)
else
quo (polysum ts
(map (termproduct(m-n, ~a/b)) us))
((m-n, a/b) :: qs)
in
quo ts []
end;
这是目标。我们通过使用元组列表来密集表示多项式，每个元组包含指数在索引0处和系数在索引1处。例如，$x^2 + 1$ 表示为
[(2, 1.0), (0, 1.0)]。这由下面的辅助函数中的类型(int*real)list给出。我们想要获得一个输出(quo, rem)，每个都是指示商和余数的元组列表。 ts 是要被除的多项式，而us 是除数。这是我想象中算法的工作方式：
首先，如果
ts = []，那么这意味着我们没有多项式可以除以，因此我们返回qs，我们的累积商结果作为答案。由于我们不断将((m-n, a/b) :: qs)添加到qs列表的头部，因此需要反转列表以使其以最大指数开头。第一个if条件处理除数的指数n大于我们正在处理的当前幂m的情况。在这种情况下，我们只需不添加该元素并返回
(rev qs, (m,a) :: ts)，即(quo, rem)else条件是我感到困惑的部分。我知道第二个括号
((m-n, a/b) :: qs)是我们要添加的累积结果，但polysum ts (map (termproduct(m-n, ~a/b)) us))实际上在做什么？背后的数学是什么？
~a/b（对您的参考，意味着-a/b）。
辅助函数：
fun take ([], _) = []
| take (x::xs, i) = if i>0
then x :: take(xs, i-1)
else [];
fun drop ([], _) = []
| drop (x::xs, i) = if i>0 then drop(xs,i-1)
else x::xs;
fun termproduct (m,a) (n,b) = (m+n, a*b) : (int*real);
fun polyproduct [] us = []
| polyproduct [(m,a)] us = map (termproduct(m,a)) us
| polyproduct ts us =
let
val k = length ts div 2
in
polysum (polyproduct (take(ts,k)) us)
(polyproduct (drop(ts,k)) us)
end;
有人能给我解释一下第三点吗？我对这个算法的数学部分非常困惑。但它确实起作用..顺便说一句，这段代码可以编译，并且您可以在标准ML中测试它。