34 #include "Base/Debug/Error.hh"
35 #include <MathAlgo/Laguerre.hh>
36 #include <Base/Common/CompareFloatingPoint.hh>
47 double frand(
double min = -10.0 ,
double max = 10.0)
51 const unsigned int res = 10000000;
52 unsigned int i=rand()%res;
53 double scale = ((double) i) / ((double) res);
54 double diff = tmax - tmin;
55 return(tmin+scale*diff);
59 unsigned int GetNumberOfBinaryOnes(
unsigned int val,
62 unsigned int bitmask = mask;
63 unsigned int temp = val;
64 unsigned int count = 0;
77 void GetIndexListFromBinaryZeros(
unsigned int val,
79 std::vector<unsigned int>& indices)
82 unsigned int bitmask = mask;
83 unsigned int temp = val;
84 unsigned int count = 0;
89 indices.push_back(count);
100 void CreateRandomPolynomial(
unsigned int degree,
101 vector< complex<double> >& coeffs,
102 vector< complex<double> >& roots)
104 BIASASSERT(degree>0);
107 std::vector<unsigned int> tempIDs;
108 unsigned int coeffidx ;
110 for(
unsigned int r=0; r<degree; r++)
112 roots.push_back(frand());
114 coeffs.resize(degree+1,complex<double>(0,0));
116 unsigned int maxiter = 1<<(degree);
117 unsigned int bitmask = maxiter - 1;
118 for(
unsigned int c=0; c<maxiter; c++)
120 GetIndexListFromBinaryZeros(c,bitmask,tempIDs);
121 coeffidx = GetNumberOfBinaryOnes(c,bitmask);
122 complex<double> someroots(1,0);
123 for(
unsigned int r=0;r<tempIDs.size();r++)
125 someroots = someroots * (-roots[tempIDs[r]]);
128 BIASASSERT(coeffidx<coeffs.size());
129 coeffs[coeffidx]= coeffs[coeffidx] + someroots;
134 struct complex_comp :
135 public binary_function< complex<double>, complex<double>, bool>
137 bool operator()(complex<double> x, complex< double> y)
139 if(x.real()<=y.real())
141 if(x.real()==y.real())
143 return(x.imag()<y.imag());
152 double MeanError(vector< complex<double> >& v1,
153 vector< complex<double> >& v2,
154 double& min,
double& max)
156 BIASASSERT(v1.size()==v2.size())
158 sort(v1.begin(),v1.end(),complex_comp());
159 sort(v2.begin(),v2.end(),complex_comp());
167 double tmax=0, tmin=10000000;
168 for(
unsigned int roo=0;roo<v1.size(); roo++)
170 double n = norm(v2[roo]-v1[roo]);
177 return (error/v1.size());
181 bool Equal(
const complex<double>& a,
182 const complex<double>& b)
184 return((
Equal(a.real(),b.real(),10e-12))&&
185 ((
Equal(a.imag(),b.imag(),10e-12))));
189 int main(
int argc,
char *argv[])
192 vector< complex<double> > realcoeff;
193 vector< complex<double> > expectedroots;
194 vector< complex<double> > roots;
196 unsigned int deg = 8;
200 double meanmeanerror=0;
201 double meanmin = 10000000;
205 for(
unsigned run=0; run<100; run++)
207 CreateRandomPolynomial(deg,realcoeff,expectedroots);
208 l.
Solve(realcoeff, roots);
211 err=MeanError(expectedroots,roots,min,max);
214 err=MeanError(expectedroots,roots,tmin,tmax);
215 if(min>tmin)min=tmin;
216 if(max<tmax)max=tmax;
218 cout<<err<<
" min: "<< min<<
" max: "<< max<<endl;
220 if(err<meanmin)meanmin=err;
221 if(err>meanmax)meanmax=err;
224 meanmeanerror /= 100.0;
225 cout<<
"-----------------------------------------------------------"<<endl;
226 cout<<
"min error (no mean):"<< min <<endl;
227 cout<<
"max error (no mean):"<< max <<endl;
228 cout<<
"mean min error:"<< meanmin <<endl;
229 cout<<
"mean max error:"<< meanmax <<endl;
230 cout<<
"mean mean error:"<< meanmeanerror <<endl;
int Solve(const std::vector< std::complex< double > > &coeffs, std::vector< std::complex< double > > &roots, const double eps=1.0e-14)
compute roots of a polynomial using the laguerre method
class encapsulating a laguerre solver for polynomials
bool Equal(const T left, const T right, const T eps)
comparison function for floating point values See http://www.boost.org/libs/test/doc/components/test_...