|
realroot_doc 0.1.1
|
|
realroot_doc 0.1.1
|
#include <solver_uv_continued_fraction.hpp>
Definition at line 149 of file solver_uv_continued_fraction.hpp.
| typedef K::data data |
Definition at line 159 of file solver_uv_continued_fraction.hpp.
| typedef K::floating floating |
Definition at line 154 of file solver_uv_continued_fraction.hpp.
| typedef K::rational FT |
Definition at line 152 of file solver_uv_continued_fraction.hpp.
| typedef K::integer integer |
Definition at line 151 of file solver_uv_continued_fraction.hpp.
| typedef polynomial< floating, with<MonomialTensor> > polynomial_floating |
Definition at line 158 of file solver_uv_continued_fraction.hpp.
| typedef K::Polynomial polynomial_integer |
Definition at line 156 of file solver_uv_continued_fraction.hpp.
| typedef polynomial< rational, with<MonomialTensor> > polynomial_rational |
Definition at line 157 of file solver_uv_continued_fraction.hpp.
| typedef K::rational rational |
Definition at line 153 of file solver_uv_continued_fraction.hpp.
| typedef K::root_t root_t |
Definition at line 155 of file solver_uv_continued_fraction.hpp.
| typedef K::integer RT |
Definition at line 150 of file solver_uv_continued_fraction.hpp.
| static void set_precision | ( | int | prec | ) | [inline, static] |
Definition at line 161 of file solver_uv_continued_fraction.hpp.
{K::set_precision(prec);}
| static void solve | ( | output & | sol, |
| const polynomial_integer & | f, | ||
| int | mult = 1 |
||
| ) | [inline, static] |
for (unsigned i = 0 ; i < isolating_intervals.size(); ++i) { if ( singleton( isolating_intervals[i]) ) { std::cout<<"XXX Singleton "<<isolating_intervals[i]<<std::endl; if ( lower( isolating_intervals[i]) == 0 ) continue;
polynomial_integer t= polynomial_integer("x")*denominator(lower(isolating_intervals[i])) - numerator( lower(isolating_intervals[i])); std::cout<<t<<" "<<p<<std::endl; polynomial_integer dummy; univariate::div_rem( dummy, p, t); std::cout<<dummy<<std::endl; //p = dummy; } }
Definition at line 298 of file solver_uv_continued_fraction.hpp.
References mmx::degree(), Seq< C, R >::size(), and continued_fraction_subdivision< K >::solve_positive().
Referenced by continued_fraction_subdivision< K >::solve().
{
// std::cout << __FUNCTION__ << " I "<<f<<std::endl;
Seq < root_t > isolating_intervals;
// Check if 0 is a root
int idx;
for (idx = 0; idx <= degree( f); ++idx) {
if ( f[idx] != 0 ) break;
}
polynomial_integer p;
if ( idx == 0 ) { p = f; }
else {
p= polynomial_integer(1,degree(f) - idx);
for (int j = idx; j <= degree(f); j++)
p[j-idx] = f[j];
}
// std::cout << "Solving: " << p << std::endl;
// Isolate the negative roots
// for (int i = 1; i <= degree(p); i+=2) p[i] *= -1;
solve_positive( isolating_intervals, p, false);
// Is 0 a root?
// std::cout << "ok negative" << std::endl;
if (idx != 0) isolating_intervals << root_t( 0, 0);
// for (int i = 1; i <= degree(p); i+=2) p[i] *= -1;
solve_positive( isolating_intervals, p, true);
// sort( isolating_intervals.begin(), isolating_intervals.end(), CompareFIT());
// std::cout << "ok positive" << std::endl;
// std::cout << "now p: " << p << ", #nr: " << isolating_intervals.size() << std::endl;
// std::cout << "Done...." << std::endl;
for (unsigned i = 0 ; i < isolating_intervals.size(); ++i)
{sol << isolating_intervals[i];}
// return sol;
}
| static void solve | ( | output & | sol, |
| const polynomial_rational & | f | ||
| ) | [inline, static] |
Definition at line 350 of file solver_uv_continued_fraction.hpp.
References continued_fraction_subdivision< K >::solve().
{
// std::cout << __FUNCTION__ << " R "<<f<<std::endl;
solve(sol, univariate::numer<polynomial_integer> (f));
}
| static void solve | ( | output & | sol, |
| const polynomial_floating & | f | ||
| ) | [inline, static] |
Definition at line 356 of file solver_uv_continued_fraction.hpp.
References mmx::degree(), and continued_fraction_subdivision< K >::solve().
{
// std::cout << __FUNCTION__ << " R "<<f<<std::endl;
polynomial_rational p(rational(0),degree(f));
for(int i=0;i<degree(f)+1;i++) {
p[i] = as<rational>(f[i]);
}
solve(sol,p);
}
| static void solve_homography | ( | output & | sol, |
| const data & | ID | ||
| ) | [inline, static] |
Definition at line 191 of file solver_uv_continued_fraction.hpp.
References IntervalData< RT, Poly >::b, IntervalData< RT, Poly >::d, mmx::div_x(), IntervalData< RT, Poly >::p, mmx::reverse(), mmx::reverse_shift_homography(), IntervalData< RT, Poly >::s, mmx::scale(), mmx::shift(), mmx::shift_by_1(), mmx::sign_variation(), mmx::sparse::swap(), and mmx::to_FT().
Referenced by continued_fraction_subdivision< K >::solve_positive().
{
// std::cout << __FUNCTION__ << " "<<ID.p<<std::endl;
polynomial_integer X(1,0,1);
//X[1] = RT(1); X[0]=RT(0);
int iters = 0;
const RT One(1);
FT Zero(0);
// std::cout << "Polynomial is " << ID.p << std::endl;
typedef data IntervalData;
std::stack< IntervalData > S;
S.push( ID );
while ( !S.empty() ) {
++iters;
IntervalData ID = S.top();
S.pop();
// std::cout << "Polynomial is " << ID.p << std::endl;
// Steps 3 - 4: Choose the method for computing the lower bound
//--------------------------------------------------------------------
RT a = K::lower_bound(ID.p);
// long k = Bd.lower_power_2( ID.p);
// std::cout<< "\t Lower bound is "<< a<< std::endl;
if ( a > RT(1) ) {
scale(ID,a);
a = RT(1);
}
//--------------------------------------------------------------------
// Step 5 //
if ( a >= RT(1) ) {
shift(ID, a);
// std::cout<<"Shift by "<<a<<std::endl;
if ( ID.p[0] == RT(0))
{
div_x(ID.p,1);
sol << root_t( to_FT( ID.b, ID.d), to_FT( ID.b, ID.d ));
}
ID.s = sign_variation( ID.p);
}
//int s= Kernel::init_shift(ID);
//--------------------------------------------------------------------
if ( K::is_empty(ID) )
continue;
else if( K::is_good(ID) ) {
sol << K::as_root(ID);
continue;
}
//--------------------------------------------------------------------
// Step 6
IntervalData I1;
shift_by_1( I1, ID);
unsigned long r = 0;
if (I1.p[0] == RT(0)) {
// std::cout << "Zero at end point"<<std::endl;;
sol << root_t( to_FT( I1.b, I1.d), to_FT(I1.b, I1.d) );
div_x(I1.p,1);
r = 1;
}
I1.s = sign_variation( I1.p);
IntervalData I2;
I2.s = ID.s - I1.s - r;
reverse_shift_homography(I2,ID);
// std::cout <<I1.s <<" "<<I2.s<<std::endl;
// Step 7;
if ( !K::is_empty(I2) && !K::is_good(I2) ) {
//p2 = p2( 1 / (x+1));
reverse( I2.p, ID.p);
shift_by_1(I2.p);
if ( I2.p[0] == 0) {
div_x(I2.p,1);
}
I2.s = sign_variation( I2.p);
}
// Step 8
if ( I1.s < I2.s ) {std::swap( I1, I2); }
// Step 9
if ( K::is_good(I1) ) {
// std::cout << "C) Sign variation: 1"<<std::endl;;
sol << K::as_root(I1);
} else if ( !K::is_empty(I1) ) {
S.push(I1); //IntervalData( I1.a, I1.b, I1.c, I1.d, I1.p, I1.s));
}
// Step 10
if ( K::is_good(I2) ) {
// std::cout << "D) Sign variation: 1"<<std::endl;;
sol << K::as_root(I2);
} else if ( !K::is_empty(I2) ) {
S.push(I2); //IntervalData( I2.a, I2.b, I2.c, I2.d, I2.p, I2.s));
}
} // while
// std::cout << "-------------------- iters: " << iters << std::endl;
return;
}
| static void solve_positive | ( | Seq< root_t > & | sol, |
| const polynomial_integer & | f, | ||
| bool | posneg | ||
| ) | [inline, static] |
Definition at line 164 of file solver_uv_continued_fraction.hpp.
References IntervalData< RT, Poly >::a, mmx::bound_root(), mmx::degree(), IntervalData< RT, Poly >::p, IntervalData< RT, Poly >::s, mmx::sign_variation(), and continued_fraction_subdivision< K >::solve_homography().
Referenced by continued_fraction_subdivision< K >::solve().
{
// std::cout << __FUNCTION__ << " "<<f<<" "<<posneg<<std::endl;
typedef typename K::data IntervalData;
IntervalData ID(1, 0, 0, 1, f, 0);
if (!posneg)
{
ID.a=-1;
for (int i = 1; i <= degree(f); i+=2) ID.p[i] *= -1;
}
ID.s = sign_variation(ID.p);
if ( K::is_empty(ID) ) { return; }
if ( K::is_good(ID) ) {
//std::cout << "A) Sign variation: 1"<<std::endl;;
FT B = bound_root( f, Cauchy<FT>());
if ( posneg )
sol << root_t( FT(0), B);
else sol << root_t( FT(0), FT(-B));
return;
}
solve_homography(sol,ID);
}
