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

다항식 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.py 를 수정한 것이다.

python 대신 jython이나 IronPython 으로도 수정 없이 그대로 실행된다.

1. # coding: MS949
3. #  Filename: testSyntheticDivision2.py
4. #
5. #  Purpose:  Find the quotient and remainder when some polynomial is
6. #            divided by a monic polynomial of the first degree.
7. #
8. #  Execute:  python testSyntheticDivision2.py 5 -4 7 8 6 8
9. #        Or  jython testSyntheticDivision2.py 5 -4 7 8 6 8
11. import sys
13. # 사용법 표시
14. def printUsage():
15.     print("사용법: python testSyntheticDivision2.py [제식의 계수] [피제식의 계수들]")
16.     print("조립제법(synthetic method)에 의한 다항식 나눗셈 결과를 보여준다.")
18. # 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
19. # 전체 문자열 표시 너비는 매개변수 width 로 전달받아 처리한다.
20. def simplify(v, width=None):
21.     t = "%g" % v
22.     tlen = len(t)
23.     if t[tlen-2:tlen-1] == ".0":
24.         t = t[0, -2]
25.     if width != None:
26.         if tlen < width:
27.             t = "              "[0: width - tlen] + t
28.     return t
30. # "/수" 표시하기
31. # 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
32. # 전체 문자열 표시 너비는 매개변수 width 로 전달받아 처리한다.
33. def simplifyReciprocal(v, width=None):
34.     t = "/%g" % v
35.     tlen = len(t)
36.     if t[tlen-2:tlen-1] == ".0":
37.         t = t[0, -2]
38.     if width != None:
39.         if tlen < width:
40.             t = "              "[0: width - tlen] + t
41.     return t
43. # 다항식을 내림차순의 스트링 표현으로 반환
44. def toPolyString(c):
45.     t = ""
46.     sc0 = simplify(c[0])
47.     if len(c) > 2:
48.         if sc0 == "1":
49.             t += "x^%d" % (len(c)-1)
50.         elif sc0 == "-1":
51.             t += "-x^%d" % (len(c)-1)
52.         else:
53.             t += sc0 + " x^%d" % (len(c)-1)
54.     elif len(c) == 2:
55.         if sc0 == "1":
56.             t += "x"
57.         elif sc0 == "-1":
58.             t += "-x"
59.         else:
60.             t += sc0 + " x"
61.     elif len(c) == 1:
62.         t += sc0
64.     for i in range(1, len(c)):
65.         k = len(c) - 1 - i
66.         sc = simplify(c[i])
67.         if k > 1:
68.             if c[i] > 0.0:
69.                 if sc == "1":
70.                     t += " + " + "x^%d" % k
71.                 else:
72.                     t += " + " + sc + " x^%d" % k
73.             elif c[i] < 0.0:
74.                 if sc == "-1":
75.                     t += " - " + "x^%d" % k
76.                 else:
77.                     t += " - " + simplify(abs(c[i])) + " x^%d" % k
78.         elif k == 1:
79.             if c[i] > 0.0:
80.                 if sc == "1":
81.                     t += " + " + "x"
82.                 else:
83.                     t += " + " + sc + " x"
84.             elif c[i] < 0.0:
85.                 if sc == "-1":
86.                     t += " - " + "x"
87.                 else:
88.                     t += " - " + simplify(abs(c[i])) + " x"
89.         elif k == 0:
90.             if c[i] > 0.0:
91.                 t += " + " + sc
92.             elif c[i] < 0.0:
93.                 t += " - " + simplify(abs(c[i]))
94.     return t
96. # 다항식 나눗셈 결과를
97. #     (피제식) = (제식)(몫) + (나머지)
98. # 형태로 출력
99. def printDivisionResult(a, c, d, b):
100.     strLine = "  " + toPolyString(c)
101.     print( strLine )
103.     strLine = "    = ( " + toPolyString( [a[0], -a[1]] ) + " )"
104.     tmp = [0.0] * (len(b) - 1)
105.     for i in range(0, len(tmp)):
106.         tmp[i] = b[i]
107.     strLine += "( " + toPolyString(tmp) + " )"
108.     r = d[len(d) - 1]
109.     if r > 0.0:
110.         strLine += " + " + simplify(r)
111.     elif r < 0.0:
112.         strLine += " - " + simplify(abs(r))
114.     print( strLine )
116. # 조립제법 계산표 출력 함수
117. def printSyntheticTable(a, c, s, d, q):
118.     strLine = "         | "
119.     strLine += simplify(c[0], 8)
120.     for i in range(1, len(c)):
121.         strLine += "  " + simplify(c[i], 8)
122.     print( strLine )
124.     strLine = simplify(a[1], 8) + " |"
125.     strLine += "           "
126.     strLine += simplify(s[1], 8)
127.     for i in range(2, len(s)):
128.         strLine += "  " + simplify(s[i], 8)
129.     print( strLine )
131.     strLine = "         |"
132.     for i in range(0, len(q)):
133.         strLine += "----------"
134.     print( strLine )
136.     strLine = "         | "
137.     strLine += simplify(d[0], 8)
138.     for i in range(1, len(d)):
139.         strLine += "  " + simplify(d[i], 8)
140.     print( strLine )
142.     strLine = simplifyReciprocal(a[0], 8) + " | "
143.     strLine += simplify(q[0], 8)
144.     for i in range(1, len(q) - 1):
145.         strLine += "  " + simplify(q[i], 8)
146.     print( strLine )
148. # 실행 시작 지점
149. if len(sys.argv) < 3:
150.     printUsage()
151.     sys.exit(1)
153. ######################################################
154. # 피제식은 c_0 x^n +  c_1 x^(n -1) + ... + c_n
155. # 제식은 a x -  b
156. a = [float(sys.argv[1]), - float(sys.argv[2])]
157. c = [0.0]*(len(sys.argv) - 3)
158. s = [0.0]*(len(sys.argv) - 3)
159. d = [0.0]*(len(sys.argv) - 3)
160. b = [0.0]*(len(sys.argv) - 3)
162. for i in range(0, len(c)):
163.     c[i] = float(sys.argv[i + 3])
165. ######################################################
166. # 조립제법의 주요 부분
167. s[0] = 0.0
168. d[0] = c[0]
169. b[0] = c[0] / a[0]
170. for i in range(1, len(c)):
171.     s[i] = b[i-1]*a[1]
172.     d[i] = c[i] + s[i]
173.     b[i] = d[i] / a[0]
175. ######################################################
176. # 몫의 계수와 나머지를 출력한다.
177. print("몫의 계수는"),
178. for i in range(0, len(b) - 2):
179.     print(simplify(b[i], None) + ", " ),
180. print(simplify(b[len(b) - 2], None)),
181. print("이고, 나머지는 " + simplify(d[len(d) - 1], None) + " 이다.")
182. print
184. ######################################################
185. # 조립제법 표를 출력한다.
186. printSyntheticTable(a, c, s, d, b)
187. print
189. ######################################################
190. # (피제식) = (제식) x (몫) + (나머지)
191. printDivisionResult(a, c, d, b)

실행> python testSyntheticDivision2.py 5 -4 7 8 6 8
몫의 계수는 1.4,  2.72,  3.376 이고, 나머지는 21.504 이다.

         |        7         8         6         8
       4 |                5.6     10.88    13.504
         |----------------------------------------
         |        7      13.6     16.88    21.504
      /5 |      1.4      2.72     3.376

  7 x^3 + 8 x^2 + 6 x + 8
    = ( 5 x - 4 )( 1.4 x^2 + 2.72 x + 3.376 ) + 21.504




이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.