Polynomial Model
다항식 모델
- 다항식을 표현 및 처리할 수 있는 ADT를 구현한다.
Main Specification (주요 기능)
1. Basic Operations
- 다항식의 앞에 '+' 혹은 '-'를 위치시켜 부호를 유지하거나 반전(Negation)시키는 Operator들이 Overloading되어 있다.
- 다항식끼리의 덧셈, 뺄셈, 곱셈에 대한 Operator들이 Overloading되어 있다.
2. Mathematical Functions
- 1차, 2차, 3차식에 한하여, \(f(x) = 0\) (Equation)에 대한 해를 출력하는 Member Function \(\texttt{findRoot()}\)가 구현되어 있다.
- 2차식, 3차식에 한하여, Discriminant(판별식)의 값을 출력하는 Member Function \(\texttt{discriminant()}\)가 구현되어 있다.
* Miscellaneous
- 계산과정에서 계수가 0이 되는 항은 따로 표현되지 않고 사라진다.
- 다항식을 표현한 String을 \(\texttt{polynomial}\) Type으로 변환하는 Private Member Function \(\texttt{convert()}\)가 구현되어 있다.
- 사용자가 다항식을 어떠한 방식으로 입력해도,
유효한 입력에 한하여 정상적인 \(\texttt{polynomial}\) Data Type으로 입력받을 수 있어야 한다.
(이 또한, \(\texttt{convert()}\)가 여러가지 입력에 대비하여 \(\texttt{polynomial}\) Type으로 변환한다.)
\(\texttt{polynomial}\) Implementation
* GitHub (URL)
Mathematical Details
1. Discriminant (URL)
| Discriminant | for Quartic Polynomial (\(ax^4 + bx^3 + cx^2 + dx + e\)) |
for Cubic Polynomial (\(ax^3 + bx^2 + cx + d\)) |
for Quadratic Polynomial (\(ax^2 + bx + c\)) |
D |
\(256a^3e^3 - 192a^2bde^2\\- 128a^2c^2e^2 + 144a^2cd^2e \\- 27a^2d^4 + 144ab^2ce^2\\- 6ab^2d^2e - 80abc^2de\\+ 18abcd^3 + 16ac^4e\\- 4ac^3d^2 - 27b^4e^2\\+ 18b^3cde - 4b^3d^3\\- 4b^2c^3e + b^2c^2d^2\) | \(b^2c^2 - 4ac^3\\- 4b^3d - 27a^2d^2 + 18abcd\) | \(b^2 - 4ac\) |
| D > 0 | 근 전체가 실근 혹은 근 전체가 허근 |
세 개의 서로 다른 실근 | 두 개의 서로 다른 실근 |
| D = 0 | 적어도 두 근 이상이 서로 같음 | 세 개의 서로 같은 실근 (삼중근) 서로 같은 두 실근과 다른 한 실근 (중근) |
서로 같은 두 실근 (중근) |
| D < 0 | 두 실근과 두 켤레 복소근 | 서로 다른 두 허근과 한 실근 | 서로 다른 두 허근 |
2. Real Root (URL)
| for Cubic Equation (\(ax^3 + bx^2 + cx + d\)) |
for Quadratic Equation (\(ax^2 + bx + c\)) |
\(x = {-b \pm \sqrt{b^2-4ac} \over 2a}\) |
\(x_k = -{1 \over 3a} (b + \xi^kC + {\Delta_0 \over \xi^kC})\\ k \in \{0, 1, 2\}\) |
* \(\Delta_0 = b^2 - 3ac\) * \(\Delta_1 = 2b^3 - 9abc + 27a^2d\) * \(C = \sqrt[3]{\Delta_1 \pm \sqrt{\Delta_1^2-4\Delta_0^3} \over 2}\) * \(\xi = {-1 + \sqrt{-3} \over 2}\) |
Performance
Reference: Fundamentals of Data Structure in C++ (Horowitz, Sahni, Mehta 저, Silicon Press, 2006)
