1.3次多項式の因数分解
2次の多項式の因数分解ができるようになったので、3次の多項式について考える。一般に、3次の多項式は\(p \times x^3 +q \times x^2 +r \times x + s\)と表すことができる。但し、\(p>0\)。これは因数分解できる場合には、\(a \times x^2 + b \times x + c\)と\(a' \times x + b'\)の式を得る。このとき、\(a \times a' = p\), \(a \times b' + b \times a'= q\), \(b \times b' + c \times a'= r\), \(c \times b' = s\)である。
2次多項式の場合と同様にプログラムを書くと次のようになる。
factor3 (p:q:r:s:[]) = concat $ take 1 $ [[[a,b,c],[a',b']] | a <- [1..p], mod p a == 0, let a' = div p a, c <- [-abs(s)..abs(s)], c /= 0, mod s c == 0, let b' = div s c, mod (q - a * b') a' == 0, let b = div (q - a * b') a', b * b' + c * a' == r]
実行結果は次のようになる。
*Main> factor3 [1,0,0,-1] [[1,1,1],[1,-1]]
2.一般化
2次あるいは3次の多項式を別々の関数で呼ぶのは面倒くさいので、多項式を入力すれば、因数分解するプログラムを求めることにする。まず、最初の係数は正であるという制約を外し、負でもよいことにする。プログラムの概要は次のようになる。関数の名前はfactorである。これは、入力リストを見て、何次の多項式であるかを見極め、そのために用意された関数を呼び出す。また、3次の多項式で因数分解できたときは、そこで得た2次の多項式に対してさらに因数分解を試みる。
プログラムは以下の通りとなる。
factor :: [Int] -> [[Int]] factor x | length x < 2 = error "We need a linear equation." | length x > 4 = error "We have not implemented it yet." | otherwise = factor' x factor' (p:q:r:[]) | p < 0 = [[-1]] ++ factor2 [-p,-q,-r] | otherwise = factor2 [p,q,r] factor' (p:q:r:s:[]) | p < 0 = [[-1]] ++ factor3 [-p,-q,-r,-s] | otherwise = factor3 [p,q,r,s] factor2 :: [Int] -> [[Int]] factor2 (p:q:0:[]) = [[1,0],[p,q]] factor2 (p:q:r:[]) = concat $ take 1 $ [[[a,b],[a',b']] | a <- [1..p], mod p a == 0, let a' = div p a, b <- [-abs(r)..abs(r)], b /= 0, mod r b == 0, let b' = div r b, a * b' + b * a' == q] factor3 :: [Int] -> [[Int]] factor3 (p:q:r:0:[]) | w == [] = [[1,0],[p,q,r]] | otherwise = [[1,0]] ++ w where w = factor2 [p,q,r] factor3 (p:q:r:s:[]) | x == [] = [] | y == [] = x | otherwise = (last x) : y where x = concat $ take 1 $ [[[a,b,c],[a',b']] | a <- [1..p], mod p a == 0, let a' = div p a, c <- [-abs(s)..abs(s)], c /= 0, mod s c == 0, let b' = div s c, mod (q - a * b') a' == 0, let b = div (q - a * b') a', b * b' + c * a' == r] y = factor2 $ head x
実行結果は次のようになる。
Main> factor [1,1,-1,-1]
[[1,1],[1,-1],[1,1]]
|