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

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

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

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

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

1. #  Filename: testSyntheticDivision.io
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: io testSyntheticDivision.io -2 1 3 3 1
8. // 사용법 표시
9. printUsage := method (
10.     "Usage: io testSyntheticDivision.io [number] [coefficients of denominator]" println
11.      "Display the result of a synthetic division on the console." println
12. )
14. // 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
15. simplify := method(v,
16.     t := "" .. v
17.     if ((t size) > 2 and (t silce(t size - 2) == ".0")) then (
18.         t = t silce(t size - 2)
19.     )
20.     t
21. )
23. // 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
24. // 전체 문자열 표시 너비는 매개변수 width 로 전달받아 처리한다.
25. simplify := method(v, width,
26.     t := "" .. v
27.     if ((t size) > 2 and (t silce(t size - 2) == ".0")) then (
28.         t = t silce(t size - 2)
29.     )
31.     len := t size
32.     if (len < width) then (
33.         t = "               " slice(0, width - len) .. t
34.     )
35.     t
36. )
38. // 다항식을 내림차순의 스트링 표현으로 반환
39. toPolyString := method(c,
40.     t := ""
41.     sc0 := simplify(c at(0), 0 )
42.     if (c size  > 2) then (
43.         if (sc0 == "1")  then (
44.             t = t .. "x^" .. (c size - 1)
45.         ) elseif (sc0 == "-1")  then (
46.             t = t .. "-x^" .. (c size - 1)
47.         ) else (
48.             t = t .. sc0 .. " x^" .. (c size - 1)
49.         )
50.     ) elseif (c size == 2)  then (
51.         if (sc0 == "1")   then (
52.             t = t .. "x"
53.         ) elseif (sc0 == "-1")  then (
54.             t = t .. "-x"
55.         ) else (
56.             t = t .. sc0 .. " x"
57.         )
58.     ) elseif (c size == 1)  then (
59.         t = t .. sc0
60.     )
62.     for (i, 1, c size - 1,
63.         k := c size - 1 - i
64.         sc := simplify(c at(i), 0)
65.         if (k > 1) then (
66.             if (c at(i) asNumber > 0.0) then (
67.                 if (sc == "1") then ( 
68.                     t = t .. " + " .. "x^" .. k
69.                 ) else (
70.                     t = t .. " + " .. sc .. " x^" .. k
71.                 )
72.             ) elseif (c at(i) asNumber < 0.0) then (
73.                 if (sc == "-1") then (
74.                     t = t .. " + " .. "x^" .. k
75.                 ) else (
76.                     t = t .. " - " .. simplify(c at(i) abs, 0) .. " x^" .. k
77.                 )
78.             )
79.         ) elseif (k == 1) then (
80.             if (c at(i) asNumber > 0.0)  then (
81.                 if (sc == "1") then (
82.                     t = t .. " + " .. "x"
83.                 ) else (
84.                     t = t .. " + " .. sc .. " x"
85.                 )
86.             ) elseif (c at(i) asNumber < 0.0) then (
87.                 if (sc == "-1") then (
88.                     t = t .. " - " .. "x"
89.                 ) else (
90.                     t = t .. " - " .. simplify(c at(i) asNumber abs, 0) .. " x"
91.                 )
92.             )
93.         ) elseif (k == 0) then (
94.             if (c at(i)  asNumber > 0.0) then (
95.                 t = t .. " + " .. sc
96.             ) elseif (c at(i)  asNumber < 0.0) then (
97.                 t = t .. " - " .. simplify(c at(i)  asNumber abs, 0)
98.             )
99.         )
100.     ) 
101.     t
102. )
104. // 다항식 나눗셈 결과를
105. //     (피제식) = (제식)(몫) + (나마지)
106. // 형태로 출력
107. printDivisionResult := method(a, c, b,
108.     ("  " .. toPolyString(c)) print
109.     "" println
111.     ("    = ( " .. toPolyString( list(1.0, -a) ) .. " )") print
112.     tmp := list()
113.     for (i, 0, b size - 2,
114.         tmp append(0.0)
115.     )
116.     for (i, 0, tmp size - 1,
117.         tmp atPut(i, b at(i) asNumber)
118.     )
119.     ("( " .. toPolyString(tmp) .. " )") print
120.     r := b at(b size - 1)
121.     if (r > 0.0) then (
122.         (" + " .. simplify(r, 0), 0) print
123.     ) elseif (r < 0.0) then (
124.         (" - " .. simplify(r abs, 0), 0) print
125.     )
126.     "" println
127. )
129. // 조립제법 계산표 출력 함수
130. printSyntheticTable := method(a, c, s, q,
131.     "       | " print
132.     simplify(c at(0), 6) print
133.     for (i, 1, c size - 1,
134.         ("  " .. simplify(c at(i), 6)) print
135.     )
136.     "" println
138.     (simplify(a, 6) .. " | ") print
139.     "        " print
140.     simplify(s at(1), 6) print
141.     for (i, 2, s size - 1,
142.         ("  " .. simplify(s at (i), 6)) print
143.     )
144.     "" println
146.     "       |-" print
147.     for (i, 0, q size - 1,
148.         "--------" print
149.     )
150.     "" println
152.     "         " print
153.     simplify(q at(0), 6) print
154.     for (i, 1, q size - 1,
155.         ("  " .. simplify(q at(i), 6)) print
156.     )
157.     "" println
158. )
160. // 실행 시작 지점
161. if (args size  < 4) then (
162.     printUsage()
163.     exit(1)
164. )
166. a := (args at(1)) asNumber
167. c := list()
168. s := list()
169. b := list()
170. for (i, 0, args size - 3,
171.     c append(args at(i + 2))
172. )
173. for (i, 0, c size - 1,
174.     s append(0.0)
175.     b append(0.0)
176. )
177. s atPut(0, 0.0)
178. b atPut(0, c at(0))
179. for (i, 1, c size - 1,
180.     s atPut(i,  (b at(i-1) asNumber)*a )
181.     b atPut(i,  (c at(i) asNumber) + (s at(i) asNumber) )
182. )
184. "The coefficents of quotient is " print
185. for (i, 0, b size - 3,
186.     (simplify(b at(i), 0) .. ", " ) print
187. )
189. simplify(b at(b size - 2), 0) print
190. (", and the remainder is " .. simplify(b at(b size - 1), 0) .. ".") println
191. "" println
193. printSyntheticTable(a, c, s, b)
194. "" println
196. printDivisionResult(a, c, b)

io 명령으로 아래와 같이 실행하여 보았다.


실행> io testSyntheticDivision.io 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

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