realroot_doc 0.1.1
Static Public Member Functions
HongBound< RT > Struct Template Reference

#include <univariate_bounds.hpp>

List of all members.

Static Public Member Functions

Detailed Description

template<class RT>
struct mmx::HongBound< RT >

A lower bound based upon the upper bound given by Hong. This should be the best possible, since Hong's bound is better than Kioustelidis' bound. The problem is that it is a (n^2) procedure.

Definition at line 375 of file univariate_bounds.hpp.

Member Function Documentation

static RT lower_bound ( const Poly &  f) [inline, static]

Definition at line 378 of file univariate_bounds.hpp.

References mmx::abs(), mmx::bit_size(), mmx::degree(), and mmx::sign().

    {
      using univariate::degree;

      unsigned deg = degree(f);
    
      long lB=0, gB=0;
      bool localBoundSet = false, globalBoundSet = false;
      long temp, q;
      int s = sign(f[0]);
      //std::cout << "f[0]= " << f[0] << std::endl;
      for(int i= deg; i > 0; i--){
        //std::cout << "f["<< i << "]" << " = " << f[i] << std::endl;
        if(sign(f[i]) * s < 0){
          for(int k=i-1; k >= 0; k--){
            if(sign(f[k]) * s > 0){
              temp = bit_size( RT(f[i]) ) - bit_size( RT(f[k]) ) - 1;
              q = temp /(i-k);
              if(!localBoundSet || lB > q + 2){// Choose the minimum among localBounds
                localBoundSet = true;
                lB = q+2;
              }
            }
          }
          localBoundSet = false;
          if(!globalBoundSet || gB < lB){// Choose the maximum among globalBounds
            globalBoundSet = true;
            gB = lB;
          }
        }
        //std::cout << "Cout gb after " << i << " loop = "<< gB << std::endl;
      }
      if ( gB+1 < 0 ) return pow2<RT>( abs( gB+1) );
      return 0;
    }
The documentation for this struct was generated from the following file: