ehsan_faal
چهارشنبه 04 شهریور 1394, 18:42 عصر
سلام دوستان.
من برای تقسیم دو چند جمله ای به هم در حالتی که صرایب میتونن از نوع دابل یا مختلط باشن قصد دارم این الگوریتم رو در زبان ++C بنویسم:
degree(P):
return the index of the last non-zero element of P;
if all elements are 0, return -∞
polynomial_long_division(N, D) returns (q, r):
// N, D, q, r are vectors
if degree(D) < 0 then error
if degree(N) ≥ degree(D) then
q ← 0
while degree(N) ≥ degree(D)
d ← D shifted right by (degree(N) - degree(D))
q(degree(N) - degree(D)) ← N(degree(N)) / d(degree(d))
// by construction, degree(d) = degree(N) of course
d ← d * q(degree(N) - degree(D))
N ← N - d
endwhile
r ← N
else
q ← 0
r ← N
endif
return (q, r)
که یه مثال از روند مرحله به مرحله این الگوریتم هم میشه این:
0 1 2 3
----------------------
N: -42 0 -12 1 degree = 3
D: -3 1 0 0 degree = 1
d(N) - d(D) = 2, so let's shift D towards right by 2:
N: -42 0 -12 1
d: 0 0 -3 1
N(3)/d(3) = 1, so d is unchanged. Now remember that "shifting by 2"
is like multiplying by x2, and the final multiplication
(here by 1) is the coefficient of this monomial. Let's store this
into q:
0 1 2
---------------
q: 0 0 1
now compute N - d, and let it be the "new" N, and let's loop
N: -42 0 -9 0 degree = 2
D: -3 1 0 0 degree = 1
d(N) - d(D) = 1, right shift D by 1 and let it be d
N: -42 0 -9 0
d: 0 -3 1 0 * -9/1 = -9
q: 0 -9 1
d: 0 27 -9 0
N ← N - d
N: -42 -27 0 0 degree = 1
D: -3 1 0 0 degree = 1
looping again... d(N)-d(D)=0, so no shift is needed; we
multiply D by -27 (= -27/1) storing the result in d, then
q: -27 -9 1
and
N: -42 -27 0 0 -
d: 81 -27 0 0 =
N: -123 0 0 0 (last N)
d(N) < d(D), so now r ← N, and the result is:
0 1 2
-------------
q: -27 -9 1 → x2 - 9x - 27
r: -123 0 0 → -123
کدهایی که من نوشتم اینان:
/*
* PolynomialDegree.h
*
* Created on: Aug 26, 2015
* Author: Ehsan
*/
#ifndef POLYDIV_POLYNOMIALDEGREE_H_
#define POLYDIV_POLYNOMIALDEGREE_H_
#include "armadillo"
using namespace arma;
namespace Coupler{
template<typename T>
auto getDegree(const arma::Col<T>& input)->size_t {
size_t degree = input.n_elem;
vec query = arma::real(input);
while (query(input.n_elem - degree) == 0) {
degree--;
}
return --degree;
}
}
#endif /* POLYDIV_POLYNOMIALDEGREE_H_ */
و
/*
* ShiftPolynomial.h
*
* Created on: Aug 24, 2015
* Author: Ehsan
*/
#ifndef POLYDIV_SHIFTPOLYNOMIAL_H_
#define POLYDIV_SHIFTPOLYNOMIAL_H_
#include "armadillo"
using namespace arma;
namespace Coupler{
template<typename T>
auto shiftPolynomial(const Col<T>& input, const int& howMuch)->Col<T> {
if (howMuch > 0) {
Col<T> result(input.n_elem + howMuch, fill::none);
result.rows(0, howMuch - 1).zeros();
result.rows(howMuch, result.n_elem - 1) = input;
return result;
}
return input;
}
}
#endif /* POLYDIV_SHIFTPOLYNOMIAL_H_ */
و
/*
* PolyDiv.h
*
* Created on: Aug 26, 2015
* Author: Ehsan
*/
#ifndef POLYDIV_POLYDIV_H_
#define POLYDIV_POLYDIV_H_
#include "PolynomialDegree.h"
#include "ShiftPolynomial.h"
namespace Coupler{
template<typename T1 ,typename T2>
auto polydiv(const Col<T1>& Nu,const Col<T2>& De)->Col<T1>{
auto Ndegree = Coupler::getDegree(Nu), Ddegree = Coupler::getDegree(De);
Col<T1> N{flipud(Nu)};
Col<T2> D{flipud(De)};
Col<T1> Q((Ndegree - Ddegree + 1),fill::zeros);
size_t smallD_Degree = 0;
while (Ndegree >= Ddegree) {
Col<T1> smallD = conv_to<Col<T1>>::from(Coupler::shiftPolynomial(D, (Ndegree - Ddegree)));
auto index = Ndegree - Ddegree;
smallD_Degree = Coupler::getDegree(smallD);
Q(index) = N(Ndegree) / smallD(smallD_Degree);
smallD *= Q(index);
N -= smallD;
Ndegree = Coupler::getDegree(Col<T1>{flipud(N)});
}
return flipud(Q);
}
}
#endif /* POLYDIV_POLYDIV_H_ */
و نهایتا تابع main :
#include <iostream>
#include "armadillo"
#include "PolyDiv.h"
using namespace arma;
using namespace std;
auto main()->int{
cx_vec D{{-9.074e-001,-3.645e-015},
{2.768e+001,-1.051e-013},
{-4.159e+001,-1.528e-013},
{+4.167e+001,+1.560e-013},
{+2.751e+001,+9.958e-014},
{+1.000e+000,+3.641e-015}};
vec N{-1,0,1};
cout<<Coupler::polydiv(D,N)<<endl;
return 0;
}
تنها تفاوتی که توی کد من با این الگوریتم هست اینه که اون برای محاسبه درجه و کلا کار با چند جمله ایها درجه ها رو از کم به زیاد در نظر گرفته یعنی اولین جمله درجه صفر داره و ..
ولی برای من چون ورودیها رو از یه سری تابع دیگه میگیرم و به تابع getDegree در جاهای دیگه هم نیاز دارم پس ترتیب چندجمله ایهام رو عکس در نظر گرفتم.
نمیدونم چرا این کد انگار توی یه حلقه بینهایت میفته و به محض فراخوانی تابع polydiv برنامه دیگه تموم نمیشه.
کسی میتونه راهنماییم کنه؟
لینک صفحه حاوی الگوریتم (http://rosettacode.org/wiki/Polynomial_long_division#C.2B.2B)
با تشکر
من برای تقسیم دو چند جمله ای به هم در حالتی که صرایب میتونن از نوع دابل یا مختلط باشن قصد دارم این الگوریتم رو در زبان ++C بنویسم:
degree(P):
return the index of the last non-zero element of P;
if all elements are 0, return -∞
polynomial_long_division(N, D) returns (q, r):
// N, D, q, r are vectors
if degree(D) < 0 then error
if degree(N) ≥ degree(D) then
q ← 0
while degree(N) ≥ degree(D)
d ← D shifted right by (degree(N) - degree(D))
q(degree(N) - degree(D)) ← N(degree(N)) / d(degree(d))
// by construction, degree(d) = degree(N) of course
d ← d * q(degree(N) - degree(D))
N ← N - d
endwhile
r ← N
else
q ← 0
r ← N
endif
return (q, r)
که یه مثال از روند مرحله به مرحله این الگوریتم هم میشه این:
0 1 2 3
----------------------
N: -42 0 -12 1 degree = 3
D: -3 1 0 0 degree = 1
d(N) - d(D) = 2, so let's shift D towards right by 2:
N: -42 0 -12 1
d: 0 0 -3 1
N(3)/d(3) = 1, so d is unchanged. Now remember that "shifting by 2"
is like multiplying by x2, and the final multiplication
(here by 1) is the coefficient of this monomial. Let's store this
into q:
0 1 2
---------------
q: 0 0 1
now compute N - d, and let it be the "new" N, and let's loop
N: -42 0 -9 0 degree = 2
D: -3 1 0 0 degree = 1
d(N) - d(D) = 1, right shift D by 1 and let it be d
N: -42 0 -9 0
d: 0 -3 1 0 * -9/1 = -9
q: 0 -9 1
d: 0 27 -9 0
N ← N - d
N: -42 -27 0 0 degree = 1
D: -3 1 0 0 degree = 1
looping again... d(N)-d(D)=0, so no shift is needed; we
multiply D by -27 (= -27/1) storing the result in d, then
q: -27 -9 1
and
N: -42 -27 0 0 -
d: 81 -27 0 0 =
N: -123 0 0 0 (last N)
d(N) < d(D), so now r ← N, and the result is:
0 1 2
-------------
q: -27 -9 1 → x2 - 9x - 27
r: -123 0 0 → -123
کدهایی که من نوشتم اینان:
/*
* PolynomialDegree.h
*
* Created on: Aug 26, 2015
* Author: Ehsan
*/
#ifndef POLYDIV_POLYNOMIALDEGREE_H_
#define POLYDIV_POLYNOMIALDEGREE_H_
#include "armadillo"
using namespace arma;
namespace Coupler{
template<typename T>
auto getDegree(const arma::Col<T>& input)->size_t {
size_t degree = input.n_elem;
vec query = arma::real(input);
while (query(input.n_elem - degree) == 0) {
degree--;
}
return --degree;
}
}
#endif /* POLYDIV_POLYNOMIALDEGREE_H_ */
و
/*
* ShiftPolynomial.h
*
* Created on: Aug 24, 2015
* Author: Ehsan
*/
#ifndef POLYDIV_SHIFTPOLYNOMIAL_H_
#define POLYDIV_SHIFTPOLYNOMIAL_H_
#include "armadillo"
using namespace arma;
namespace Coupler{
template<typename T>
auto shiftPolynomial(const Col<T>& input, const int& howMuch)->Col<T> {
if (howMuch > 0) {
Col<T> result(input.n_elem + howMuch, fill::none);
result.rows(0, howMuch - 1).zeros();
result.rows(howMuch, result.n_elem - 1) = input;
return result;
}
return input;
}
}
#endif /* POLYDIV_SHIFTPOLYNOMIAL_H_ */
و
/*
* PolyDiv.h
*
* Created on: Aug 26, 2015
* Author: Ehsan
*/
#ifndef POLYDIV_POLYDIV_H_
#define POLYDIV_POLYDIV_H_
#include "PolynomialDegree.h"
#include "ShiftPolynomial.h"
namespace Coupler{
template<typename T1 ,typename T2>
auto polydiv(const Col<T1>& Nu,const Col<T2>& De)->Col<T1>{
auto Ndegree = Coupler::getDegree(Nu), Ddegree = Coupler::getDegree(De);
Col<T1> N{flipud(Nu)};
Col<T2> D{flipud(De)};
Col<T1> Q((Ndegree - Ddegree + 1),fill::zeros);
size_t smallD_Degree = 0;
while (Ndegree >= Ddegree) {
Col<T1> smallD = conv_to<Col<T1>>::from(Coupler::shiftPolynomial(D, (Ndegree - Ddegree)));
auto index = Ndegree - Ddegree;
smallD_Degree = Coupler::getDegree(smallD);
Q(index) = N(Ndegree) / smallD(smallD_Degree);
smallD *= Q(index);
N -= smallD;
Ndegree = Coupler::getDegree(Col<T1>{flipud(N)});
}
return flipud(Q);
}
}
#endif /* POLYDIV_POLYDIV_H_ */
و نهایتا تابع main :
#include <iostream>
#include "armadillo"
#include "PolyDiv.h"
using namespace arma;
using namespace std;
auto main()->int{
cx_vec D{{-9.074e-001,-3.645e-015},
{2.768e+001,-1.051e-013},
{-4.159e+001,-1.528e-013},
{+4.167e+001,+1.560e-013},
{+2.751e+001,+9.958e-014},
{+1.000e+000,+3.641e-015}};
vec N{-1,0,1};
cout<<Coupler::polydiv(D,N)<<endl;
return 0;
}
تنها تفاوتی که توی کد من با این الگوریتم هست اینه که اون برای محاسبه درجه و کلا کار با چند جمله ایها درجه ها رو از کم به زیاد در نظر گرفته یعنی اولین جمله درجه صفر داره و ..
ولی برای من چون ورودیها رو از یه سری تابع دیگه میگیرم و به تابع getDegree در جاهای دیگه هم نیاز دارم پس ترتیب چندجمله ایهام رو عکس در نظر گرفتم.
نمیدونم چرا این کد انگار توی یه حلقه بینهایت میفته و به محض فراخوانی تابع polydiv برنامه دیگه تموم نمیشه.
کسی میتونه راهنماییم کنه؟
لینک صفحه حاوی الگوریتم (http://rosettacode.org/wiki/Polynomial_long_division#C.2B.2B)
با تشکر