다항식 p(x) 를 1차 다항식 ax - b 로 나눌 때의 몫과 나머지를 구하는 조립제법을
Python 언어로 구현해 보았다. 조립제법은 일명 Horner의 방법이라고도 불리우는데, 이는
x = a 에서 다항식 p(x)의 값 p(a)을 계산하는 가장 빠른 알고리즘이기도 하다.
p(x) = (ax - b)q(x) + r
여기서 r은 나머지이며 r = p(b/a) 이다. 또 q(x)는 몫이다.
[참고]
* 온라인으로 조립제법 표 만들기 손으로 계산하는 조립제법 표
* 온라인으로 구하는 다항식의 도함수: 조립제법을 이용한 다항식의 도함수
아래의 소스파일은 파일 testSyntheticDivision.jl 을 수정한 것이다.
python 대신 jython이나 IronPython 으로도 수정 없이 그대로 실행된다.
- ## Filename: testSyntheticDivision2.jl
- ##
- ## Purpose: Find the quotient and remainder when some polynomial is
- ## divided by a monic polynomial of the first degree.
- ##
- ## Execute: julia testSyntheticDivision2.jl 5 -4 7 8 6 8
- ##
- ## Date: 2013. 3. 7.
- # 사용법 표시
- function printUsage()
- println("사용법: python testSyntheticDivision2.py [제식의 계수] [피제식의 계수들]")
- println("조립제법(synthetic method)에 의한 다항식 나눗셈 결과를 보여준다.")
- end
- # 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
- # 전체 문자열 표시 너비는 매개변수 width 로 전달받아 처리한다.
- function simplify(v, width)
- t = string("", round(v,13))
- tlen = length(t)
- if tlen >1 && t[tlen-1:tlen] == ".0"
- t = t[1:tlen-2]
- end
- tlen = length(t)
- if width > 0
- if tlen < width
- t = string(" "[1: width - tlen], t)
- end
- end
- return t
- end
- # "/수" 표시하기
- # 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
- # 전체 문자열 표시 너비는 매개변수 width 로 전달받아 처리한다.
- function simplifyReciprocal(v, width)
- t = string("", round(v,13))
- tlen = length(t)
- if tlen > 2 && t[tlen-1:tlen] == ".0"
- t = t[1:tlen-2]
- end
- if width > 0
- if tlen < width
- t = string(" "[1: width - tlen], t)
- end
- end
- return t
- end
- # 다항식을 내림차순의 스트링 표현으로 반환
- function toPolyString(c)
- t = ""
- sc0 = simplify(c[1], 0)
- if length(c) > 2
- if sc0 == "1"
- t = string(t, "x^$(length(c)-1)")
- elseif sc0 == "-1"
- t = string(t, "-x^$(length(c)-1)")
- else
- t = string(t, sc0 , " x^$(length(c)-1)")
- end
- elseif length(c) == 2
- if sc0 == "1"
- t = string(t, "x")
- elseif sc0 == "-1"
- t = string(t, "-x")
- else
- t = string(t, sc0, " x")
- end
- elseif length(c) == 1
- t = string(t, sc0)
- end
- for i = 2: length(c)
- k = length(c) - i
- sc = simplify(c[i], 0)
- if k > 1
- if c[i] > 0.0
- if sc == "1"
- t = string(t, " + ", "x^$(k)")
- else
- t = string(t, " + ", sc, " x^$(k)")
- end
- elseif c[i] < 0.0
- if sc == "-1"
- t = string(t, " - ", "x^$(k)")
- else
- t = string(t, " - ", simplify(abs(c[i]), 0), " x^$(k)")
- end
- end
- elseif k == 1
- if c[i] > 0.0
- if sc == "1"
- t = string(t, " + ", "x")
- else
- t = string(t, " + ", sc, " x")
- end
- elseif c[i] < 0.0
- if sc == "-1"
- t = string(t, " - ", "x")
- else
- t = string(t, " - ", simplify(abs(c[i]), 0), " x")
- end
- end
- elseif k == 0
- if c[i] > 0.0
- t = string(t, " + ", sc)
- elseif c[i] < 0.0
- t = string(t, " - ", simplify(abs(c[i]), 0))
- end
- end
- end
- return t
- end
- # 다항식 나눗셈 결과를
- # (피제식) = (제식)(몫) + (나머지)
- # 형태로 출력
- function printDivisionResult(a, c, d, b)
- strLine = " " * toPolyString(c)
- println( strLine )
- strLine = " = ( " * toPolyString( [a[1], -a[2]] ) * " )"
- tmp = [0.0 for i = 1:(length(b) - 1) ]
- for i = 1:length(tmp)
- tmp[i] = b[i]
- end
- strLine = string(strLine, "( ", toPolyString(tmp), " )")
- r = d[length(d)]
- if r > 0.0
- strLine = string(strLine, " + ", simplify(r, 0))
- elseif r < 0.0
- strLine = string(strLine, " - ", simplify(abs(r), 0))
- end
- println( strLine )
- end
- # 조립제법 계산표 출력 함수
- function printSyntheticTable(a, c, s, d, q)
- strLine = " | "
- strLine = string(strLine, simplify(c[1], 8))
- for i = 2:length(c)
- strLine = string(strLine, " ", simplify(c[i], 8))
- end
- println( strLine )
- strLine = string(simplify(a[2], 8), " |")
- strLine = string(strLine, " ")
- strLine = string(strLine, simplify(s[2], 8))
- for i = 3:length(s)
- strLine = string(strLine, " ", simplify(s[i], 8))
- end
- println( strLine )
- strLine = " |"
- for i = 1:length(q)
- strLine = string(strLine, "----------")
- end
- println( strLine )
- strLine = " | "
- strLine = string(strLine, simplify(d[1], 8))
- for i = 2:length(d)
- strLine = string(strLine, " ", simplify(d[i], 8))
- end
- println( strLine )
- strLine = simplifyReciprocal(a[1], 10) * " | "
- strLine = string(strLine, simplify(q[1], 8))
- for i = 2:length(q) - 1
- strLine = string(strLine, " ", simplify(q[i], 8))
- end
- println( strLine )
- end
- # 실행 시작 지점
- if length(ARGS) < 4
- printUsage()
- exit(1)
- end
- ######################################################
- # 피제식은 c_0 x^n + c_1 x^(n -1) + ... + c_n
- # 제식은 a x - b
- a = [ float64(parse_float(ARGS[1]) ), - float64(parse_float(ARGS[2]) ) ]
- c = [0.0 for i=1:length(ARGS) - 2 ]
- s = [0.0 for i=1:length(ARGS) - 2 ]
- d = [0.0 for i=1:length(ARGS) - 2 ]
- b = [0.0 for i=1:length(ARGS) - 2 ]
- for i = 1:length(c)
- c[i] = float64(parse_float(ARGS[i + 2]))
- end
- ######################################################
- # 조립제법의 주요 부분
- s[1] = 0.0
- d[1] = c[1]
- b[1] = c[1] / a[1]
- for i in 2:length(c)
- s[i] = b[i-1]*a[2]
- d[i] = c[i] + s[i]
- b[i] = d[i] / a[1]
- end
- ######################################################
- # 몫의 계수와 나머지를 출력한다.
- print("몫의 계수는 ")
- for i = 1:length(b)-2
- print(simplify(b[i], 0), ", " )
- end
- print(simplify(b[length(b) - 1], 0), " ")
- println("이고, 나머지는 ", simplify(d[length(d)], 0), " 이다.")
- println("")
- ######################################################
- # 조립제법 표를 출력한다.
- printSyntheticTable(a, c, s, d, b)
- println()
- ######################################################
- # (피제식) = (제식) x (몫) + (나머지)
- printDivisionResult(a, c, d, b)
실행> julia testSyntheticDivision2.jl 5 -4 7 8 6 8
몫의 계수는 1.4, 2.72, 3.376 이고, 나머지는 21.504 이다.
| 7 8 6 8
4 | 5.6 10.88 13.504
|----------------------------------------
| 7 13.6 16.88 21.504
/5 | 1.4 2.72 3.376
7 x^3 + 8 x^2 + 6 x + 8
= ( 5 x - 4 )( 1.4 x^2 + 2.72 x + 3.376 ) + 21.504
'프로그래밍 > Julia' 카테고리의 다른 글
| Julia 언어로 역삼각함수, 역쌍곡선함수 값을 구하는 예제 (0) | 2013.03.07 |
|---|---|
| 감마함수(gamma function)의 값을 (유효수자 15자리 까지 정밀하게) 계산하는 Julia 언어 소스 (0) | 2013.03.07 |
| 숫자 맞추기 게임 with Julia (0) | 2013.03.06 |
| 손으로 계산하는 긴자리 곱셈표 만들기 with Julia (0) | 2013.03.05 |
| 문자열 거꾸로 하기 with Julia (0) | 2013.03.05 |