include/algebramix/polynomial_balanced.hpp

Go to the documentation of this file.

/******************************************************************************
* MODULE     : polynomial_balanced.hpp
* DESCRIPTION: degree balancing
* COPYRIGHT  : (C) 2008  Gregoire Lecerf
*******************************************************************************
* This software falls under the GNU general public license and comes WITHOUT
* ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for more details.
* If you don't have this file, write to the Free Software Foundation, Inc.,
* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
******************************************************************************/

#ifndef __MMX__POLYNOMIAL_BALANCED__HPP
#define __MMX__POLYNOMIAL_BALANCED__HPP

namespace mmx {
#define TMPL template<typename C>

/******************************************************************************
* Balanced algorithms for polynomials
******************************************************************************/

template<typename V>
struct polynomial_balanced: public V {
  typedef typename V::Vec Vec;
  typedef typename V::Naive Naive;
  typedef polynomial_balanced<typename V::Positive> Positive;
  typedef polynomial_balanced<typename V::No_simd> No_simd;
  typedef polynomial_balanced<typename V::No_thread> No_thread;
  typedef polynomial_balanced<typename V::No_scaled> No_scaled;
};

template<typename F, typename V, typename W>
struct implementation<F,V,polynomial_balanced<W> >:
  public implementation<F,V,W> {};

/******************************************************************************
* Multiplication
******************************************************************************/

template<typename V, typename W>
struct implementation<polynomial_multiply,V,polynomial_balanced<W> >:
  public implementation<polynomial_linear,V>
{
  typedef implementation<vector_linear,V> Vec;
  typedef implementation<polynomial_linear,W> Pol;
  typedef implementation<polynomial_multiply,W> Fallback;

TMPL static inline void
mul (C* dest, const C* s1, const C* s2, nat n1, nat n2) {
  if (n1 == 0 && n2 == 0)
    return;
  if (n1 == 0 || n2 == 0) {
    Pol::clear (dest, n1+n2-1);
    return;
  }
  if (n1 == n2) {
    Fallback::mul (dest, s1, s2, n1, n2);
    return;
  }
  nat n= n1+n2-1;
  Pol::clear (dest, n);
  if (n1 < n2) {
    nat l= aligned_size<C,V> (2*n1-1);
    C* temp= mmx_new<C> (l);
    while (n2 > 0) {
      nat n3= min (n1, n2);
      mul (temp, s1, s2, n1, n3);
      Vec::add (dest, temp, n1+n3-1);
      n2 -= n3; s2 += n3; dest += n3;
    }
    mmx_delete<C> (temp, l);
  }
  else {
    nat l= aligned_size<C,V> (2*n2-1);
    C* temp= mmx_new<C> (l);
    while (n1 > 0) {
      nat n3= min (n1, n2);
      mul (temp, s1, s2, n3, n2);
      Vec::add (dest, temp, n2+n3-1);
      n1 -= n3; s1 += n3; dest += n3;
    }
    mmx_delete<C> (temp, l);
  }
}

TMPL static inline void
square (C* dest, const C* s, nat n) {
  Fallback::square (dest, s, n);
}

}; // implementation<polynomial_multiply,V,polynomial_balanced<W> >

#undef TMPL
} // namespace mmx
#endif //__MMX__POLYNOMIAL_BALANCED__HPP

---