include/algebramix/base_naive.hpp

Go to the documentation of this file.

/******************************************************************************
* MODULE     : base_naive.hpp
* DESCRIPTION: Implementation and interface for naive 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_NAIVE__HPP
#define __MMX__BASE_NAIVE__HPP
#include <basix/vector.hpp>
#include <numerix/modular.hpp>

namespace mmx {

/******************************************************************************
* Size bound in base
******************************************************************************/

template<typename C, typename I=C>
struct size_bound_in_base_helper {
  static inline nat
  size (const C& s, const I& p) {
    ASSERT (N (p) > 1, "invalid base");
    return is_signed_helper<C>::value ?
      1 + (1 + N (s)) / (N (p) - 1):
      1 + N (s) / (N (p) - 1); }
};
  
/******************************************************************************
* Standard parameters
******************************************************************************/

template<typename C,typename I=C>
struct std_base_naive {
  typedef C                           base;
  typedef I                           modulus_base;
  typedef typename Modulus_variant(I) modulus_base_variant;
};

/******************************************************************************
* Naive variant for Base
******************************************************************************/

#define Base_naive_variant(C) base_naive_variant_helper<C>::BV

struct base_naive {};

template<typename C>
struct base_naive_variant_helper {
  typedef base_naive BV;
};

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

struct base_transform {};

template<typename V>
struct implementation<base_transform,V,base_naive> {

  template<typename C, typename M, typename I> static inline nat
  direct (I* c, nat n, const C& a, const M& p) {
    C x (a); nat i= 0;
    while (x != 0 && i < n) c[i++]= as<I> (rem (x, * p, x));
    return i; }

  template<typename C, typename M, typename I> static inline void
  inverse (C& a, const I* c, nat n, const M& p) {
    a= 0; while (n > 0) a = * p * a + c[--n]; }

};

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

template<typename V> struct base_signed {};

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

template<typename V,typename W>
struct implementation<base_transform,V,base_signed<W> > :
    implementation<base_transform,V,W > {

  template<typename C, typename M, typename I> static inline nat
  direct (I* c, nat n, const C& a, const M& p) {
    C x (a); C r, h (* p >> 1); nat i= 0;
    while (x != 0 && i < n) {
      if (x > 0) {
        r= rem (x, * p, x);
        if (r > h) {
          c[i++]= as<I> (r - * p);
          x += 1;
        }
        else
          c[i++]= as<I> (r);
      }
      else {
        r= rem (-x, * p, x); neg (x);
        if (r > h) {
          c[i++]= as<I> (* p - r);
          x -= 1;
        }
        else
          c[i++]= as<I> (- r);
      }
    }
    return i; }
};

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

template<typename C, typename S=std_base_naive<C>,
         typename V=typename Base_naive_variant(C) >
struct base_naive_transformer : public S {

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

  M p; // modulus of the base

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

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

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

/******************************************************************************
* Higher interface level -- common to all transformers
******************************************************************************/

#define C typename Baser::base
#define I typename Baser::modulus_base
#define M modulus<typename Baser::modulus_base,\
                  typename Baser::modulus_base_variant>

template<typename Baser> inline nat
size_bound (const C& a, Baser& baser) {
  // return a bound size for the expansion of a
  return size_bound_in_base_helper<C,I>::size (a, * baser.p);
}

template<typename Baser> inline nat
direct_base (I* dest, nat n, const C& s, Baser& baser) {
  // return the size filled in dest
  return baser.direct_transform (dest, n, s);
}

template<typename Baser, typename W> inline void
direct_base (vector<I,W>& dest, const C& s, Baser& baser) {
  nat n= size_bound (s, baser);
  nat l= aligned_size<I,W> (n);
  I* tmp= mmx_formatted_new<I> (l, CF(dest));
  n= baser.direct_transform (tmp, n, s);
  dest= vector<I,W> (tmp, n, l, CF(dest));
}

template<typename Baser> inline vector<I>
direct_base (const C& s, Baser& baser) {
  vector<I> dest;
  direct_base (dest, s, baser);
  return dest;
}

template<typename Baser> inline void
inverse_base (C& d, const I* src, nat n, Baser& baser) {
  baser.inverse_transform (d, src, n);
}

template<typename Baser, typename W> inline void
inverse_base (C& d, const vector<I,W>& src, Baser& baser) {
  baser.inverse_transform (d, seg (src), N(src));
}

template<typename Baser, typename W> inline C
inverse_base (const vector<I,W>& src, Baser& baser) {
  C d; inverse_base (d, seg (src), N(src), baser);
  return d;
}

#undef C
#undef I
#undef M
} // namespace mmx
#endif //__MMX__BASE_NAIVE__HPP

---