include/algebramix/base_dicho.hpp

Go to the documentation of this file.

/******************************************************************************
* MODULE     : base_dicho.hpp
* DESCRIPTION: Implementation and interface for dichotomic change of bases
* COPYRIGHT  : (C) 2009  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__BASE_DICHO__HPP
#define __MMX__BASE_DICHO__HPP
#include <algebramix/base_naive.hpp>

namespace mmx {

/******************************************************************************
* Standard parameters
******************************************************************************/

template<typename C>
struct std_base_dicho {
  typedef C                           base;
  typedef C                           modulus_base;
  typedef typename Modulus_variant(C) modulus_base_variant;
};

/******************************************************************************
* Dichotomic variant for Base
******************************************************************************/

#define Base_dicho_variant(C) base_dicho_variant_helper<C>::BV

template<typename V>
struct base_dicho : public V {};

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

template<typename C>
struct base_dicho_variant_helper {
  typedef base_dicho<typename base_naive_variant_helper<C>::BV> BV;
};

/******************************************************************************
* Direct and inverse transforms
******************************************************************************/

template<typename V, typename W>
struct implementation<base_transform,V,base_dicho<W> > {

  template<typename C, typename M, typename I> static inline nat
  direct (I* c, nat n, const C& a, const M* pow_p) {
    if (n == 0 || a == 0) return 0;
    if (n == 1) {
      c[0]= rem (a, * pow_p[0]);
      return 1; }
    C q, r;
    nat h= (n+1) >> 1, l= log_2 (h); nat m= ((nat) 1) << l;
    r= rem (a, * pow_p[l], q);
    nat o= direct (c, m, r, pow_p);
    if (q == 0) return o;
    for (; o < m; o++) c[o]= 0;
    return m + direct (c + m, n - m, q, pow_p); }

  template<typename C, typename M, typename I> static inline void
  inverse (C& a, const I* c, nat n, const M* pow_p) {
    if (n == 0) return;
    if (n == 1) { a= c[0]; return; }
    if (n == 2) { a= c[0] + C(* pow_p[0]) * c[1]; return; }
    nat h= (n+1) >> 1; nat l= log_2 (h); nat m= ((nat) 1) << l; C b;
    inverse (a, c    , m    , pow_p);
    inverse (b, c + m, n - m, pow_p);
    a += * pow_p[l] * b; }
};

/******************************************************************************
* Signed variant for signed types
******************************************************************************/

template<typename V,typename W>
struct implementation<base_transform,V,base_signed<base_dicho<W> > > :
    implementation<base_transform,V,base_dicho<W> > {
private:
  template<typename C, typename M, typename I> static inline nat
  direct (I* c, nat n, const C& a, const M* pow_p, I& carry) {
    if (n == 0 || a == 0) { carry= 0; return 0; }
    C q, r;
    if (n == 1) {
      if (a < 0) {
        r= rem (- a, * pow_p[0], q);
        if (r > * pow_p[0] >> 1) { r -= * pow_p[0]; q += 1; }
        neg (r); neg (q);
      }
      else {
        r= rem (a, * pow_p[0], q);
        if (r > * pow_p[0] >> 1) { r -= * pow_p[0]; q += 1; }
      }
      c[0]= as<I> (r); carry= q;
      return c[0] == 0 ? 0 : 1;
    }
    nat h= (n+1) >> 1, l= log_2 (h); nat m= ((nat) 1) << l;
    r= rem (abs (a), * pow_p[l], q);
    if (a < 0) { neg (r); neg (q); }
    nat o= direct (c, m, r, pow_p, carry); q += carry;
    if (q == 0) return o;
    for (; o < m; o++) c[o]= 0;
    return m + direct (c + m, n - m, q, pow_p, carry);
  }
public:
  template<typename C, typename M, typename I> static inline nat
  direct (I* c, nat n, const C& a, const M* pow_p) {
    I carry (0); nat o= direct (c, n, a, pow_p, carry); (void) carry;
    return o; }

};

/******************************************************************************
* The naive base transformer class
******************************************************************************/

template<typename C, typename S=std_base_dicho<C>,
         typename V=typename Base_dicho_variant(C) >
struct base_dicho_transformer : public S {

  typedef typename S::modulus_base I;
  typedef modulus<I, typename S::modulus_base_variant> M;
  typedef implementation<base_transform,V> Base;

  vector<M> pow_p;
  M p;

private:
  void extend (nat n) {
    while (((nat) 1) << N(pow_p) <= ((n + 1) >> 1))
      pow_p << M (square (* pow_p[N(pow_p) - 1])); }
public:

  template<typename K> 
  inline base_dicho_transformer (const K& _p) : p(_p) {
    ASSERT (_p != 0, "invalid base");
    pow_p << p; }

  inline nat direct_transform (I* c, nat n, const C& a) {
    extend (n);
    return Base::direct (c, n, a, seg (pow_p)); }

  inline void inverse_transform (C& a, const I* c, nat n) {
    extend (n);
    Base::inverse (a, c, n, seg (pow_p)); }
};

} // namespace mmx
#endif //__MMX__BASE_DICHO__HPP

---