조립제법(Horner의 방법) 예제 2 for Common Lisp

다항식 p(x) 를 1차 다항식 ax - b 로 나눌 때의 몫과 나머지를 구하는 조립제법을
Python 언어로 구현해 보았다. 조립제법은 일명 Horner의 방법이라고도 불리우는데, 이는
x = a 에서 다항식 p(x)의 값 p(a)을 계산하는 가장 빠른 알고리즘이기도 하다.

         p(x) = (ax - b)q(x) + r

여기서 r은 나머지이며 r = p(b/a) 이다. 또 q(x)는 몫이다.

[참고]
    * 온라인으로 조립제법 표 만들기 손으로 계산하는 조립제법 표 
    * 온라인으로 구하는 다항식의 도함수: 조립제법을 이용한 다항식의 도함수


아래의 소스파일은 이전에 작성했던 파일 testSyntheticDivision.lsp 를 수정한 것이다.

1. ;;  Filename: testSyntheticDivision2.lsp
2. ;;
3. ;;  Purpose:  Find the quotient and remainder when some polynomial is
4. ;;            divided by a monic polynomial of the first degree.
5. ;;
6. ;;  Execute:  clisp testSyntheticDivision2.lsp 5 -4 7 8 6 8
7. ;;
8. ;;  Date: 2013. 9. 7.
11. ;; 사용법 표시
12. (defun printUsage()
13.     (format t "사용법: clisp testSyntheticDivision2.lsp [제식의 계수] [피제식의 계수들]~%")
14.     (format t "조립제법(synthetic method)에 의한 다항식 나눗셈 결과를 보여준다.~%")
15. )
17. ;; 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
18. ;; 전체 문자열 표시 너비는 매개변수 width 로 전달받아 처리한다.
19. (defun simplify(v &optional width)
20.     (let* ((tt "")
21.            (slen 0))
22.         (setf tt (format nil "~A" v))
23.         (setf slen (length tt))
24.         (if (and (>= slen 2) (string= (substring tt (- slen 2) slen) ".0"))
25.             (setf tt (substring tt 0 (- slen 2))) )
26.         (setf slen (length tt))
27.         (if width
28.             (if (< slen width)
29.                 (setf tt (concatenate 'string (make-string (- width slen) :initial-element #\Space) tt)) ))
30.         tt
31.     )
32. )
34. ;; "/수" 표시하기
35. ;; 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
36. ;; 전체 문자열 표시 너비는 매개변수 width 로 전달받아 처리한다.
37. (defun simplifyReciprocal(v &optional width)
38.     (let* ((tt "")
39.            (tlen 0))
40.         (setf tt (format nil "/~A" v))
41.         (setf tlen (length tt))
42.         (if (and (>= tlen 2) (string= (substring tt (- tlen 2) tlen) ".0"))
43.             (setf tt (substring tt 0 (- tlen 2))) )
44.         (setf tlen (length tt))
45.         (if width
46.             (if (< tlen width)
47.                 (setf tt (concatenate 'string (make-string (- width tlen) :initial-element #\Space) tt)) ))
48.         tt
49.     )
50. )
52. ;; 다항식을 내림차순의 스트링 표현으로 반환
53. (defun toPolyString(c)
54.     (let* ((ttt "")
55.            (sc0 "")
56.            (sc "")
57.            (k 0))
58.         (setf ttt "")
59.         (setf sc0 (simplify (nth 0 c) nil ))
60.         (if (> (length c) 2)
61.             (cond
62.                ((string= sc0 "1") (setf ttt (concatenate 'string ttt (format nil "x^~D" (- (length c) 1)))))
63.                ((string= sc0 "-1") (setf ttt (concatenate 'string ttt (format nil "-x^~D" (- (length c) 1)))))
64.                (t (setf ttt (concatenate 'string ttt sc0 (format nil " x^~D" (- (length c) 1)))))
65.             )
66.         )
68.         (if (= (length c) 2)
69.             (cond
70.                ((string= sc0 "1") (setf ttt (concatenate 'string ttt "x")))
71.                ((string= sc0 "-1") (setf ttt (concatenate 'string ttt "-x")))
72.                (t (setf ttt (concatenate 'string ttt sc0 " x")))
73.             )
74.         )
75.         (if (= (length c) 1)
76.                (setf ttt (concatenate 'string ttt sc0))
77.         )
79.         (loop for i from 1 below (length c) do
80.             (setf k (- (length c) 1 i))
81.             (setf sc (simplify (nth i c) nil))
82.             (if (> k 1) (progn
83.                 (cond
84.                     ((> (nth i c) 0.0)
85.                         (if (string= sc "1")
86.                             (setf ttt (concatenate 'string ttt " + " (format nil "x^~D" k)))
87.                             (setf ttt (concatenate 'string ttt " + " sc (format nil " x^~D" k)))
88.                         ) )
89.                     ((< (nth i c) 0.0)
90.                         (if (string= sc "-1")
91.                             (setf ttt (concatenate 'string ttt " - " (format nil "x^~D" k)))
92.                             (setf ttt (concatenate 'string ttt " - " (simplify (abs (nth i c)) nil) (format nil " x^~D" k)))
93.                         ) )
94.                     )
95.                 )
96.             )
98.             (if (= k 1)
99.                 (cond
100.                     ((> (nth i c) 0.0)
101.                         (if (string= sc "1")
102.                             (setf ttt (concatenate 'string ttt " + " "x"))
103.                             (setf ttt (concatenate 'string ttt " + " sc " x"))
104.                         ) )
105.                     ((< (nth i c) 0.0)
106.                         (if (string= sc "-1")
107.                             (setf ttt (concatenate 'string ttt " - " "x"))
108.                             (setf ttt (concatenate 'string ttt " - " (simplify (abs (nth i c))) " x"))
109.                         ) )
110.                 )
111.             )
112.             (if (= k 0)
113.                 (cond
114.                     ( (> (nth i c) 0.0) (setf ttt (concatenate 'string ttt " + " sc)) )
115.                     ( (< (nth i c) 0.0) (setf ttt (concatenate 'string ttt " - " (simplify (abs (nth i c))) )) )
116.                 )
117.             )
118.         )
119.         ttt
120.     )
121. )
124. ;; 다항식 나눗셈 결과를
125. ;;     (피제식) = (제식)(몫) + (나머지)
126. ;; 형태로 출력
127. (defun printDivisionResult(a c d b)
128.     (let* ((strLine ""))
129.         (setf strLine (concatenate 'string "  " (toPolyString c)))
130.         (format t "~A~%" strLine)
131.         (setf strLine (concatenate 'string "    = ( " (toPolyString (list (nth 0 a) (- (nth 1 a)))) " )"))
132.         (setf tmp (make-list (- (length b) 1) :initial-element 0.0)) 
133.         (loop for i from 0 below (length tmp) do
134.             (setf (nth i tmp) (nth i b)) )
135.         (setf strLine (concatenate 'string strLine "( " (toPolyString tmp) " )"))
136.         (setf r (nth (- (length d) 1) d))
137.         (cond
138.            ((> r 0.0)  (setf strLine (concatenate 'string strLine " + " (simplify r nil) )))
139.            ((< r 0.0)  (setf strLine (concatenate 'string strLine " - " (simplify (abs r) nil) )))
140.         )
141.         (format t "~A~%" strLine)
142.     )
143. )
146. ;; 조립제법 계산표 출력 함수
147. (defun printSyntheticTable(a c s d q)
148.     (let* ((strLine ""))
149.         (setf strLine "         | ")
150.         (setf strLine (concatenate 'string strLine (simplify (nth 0 c) 10) ))
152.         (loop for i from 1 below (length c) do
153.             (setf strLine (concatenate 'string strLine "  " (simplify (nth i c) 10) )))
154.         (format t "~A~%" strLine)
156.         (setf strLine (concatenate 'string (simplify (nth 1 a) 8) " |"))
157.         (setf strLine (concatenate 'string strLine "             "))
158.         (setf strLine (concatenate 'string strLine (simplify (nth 1 s) 10)))
159.         (loop for i from 2 below (length s) do
160.             (setf strLine (concatenate 'string strLine "  " (simplify (nth i s) 10) )))
161.         (format t "~A~%" strLine)
163.         (setf strLine "         |")
164.         (loop for i from 0 below (length q) do
165.             (setf strLine (concatenate 'string strLine "------------")))
166.         (format t "~A~%" strLine)
168.         (setf strLine "         | ")
169.         (setf strLine (concatenate 'string strLine (simplify (nth 0 d) 10)))
170.         (loop for i from 1 below (length d) do
171.             (setf strLine (concatenate 'string strLine "  " (simplify (nth i d) 10))))
172.         (format t "~A~%" strLine)
174.         (setf strLine (concatenate 'string (simplifyReciprocal (nth 0 a) 8) " | "))
175.         (setf strLine (concatenate 'string strLine (simplify (nth 0 q) 10)))
176.         (loop for i from 1 below (1- (length q)) do
177.             (setf strLine (concatenate 'string strLine "  " (simplify (nth i q) 10) )))
178.         (format t "~A~%" strLine)
179.     )
180. )
182. ;; 실행 시작 지점
183. (if (< (length ext:*args*) 3) (progn
184.     (printUsage)
185.     (quit) ))
187. ;; ----------------------------------------------------
188. ;; 피제식은 c_0 x^n +  c_1 x^(n -1) + ... + c_n
189. ;; 제식은 a x -  b
190. (setf a (list (read-from-string (nth 0 ext:*args*)) (- (read-from-string (nth 1 ext:*args*)))) )
191. (setf c (make-list (- (length ext:*args*) 2) :initial-element 0.0) )
192. (setf s (make-list (- (length ext:*args*) 2) :initial-element 0.0) )
193. (setf d (make-list (- (length ext:*args*) 2) :initial-element 0.0) )
194. (setf b (make-list (- (length ext:*args*) 2) :initial-element 0.0) )
196. (loop for i from 0 below (length c) do
197.     (setf (nth i c) (read-from-string (nth (+ i 2) ext:*args*))))
199. ;; ----------------------------------------------------
200. ;; 조립제법의 주요 부분
201. (setf (nth 0 s) 0.0)
202. (setf (nth 0 d) (nth 0 c))
203. (setf (nth 0 b)  (+ 0.0 (/ (nth 0 c) (nth 0 a))))
204. (loop for i from 1 below (length c) do
205.     (setf (nth i s) (* (nth (- i 1) b) (nth 1 a)))
206.     (setf (nth i d) (+ (nth i c) (nth i s)))
207.     (setf (nth i b) (+ 0.0 (/ (nth i d) (nth 0 a)))) )
209. ;; ----------------------------------------------------
210. ;; 몫의 계수와 나머지를 출력한다.
211. (format t "몫의 계수는 ")
212. (loop for i from 0 below (- (length b) 2) do
213.     (format t (concatenate 'string (simplify (nth i b)) ",  ")))
214. (format t (concatenate 'string (simplify (nth (- (length b) 2) b)) " "))
215. (format t (concatenate 'string "이고, 나머지는 " (simplify (nth (- (length d) 1) d)) " 이다.~%"))
216. (terpri)
218. ;; ----------------------------------------------------
219. ;; 조립제법 표를 출력한다.
220. (printSyntheticTable a c s d b)
221. (terpri)
223. ;; ----------------------------------------------------
224. ;; (피제식) = (제식) x (몫) + (나머지)
225. (printDivisionResult a c d b)
226. (format t "~%")

실행> clisp testSyntheticDivision2.lsp 5 -4 7 8 6 8

몫의 계수는 1.4, 2.72, 3.3760002 이고, 나머지는 21.504002 이다. | 7 8 6 8 4 | 5.6 10.88 13.504001 |------------------------------------------------ | 7 13.6 16.880001 21.504002 /5 | 1.4 2.72 3.3760002 7 x^3 + 8 x^2 + 6 x + 8 = ( 5 x - 4 )( 1.4 x^2 + 2.72 x + 3.3760002 ) + 21.504002