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

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

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

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

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

1. /*
2.  *  Filename: testSyntheticDivision.scala
3.  *
4.  *  Purpose:  Find the quotient and remainder when some polynomial is
5.  *            divided by a monic polynomial of the first degree.
6.  *     이 소스는 그루비 소스 testSyntheticDivision.groovy 를
7.  *     스칼라 소스로 변환한 것이다.
8.  *
9.  *  Execute: scala -encoding MS949 testSyntheticDivision.scala -2 1 3 3 1
10.  *
11.  */
13. // 사용법 표시
14. def printUsage() {
15.      println("사용법: scala testSyntheticDivision.scala [수] [피제식의 계수들]")
16.      println("조립제법(synthetic method)에 의한 다항식 나눗셈 결과를 보여준다.")
17. }
19. // 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
20. def simplify(v: Double) : String = {
21.     var t : String = "" + v 
22.     if (t.endsWith(".0"))
23.         t = t.substring(0, t.length - 2)
24.     return t
25. }
27. // 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
28. // 전체 문자열 표시 너비는 매개변수 width 로 전달받아 처리한다.
29. def simplify(v: Double, width: Int) : String = {
30.     var t : String = "" + v
31.     if (t.endsWith(".0"))
32.         t = t.substring(0, t.length - 2)
33.     var len : Int = t.length
34.     if (len < width)
35.         t = "               ".substring(0, width - len) + t
36.     return t;
37. }
39. // 다항식을 내림차순의 스트링 표현으로 반환
40. def toPolyString(c : Array[Double]) : String = {
41.     var t : String = ""
42.     var sc0 : String = simplify(c(0))
44.     if (c.length > 2) {
45.         if (sc0 == "1")
46.             t += "x^" + (c.length-1)
47.         else if (sc0 == "-1")
48.             t += "-x^" + (c.length-1)
49.         else
50.             t += sc0 + " x^" + (c.length-1)
51.     }
52.     else if (c.length == 2) {
53.         if (sc0 == "1")
54.             t += "x"
55.         else if (sc0 == "-1")
56.             t += "-x"
57.         else
58.             t += sc0 + " x"
59.     }
60.     else if (c.length == 1) {
61.         t += sc0
62.     }
64.     for (i <- List.range(1, c.length)) {
65.         def k = c.length - 1 - i
66.         def sc = simplify(c(i))
67.         if (k > 1) {
68.             if (c(i) > 0.0) {
69.                 if (sc == "1")
70.                     t += " + " + "x^" + k
71.                 else
72.                     t += " + " + sc + " x^" + k
73.             }
74.             else if (c(i) < 0.0) {
75.                 if (sc == "-1")
76.                     t += " - " + "x^" + k
77.                 else
78.                     t += " - " + simplify(Math.abs((i))) + " x^" + k
79.             }
80.         }
81.         else if (k == 1) {
82.             if (c(i) > 0.0) {
83.                 if (sc == "1")
84.                     t += " + " + "x"
85.                 else
86.                     t += " + " + sc + " x"
87.             }
88.             else if (c(i) < 0.0) {
89.                 if (sc == "-1")
90.                     t += " - " + "x"
91.                 else
92.                     t += " - " + simplify(Math.abs(c(i))) + " x"
93.             }
94.         }
95.         else if (k == 0) {
96.             if (c(i) > 0.0) {
97.                 t += " + " + sc
98.             }
99.             else if (c(i) < 0.0)
100.                 t += " - " + simplify(Math.abs(c(i)))
101.         }
102.     }
103.     return t
104. }
106. // 다항식 나눗셈 결과를
107. //     (피제식) = (제식)(몫) + (나마지)
108. // 형태로 출력
109. def printDivisionResult(a : Double, c : Array[Double], b : Array[Double]) {
110.     print("  " + toPolyString(c))
111.     println()
113.     print("    = ( " + toPolyString( Array(1.0, -a)  ) + " )")
114.     var tmp : Array[Double] = new Array[Double](b.length - 1)
115.     for (i <- List.range(0, tmp.length)) {
116.         tmp(i) = b(i)
117.     }
118.     print("( " + toPolyString(tmp) + " )")
119.     var r : Double = b(b.length - 1)
120.     if (r > 0.0)
121.         print(" + " + simplify(r))
122.     else if (r < 0.0)
123.         print(" - " + simplify(Math.abs(r)))
124.     println()
125. }
127. // 조립제법 계산표 출력 함수
128. def printSyntheticTable(a : Double, c : Array[Double], s : Array[Double], q : Array[Double]) {
129.     print("       | ")
130.     print(simplify(c(0), 6))
131.     for (i <- List.range(1, c.length)) {
132.         print("  " + simplify(c(i), 6))
133.     }
134.     println()
135.     print(simplify(a, 6) + " | ")
136.     print("        ")
137.     print(simplify(s(1), 6))
138.     for (i <- List.range(2, s.length)) {
139.         print("  " + simplify(s(i), 6))
140.     }
141.     println()
143.     print("       |-")
144.     for (i <- List.range(0, q.length)) {
145.         print("--------")
146.     }
147.     println()
149.     print("         ")
150.     print(simplify(q(0), 6))
151.     for (i <- List.range(1, q.length)) {
152.         print("  " + simplify(q(i), 6))
153.     }
154.     println()
155. }
157. // 실행 시작 지점
158. if (args.length < 3) {
159.     printUsage()
160.     System.exit(1)
161. }
163. var a : Double = args(0).toDouble
164. var c : Array[double] = new Array[Double](args.length - 1)
165. var s : Array[double] = new Array[Double](c.length)
166. var b : Array[double] = new Array[Double](c.length)
167. for (i <- List.range(0, c.length)) {
168.     c(i) = args(i + 1).toDouble
169. }
171. s(0) = 0.0
172. b(0) = c(0)
173. for (i <- List.range(1, c.length)) {
174.     s(i) = b(i-1)*a
175.     b(i) = c(i) + s(i)
176. }
178. print("몫의 계수는 ")
179. for (i <- List.range(0, b.length - 2)) {
180.     print(simplify(b(i)) + ", " )
181. }
183. print(simplify(b(b.length - 2)))
184. println(" 이고, 나머지는 " + simplify(b(b.length - 1)) + " 이다.")
185. println()
187. printSyntheticTable(a, c, s, b)
188. println()
190. printDivisionResult(a, c, b)

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


실행> scala -encoding MS949 testSyntheticDivision.scala 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 대한민국 라이센스에 따라 이용하실 수 있습니다.