这是一个采用相当古老的语言标准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中测试它。