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

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

         p(x) = (x - a)q(x) + r

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

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


아래의 소스파일은 Groovy용 소스파일 testSyntheticDivision.groovy 를 Python용으로 수정한 것이다.

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

1. #  Filename: testSyntheticDivision.py
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:  python testSyntheticDivision.py -2 1 3 3 1
7. #        Or  jython testSyntheticDivision.py -2 1 3 3 1
9. import sys
11. # 사용법 표시
12. def printUsage():
13.     print("사용법: python testSyntheticDivision.py [수] [피제식의 계수들]")
14.     print("조립제법(synthetic method)에 의한 다항식 나눗셈 결과를 보여준다.")
16. # 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
17. # 전체 문자열 표시 너비는 매개변수 width 로 전달받아 처리한다.
18. def simplify(v, width=None):
19.     t = "%d" % v
20.     tlen = len(t)
21.     if t[tlen-2:tlen-1] == ".0":
22.         t = t[0, -2]
23.     if width != None:
24.         if tlen < width:
25.             t = "              "[0: width - tlen] + t
26.     return t
28. # 다항식을 내림차순의 스트링 표현으로 반환
29. def toPolyString(c):
30.     t = ""
31.     sc0 = simplify(c[0])
32.     if len(c) > 2:
33.         if sc0 == "1":
34.             t += "x^%d" % (len(c)-1)
35.         elif sc0 == "-1":
36.             t += "-x^%d" % (len(c)-1)
37.         else:
38.             t += sc0 + " x^%d" % (len(c)-1)
39.     elif len(c) == 2:
40.         if sc0 == "1":
41.             t += "x"
42.         elif sc0 == "-1":
43.             t += "-x"
44.         else:
45.             t += sc0 + " x"
46.     elif len(c) == 1:
47.         t += sc0
49.     for i in range(1, len(c)):
50.         k = len(c) - 1 - i
51.         sc = simplify(c[i])
52.         if k > 1:
53.             if c[i] > 0.0:
54.                 if sc == "1":
55.                     t += " + " + "x^%d" % k
56.                 else:
57.                     t += " + " + sc + " x^%d" % k
58.             elif c[i] < 0.0:
59.                 if sc == "-1":
60.                     t += " - " + "x^%d" % k
61.                 else:
62.                     t += " - " + simplify(abs(c[i])) + " x^%d" % k
63.         elif k == 1:
64.             if c[i] > 0.0:
65.                 if sc == "1":
66.                     t += " + " + "x"
67.                 else:
68.                     t += " + " + sc + " x"
69.             elif c[i] < 0.0:
70.                 if sc == "-1":
71.                     t += " - " + "x"
72.                 else:
73.                     t += " - " + simplify(abs(c[i])) + " x"
74.         elif k == 0:
75.             if c[i] > 0.0:
76.                 t += " + " + sc
77.             elif c[i] < 0.0:
78.                 t += " - " + simplify(abs(c[i]))
79.     return t
81. # 다항식 나눗셈 결과를
82. #     (피제식) = (제식)(몫) + (나머지)
83. # 형태로 출력
84. def printDivisionResult(a, c, b):
85.     strLine = "  " + toPolyString(c)
86.     print( strLine )
88.     strLine = "    = ( " + toPolyString( [1.0, -a] ) + " )"
89.     tmp = [0.0] * (len(b) - 1)
90.     for i in range(0, len(tmp)):
91.         tmp[i] = b[i]
92.     strLine += "( " + toPolyString(tmp) + " )"
93.     r = b[len(b) - 1]
94.     if r > 0.0:
95.         strLine += " + " + simplify(r)
96.     elif r < 0.0:
97.         strLine += " - " + simplify(abs(r))
98.     print( strLine )
100. # 조립제법 계산표 출력 함수
101. def printSyntheticTable(a, c, s, q):
102.     strLine = "       | "
103.     strLine += simplify(c[0], 6)
104.     for i in range(1, len(c)):
105.         strLine += "  " + simplify(c[i], 6)
106.     print( strLine )
108.     strLine = simplify(a, 6) + " |"
109.     strLine += "         "
110.     strLine += simplify(s[1], 6)
111.     for i in range(2, len(s)):
112.         strLine += "  " + simplify(s[i], 6)
113.     print( strLine )
115.     strLine = "       |"
116.     for i in range(0, len(q)):
117.         strLine += "--------"
118.     print( strLine )
120.     strLine = "         "
121.     strLine += simplify(q[0], 6)
122.     for i in range(1, len(q)):
123.         strLine += "  " + simplify(q[i], 6)
124.     print( strLine )
127. # 실행 시작 지점
128. if len(sys.argv) < 3:
129.     printUsage()
130.     sys.exit(1)
132. ######################################################
133. # 피제식은 c_0 x^n +  c_1 x^(n -1) + ... + c_n
134. # 제식은 x -  a
135. a = float(sys.argv[1])
136. c = [0.0]*(len(sys.argv) - 2)
137. s = [0.0]*(len(sys.argv) - 2)
138. b = [0.0]*(len(sys.argv) - 2)
140. for i in range(0, len(c)):
141.     c[i] = float(sys.argv[i + 2])
143. ######################################################
144. # 조립제법의 주요 부분
145. s[0] = 0.0
146. b[0] = c[0]
147. for i in range(1, len(c)):
148.     s[i] = b[i-1]*a
149.     b[i] = c[i] + s[i]
151. ######################################################
152. # 몫의 계수와 나머지를 출력한다.
153. print("몫의 계수는"),
154. for i in range(0, len(b) - 2):
155.     print(simplify(b[i], None) + ", " ),
156. print(simplify(b[len(b) - 2], None)),
157. print("이고, 나머지는 " + simplify(b[len(b) - 1], None) + " 이다.")
158. print
160. ######################################################
161. # 조립제법 표를 출력한다.
162. printSyntheticTable(a, c, s, b)
163. print
165. ######################################################
166. # (피제식) = (제식) x (몫) + (나머지)
167. printDivisionResult(a, c, b)

실행> python testSyntheticDivision.py 1 2 3 4 5
몫의 계수는 2, 5, 9 이고, 나머지는 14 이다.

       |      2       3       4       5
     1 |              2       5       9
       |---------------------------------
              2       5       9      14

  2 x^3 + 3 x^2 + 4 x + 5
    = ( x - 1 )( 2 x^2 + 5 x + 9 ) + 14