조립제법(Horner의 방법) 예제 with Go

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

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

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

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


아래의 소스파일은 go run 명령을 사용하면 컴파일 과정 없이 그대로 실행된다.
(실행 예:  go run testSyntheticDivision.go 1 2 3 4 5  )

1. /*
2.  *  Filename: testSyntheticDivision.go
3.  *
4.  *  Purpose:  Find the quotient and remainder when some polynomial is
5.  *            divided by a monic linear polynomial.
6.  *
7.  *  Execute:  go run testSyntheticDivision.go -2 1 3 3 1
8.  *
9.  *  or
10.  *
11.  *  Compile:  go build testSyntheticDivision.go
12.  *  Execute:  ./testSyntheticDivision -2 1 3 3 1
13.  */
15. package main
17. import (
18.     "fmt"
19.     "os"
20.     "strconv"
21.     "math"
22. )
24. func print(str string) {
25.     fmt.Printf("%s", str);
26. }
28. func println(str string) {
29.     fmt.Printf("%s\n", str);
30. }
32. // 사용법 표시
33. func printUsage() {
34.      /// println("사용법: testSyntheticDivision [수] [피제식의 계수들]");
35.      /// println("조립제법(synthetic method)에 의한 다항식 나눗셈 결과를 보여준다.");
36.      println("Usage: testSyntheticDivision [number] [coefficients of dividend]");
37.      println("Show the result of synthetic division.");
38. }
40. // 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
41. // 전체 문자열 표시 너비는 매개변수 width 로 전달받아 처리한다.
42. func simplify(v float64, width int) string {
43.     var n int
44.     var slen int
45.     var t string = "                               ";
46.     var tmp string = "                               ";
47.     t = fmt.Sprintf("%g", v);
48.     n = len(t);
49.     if (n > 2) && (t[n - 2] == '.') && (t[n - 1] == '0') {
50.         t = t[0:n-2]
51.     }
52.     slen = len(t);
53.     tmp =  t
54.     if (slen < width) {
55.         t = "               "
56.         t = t[0:width - slen]
57.         t = t + tmp
58.     }
59.     return t
60. }
62. // 다항식을 내림차순의 문자열로로 반환하는 함수
63. func toPolyString(c []float64, size int) string {
64.     var SIZE int = size;
65.     var i int;
66.     var t string = ""
67.     var tmp string
68.     var pc string = simplify(c[0], -1);
69.     var pci string
71.     if SIZE > 2 {
            if (len(pc) == 1 && pc[0] == '1') {
72.             t = fmt.Sprintf("x^%d", SIZE - 1);
73.         } else if (len(pc) == 2 && pc[0] == '-' && pc[1] == '1') {
74.             t = fmt.Sprintf("-x^%d", SIZE - 1);
75.         } else {
76.             t = fmt.Sprintf("%s x^%d", simplify(c[0], -1), SIZE - 1);
77.         }
78.     } else if SIZE == 2 {
79.         if (len(pc) == 1 && pc[0] == '1') {
80.             t = "x"
81.         } else if (len(pc) == 2 && pc[0] == '-' && pc[1] == '1') {
82.             t = "-x"
83.         } else {
84.             t = fmt.Sprintf("%s x", simplify(c[0], -1));
85.         }
86.     } else if SIZE == 1 {
87.         t = fmt.Sprintf("%s", simplify(c[0], -1));
88.     }
90.     for i = 1; i < SIZE; i++ {
91.         pci = simplify(c[i], -1);
92.         if SIZE - 1 - i > 1 {
93.             if c[i] > 0.0 {
94.                 if len(pci) == 1 && pci[0] == '1' {
95.                     tmp = fmt.Sprintf(" + x^%d", SIZE - 1 - i);
96.                     t += tmp
97.                 } else {
98.                     tmp = fmt.Sprintf(" + %s x^%d", simplify(c[i], -1), SIZE - 1 - i);
99.                     t += tmp
100.                 }
101.             } else if c[i] < 0.0 {
102.                 if len(pci) == 2 && pci[0] == '-' && pci[1] == '1' {
103.                     tmp = fmt.Sprintf(" - x^%d", SIZE - 1 - i);
104.                     t += tmp
105.                 } else {
106.                     tmp = fmt.Sprintf(" - %s x^%d", simplify(math.Abs(c[i]), -1), SIZE - 1 - i);
107.                     t += tmp
108.                 }
109.             }
110.         } else if SIZE - 1 - i == 1 {
111.             if c[i] > 0.0 {
112.                 if len(pci) == 1 && pci[0] == '1' {
113.                     t += " + x"
114.                 } else {
115.                     tmp = fmt.Sprintf(" + %s x", simplify(c[i], -1));
116.                     t += tmp
117.                 }
118.             } else if c[i] < 0.0 {
119.                 if len(pci) == 2 && pci[0] == '-' && pci[1] == '1' {
120.                     t += " - x"
121.                 } else {
122.                     tmp = fmt.Sprintf(" - %s x", simplify(math.Abs(c[i]), -1));
123.                     t += tmp
124.                 }
125.             }
126.         } else if SIZE - 1 - i == 0 {
127.             if c[i] > 0.0 {
128.                 tmp = fmt.Sprintf(" + %s", simplify(c[i], -1));
129.                 t += tmp
130.             } else if (c[i] < 0.0) {
131.                 tmp = fmt.Sprintf(" - %s", simplify(math.Abs(c[i]), -1));
132.                 t += tmp
133.             }
134.         }
135.     }
136.     return t
137. }
139. // 다향식 나눗셈 결과를
140. //     (피제식) = (제식)(몫) + (나마지)
141. // 형태로 출력
142. func printDivisionResult(a float64, c []float64, b []float64, size int) {
143.     var SIZE int = size;
144.     var i int
145.     var r float64
146.     var monic []float64 = []float64 { 1.0, 0.0 };
148.     print("  ");
149.     print(toPolyString(c, SIZE));
150.     println("");
151.     print("    = ( ");
152.     monic[1] = -a;
153.     print(toPolyString(  monic, 2 ));
154.     print(" )")
156.     var pTmpPoly []float64 = make([]float64, SIZE);
157.     for i = 0; i < SIZE - 1; i++ {
158.         pTmpPoly[i] = b[i];
159.     }
160.     print("( ");
161.     print(toPolyString(pTmpPoly, SIZE - 1));
162.     print(" )");
164.     r = b[SIZE - 1];
165.     if r > 0.0 {
166.         print(" + ");
167.         print(simplify(r, -1));
168.     } else if (r < 0.0) {
169.         print(" - ");
170.         print(simplify(math.Abs(r), -1));
171.     }
172.     println("");
173. }
175. // 조립제법 계산표 출력 함수
176. func printSyntheticTable(a float64, c []float64, s []float64, q []float64, size int) {
177.     var SIZE int = size;
178.     var i int
179.     print("       | ");
180.     print(simplify(c[0], 6));
181.     for i = 1; i < SIZE; i++ {
182.         print("  ");
183.         print(simplify(c[i], 6));
184.     }
185.     println("");
187.     print(simplify(a, 6));
188.     print(" | "); 
189.    print("        ");
190.     print(simplify(s[1], 6));
191.     for i = 2; i < SIZE; i++ {
192.         print("  ");
193.         print(simplify(s[i], 6));
194.     }
195.     println("");
197.     print("       |-");
198.     for i = 0; i < SIZE; i++ {
199.         print("--------");
200.     }
201.     println("");
203.     print("         ");
204.     print(simplify(q[0], 6));
205.     for i = 1; i < SIZE; i++ {
206.         print("  ");
207.         print(simplify(q[i], 6));
208.     }
209.     println("");
210. }
212. // Go 언어 프로그램의 실행 시작 지점
213. func main() {
214.     var i int
215.     var SIZE = len(os.Args) - 2
216.     var a float64
217.     var c []float64 = make([]float64, SIZE + 2)
218.     var s []float64 = make([]float64, SIZE + 2)
219.     var b []float64 = make([]float64, SIZE + 2)
221.     if len(os.Args) < 4 {
222.         printUsage()
223.         return
224.     }
226.     //////////////////////////////////////////////////////
227.     // 피제식은 c_0 x^n +  c_1 x^(n -1) + ... + c_n
228.     // 제식은 x -  a
229.     a, _ = strconv.ParseFloat(os.Args[1], 64)
231.     for i = 0; i < SIZE; i++ {
232.         c[i], _ = strconv.ParseFloat(os.Args[i + 2], 64)
233.     }
235.     //////////////////////////////////////////////////////
236.     // 조립제법의 주요 부분
237.     s[0] = 0.0;
238.     b[0] = c[0];
239.     for i = 1; i < SIZE; i++ {
240.         s[i] = b[i-1]*a;
241.         b[i] = c[i] + s[i];
242.     }
244.     //////////////////////////////////////////////////////
245.     // 몫의 계수와 나머지를 출력한다.
246.     /// print("몫의 계수는 ");
247.     print("The coefficients of the quotient are ");
248.     for i = 0; i < SIZE - 2; i++ {
249.         print(simplify(b[i], -1));
250.         print(", ");
251.     }
253.     print(simplify(b[SIZE - 2], -1));
254.     // print(" 이고, 나머지는 ");
255.     print("\nand the remainder is ");
256.     print(simplify(b[SIZE - 1], -1));
257.     /// println(" 이다.");
258.     println(".");
259.     println("");
261.     //////////////////////////////////////////////////////
262.     // 조립제법 표를 출력한다.
263.     printSyntheticTable(a, c, s, b, SIZE);
264.     println("");
266.     //////////////////////////////////////////////////////
267.     // (피제식) = (제식) x (몫) + (나머지)
268.     printDivisionResult(a, c, b, SIZE);
269. }

실행> go run testSyntheticDivision.go 1 2 3 4 5
The coefficients of the quotient are 2, 5, 9
and the remainder is 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

 

또는

 

컴파일> go build testSyntheticDivision.go

실행> ./testSyntheticDivision 1 2 3 4 5
The coefficients of the quotient are 2, 5, 9
and the remainder is 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