프로그래밍/Julia

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

Scripter 2013. 3. 3. 22:25

다항식 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)는 몫이다.

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


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


  1. ##  Filename: testSyntheticDivision.jl
  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:  julia testSyntheticDivision.jl -2 1 3 3 1
  7. ##
  8. ##      Date:  2013. 3. 4.
  10. # 사용법 표시
  11. function printUsage()
  12.     println("사용법: python testSyntheticDivision.py [수] [피제식의 계수들]")
  13.     println("조립제법(synthetic method)에 의한 다항식 나눗셈 결과를 보여준다.")
  14. end
  16. # 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
  17. # 전체 문자열 표시 너비는 매개변수 width 로 전달받아 처리한다.
  18. function simplify(v, width)
  19.     t = "$v"
  20.     tlen = length(t)
  21.     if tlen >1 && t[tlen-1:tlen] == ".0"
  22.         t = t[1:tlen-2]
  23.     end
  24.     if width > 0
  25.         if tlen < width
  26.             t = string( "              "[1: width - tlen], t)
  27.         end
  28.     end
  29.     return t
  30. end
  32. # 다항식을 내림차순의 스트링 표현으로 반환
  33. function toPolyString(c)
  34.     t = ""
  35.     sc0 = simplify(c[1], 0)
  36.     if length(c) > 2
  37.         if sc0 == "1"
  38.             t = string(t,  "x^$(length(c)-1)")
  39.         elseif sc0 == "-1"
  40.             t = string(t,  "-x^$(length(c)-1)")
  41.         else
  42.             t = string(t, sc0 , " x^$(length(c)-1)")
  43.         end
  44.     elseif length(c) == 2
  45.         if sc0 == "1"
  46.             t = string(t, "x")
  47.         elseif sc0 == "-1"
  48.             t = string(t, "-x")
  49.         else
  50.             t = string(t, sc0, " x")
  51.         end
  52.     elseif length(c) == 1
  53.         t = string(t, sc0)
  54.     end
  56.     for i = 2: length(c)
  57.         k = length(c)  - i
  58.         sc = simplify(c[i], 0)
  59.         if k > 1
  60.             if c[i] > 0.0
  61.                 if sc == "1"
  62.                     t = string(t, " + ", "x^$(k)")
  63.                 else
  64.                     t = string(t, " + ", sc, " x^$(k)")
  65.                 end
  66.             elseif c[i] < 0.0
  67.                 if sc == "-1"
  68.                     t = string(t, " - ", "x^$(k)")
  69.                 else
  70.                     t = string(t, " - ", simplify(abs(c[i]), 0), " x^$(k)")
  71.                 end
  72.             end
  73.         elseif k == 1
  74.             if c[i] > 0.0
  75.                 if sc == "1"
  76.                     t = string(t, " + ", "x")
  77.                 else
  78.                     t = string(t, " + ", sc, " x")
  79.                 end
  80.             elseif c[i] < 0.0
  81.                 if sc == "-1"
  82.                     t = string(t, " - ", "x")
  83.                 else
  84.                     t = string(t, " - ", simplify(abs(c[i]), 0), " x")
  85.                 end
  86.             end
  87.         elseif k == 0
  88.             if c[i] > 0.0
  89.                 t = string(t, " + ", sc)
  90.             elseif c[i] < 0.0
  91.                 t = string(t, " - ", simplify(abs(c[i]), 0))
  92.             end
  93.         end
  94.     end
  95.     return t
  96. end
  98. # 다항식 나눗셈 결과를
  99. #     (피제식) = (제식)(몫) + (나머지)
  100. # 형태로 출력
  101. function printDivisionResult(a, c, b)
  102.     strLine = string("  ", toPolyString(c))
  103.     println( strLine )
  105.     strLine = string("    = ( ", toPolyString( [1.0, -a] ), " )")
  106.     tmp = [0.0 for i = 1:(length(b) - 1) ]
  107.     for i = 1:length(tmp)
  108.         tmp[i] = b[i]
  109.     end
  110.     strLine = string(strLine, "( ", toPolyString(tmp), " )")
  111.     r = b[length(b)]
  112.     if r > 0.0
  113.         strLine = string(strLine, " + ", simplify(r), 0)
  114.     elseif r < 0.0
  115.         strLine = string(strLine, " - ", simplify(abs(r, 0)))
  116.     end
  117.     println( strLine )
  118. end
  120. # 조립제법 계산표 출력 함수
  121. function printSyntheticTable(a, c, s, q)
  122.     strLine = "       | "
  123.     strLine = string(strLine, simplify(c[1], 8))
  124.     for i = 2:length(c)
  125.         strLine = string(strLine, "  ", simplify(c[i], 8))
  126.     end
  127.     println( strLine )
  129.     strLine = string(simplify(a, 8), " |")
  130.     strLine = string(strLine, "         ")
  131.     strLine = string(strLine, simplify(s[2], 8))
  132.     for i = 3:length(s)
  133.         strLine = string(strLine, "  ", simplify(s[i], 8))
  134.     end
  135.     println( strLine )
  137.     strLine = "       |"
  138.     for i = 1:length(q)
  139.         strLine = string(strLine, "--------")
  140.     end
  141.     println( strLine )
  143.     strLine = "         "
  144.     strLine = string(strLine, simplify(q[1], 8))
  145.     for i = 2:length(q)
  146.         strLine = string(strLine, "  ", simplify(q[i], 8))
  147.     end
  148.     println( strLine )
  149. end
  152. # 실행 시작 지점
  153. if length(ARGS) < 3
  154.     printUsage()
  155.     exit(1)
  156. end
  158. ######################################################
  159. # 피제식은 c_0 x^n +  c_1 x^(n -1) + ... + c_n
  160. # 제식은 x -  a
  161. a = float64(parse_float(ARGS[1]) )
  162. c = [0.0 for i=1:length(ARGS) - 1 ]
  163. s = [0.0 for i=1:length(ARGS) - 1 ]
  164. b = [0.0 for i=1:length(ARGS) - 1 ]
  166. for i = 1:length(c)
  167.     c[i] = float64(parse_float(ARGS[i + 1]))
  168. end
  170. ######################################################
  171. # 조립제법의 주요 부분
  172. s[1] = 0.0
  173. b[1] = c[1]
  174. for i in 2:length(c)
  175.     s[i] = b[i-1]*a
  176.     b[i] = c[i] + s[i]
  177. end
  179. ######################################################
  180. # 몫의 계수와 나머지를 출력한다.
  181. print("몫의 계수는 ")
  182. for i = 1:length(b)-2
  183.     print(simplify(b[i], 0), ", " )
  184. end
  185. print(simplify(b[length(b) - 1], 0), " ")
  186. print("이고, 나머지는 ", simplify(b[length(b)], 0), " 이다.")
  187. println("")
  189. ######################################################
  190. # 조립제법 표를 출력한다.
  191. printSyntheticTable(a, c, s, b)
  192. println("")
  194. ######################################################
  195. # (피제식) = (제식) x (몫) + (나머지)
  196. printDivisionResult(a, c, b)



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


 

'프로그래밍 > Julia' 카테고리의 다른 글

대화형 모드의 진법(radix) 변환 예제 with Julia  (0) 2013.03.05
황금비율(golden ratio) 구하기 with Julia  (0) 2013.03.05
80컬럼 컨솔에 19단표 출력하기 예제 for Julia  (0) 2013.03.03
(최대공약수 구하기) while... 반복문 예제 for Julia  (0) 2013.03.03
if...else... 조건문 사용 예제 for Julia  (0) 2013.03.03

'프로그래밍/Julia'의 다른글

  • 현재글조립제법(Horner의 방법) 예제 for Julia

관련글

티스토리툴바