Lispで多項式計算

Table of Contents

1 定数倍

多項式を定数倍した新しい多項式を求める関数 imul は以下のように定義できる.

1:  (defun imul (b xs)
2:    (if (null xs)
3:      ()
4:      (cons (* b (car xs)) (imul b (cdr xs)))
5:  ))

2 加算

二つの多項式の和になっている新しい多項式を求める関数 add を作成する.

(add xs ys)の動作は,以下のように再帰的に定義できる.

  • xsが空リストの場合ysが答えであり,ysが空リストの場合xsが答えである.
  • どちらも空リストでない場合,(cdr xs)と(cdr ys)に対して 再帰的にaddを実行した結果のリストの前に, 双方の先頭要素の和を付け加えたリストが答えである.

これをプログラムとして記述すると,以下のようになる.

1:  (defun add (xs ys)
2:    (if (null xs)
3:      ys
4:      (if (null ys)
5:        xs
6:        (cons (+ (car xs) (car ys)) (add (cdr xs) (cdr ys)))
7:  )))

3 乗算

二つの多項式の積になっている新しい多項式を求める関数 mul を作成する.

(mul xs ys)の動作は,以下のように再帰的に定義できる.

  • xsが空リストの場合,空リストが答えである.
  • xsが空リストでない場合,(cdr xs)とysに対して 再帰的にmulを実行した結果のリストの前に0を付け加えたリストと, ysを(car xs)倍 (imul)したリストとの和 (add)が答えである.

これをプログラムとして記述すると,以下のようになる.

1:  (defun mul (xs ys)
2:    (if (null xs)
3:      ()
4:      (add (imul (car xs) ys) (cons 0 (mul (cdr xs) ys)))
5:  ))

4 プログラム全体

プログラム全体は,以下のようになる.

 1:  (defun imul (b xs)
 2:    (if (null xs)
 3:      ()
 4:      (cons (* b (car xs)) (imul b (cdr xs)))
 5:  ))
 6:  
 7:  (defun add (xs ys)
 8:    (if (null xs)
 9:      ys
10:      (if (null ys)
11:        xs
12:        (cons (+ (car xs) (car ys)) (add (cdr xs) (cdr ys)))
13:  )))
14:  
15:  (defun mul (xs ys)
16:    (if (null xs)
17:      ()
18:      (add (imul (car xs) ys) (cons 0 (mul (cdr xs) ys)))
19:  ))

Cと比較して,ずいぶん簡潔であることがわかる.

実行結果は,以下のようになる.

(imul 2 '(1 -1 0 2 -3))
(2 -2 0 4 -6)

(add '(1 2 3) '(1 -2 3 -4))
(2 0 6 -4)

(mul '(1 2 3) '(1 -2 3))
(1 0 2 0 9)

5 練習問題

  1. 二つの多項式の差を求める関数 sub を作成せよ.
  2. 多項式と整数bが与えられた時, 多項式が単項式 x-b で割り切れるかどうか調べる関数 divisible を作成せよ.
  3. 多項式を微分した新しい多項式を求める関数 deriv を作成せよ.

Date: 2017-09-29 21:45:43 JST

Author: 田村直之

Validate XHTML 1.0