bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

細かく細かく分解する(2)

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]]
|

3.問題

4次の多項式因数分解するプログラムを作成しなさい。