/Users/mourrain/Devel/mmx/algebramix/include/algebramix/base_integer.hpp

Go to the documentation of this file.

/******************************************************************************
* MODULE     : base_integer.hpp
* DESCRIPTION: Change of base for integers
* COPYRIGHT  : (C) 2009  Joris van der Hoeven and 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_INTEGER_HPP
#define __MMX_BASE_INTEGER_HPP
#include <numerix/modular_integer.hpp>
#include <algebramix/base.hpp>
#include <algebramix/base_blocks.hpp>
#include <algebramix/base_int.hpp>

namespace mmx {

/******************************************************************************
* Variants / Note that default is signed
******************************************************************************/

DEFINE_VARIANT(base_naive_integer,base_signed<base_naive>)
DEFINE_VARIANT(base_dicho_integer,base_signed<base_dicho<base_naive> >)

STMPL
struct base_naive_variant_helper<integer> {
  typedef base_naive_integer BV;
};

STMPL
struct base_dicho_variant_helper<integer> {
  typedef base_dicho_integer BV;
};

STMPL
struct base_transformer_helper<integer,integer> {
  typedef base_dicho_transformer<integer> Baser;
};

STMPL
struct base_transformer_helper_unsigned<integer,integer> {
  typedef base_dicho_transformer<integer,std_base_dicho<integer>,
                                 base_dicho<base_naive> > Baser;
};

template<typename I>
struct size_bound_in_base_helper<integer,I> {
  static inline nat
  size (const integer& s, const I& p) {
    ASSERT (bit_size (p) > 1, "invalid base");
    return 1 + (1 + bit_size (s)) / (bit_size (p) - 1); }
};

/******************************************************************************
* Threshold
******************************************************************************/

STMPL
struct threshold_helper<integer,base_blocks_threshold> {
  typedef fixed_value<nat,32> impl;
};

/******************************************************************************
* Special transformer
******************************************************************************/

template<typename I>
struct base_integer_transformer {
  typedef integer C;

  // default internal type is 'int' for speed
  static const nat internal_size=
    sizeof(I) > sizeof(int) ? sizeof(I) : sizeof(int);
  typedef typename unsigned_int_with_size_at_least_helper<
    internal_size>::type uJ;
  typedef typename signed_of_helper<uJ>::type J;

  typedef typename Modulus_variant(I) modulus_base_variant;
  typedef modulus<I, modulus_base_variant> M;

  typedef typename Modulus_variant(J) modulus_middle_variant;
  typedef modulus<J, modulus_middle_variant> N;

  typedef C base;
  typedef I modulus_base;

  struct std_J_I {
    typedef J base;
    typedef I modulus_base;
    typedef typename Modulus_variant(I) modulus_base_variant;
  };
  typedef base_naive_transformer<J,std_J_I> Baser_I;

  struct std_C_J {
    typedef C base;
    typedef J modulus_base;
    typedef modulus_middle_variant modulus_base_variant;
  };
  typedef base_blocks_transformer<
    Baser_I,
    base_naive_transformer<C,std_C_J> > Baser_low;

  typedef base_dicho_transformer<integer,
                                  std_base_dicho<integer> > Baser_high;
  typedef base_blocks_transformer<Baser_low, Baser_high> Baser;

  M p;
  Baser* baser;

  template<typename K> 
  inline base_integer_transformer (const K& _p) : p (_p) {
    J p_s= * p; nat s= 1;
    while ((p_s * * p) / * p == p_s) { p_s *= * p; s++; }
    baser= mmx_new<Baser> (1, mmx_new<Baser_low> (1, p, s));
  }

  inline ~base_integer_transformer () {
    mmx_delete<Baser> (baser, 1); }

  inline nat direct_transform (I* c, nat n, const C& a) {
    return direct_base (c, n, a, * baser); }

  inline void inverse_transform (C& a, const I* c, nat n) {
    return inverse_base (a, c, n, * baser); }
};

#define IMPLEMENTATION_HELPER(I)                                \
  STMPL struct base_transformer_helper<integer,I> {             \
    typedef base_integer_transformer<I> Baser; };
IMPLEMENTATION_HELPER(signed char)
IMPLEMENTATION_HELPER(short int)
IMPLEMENTATION_HELPER(int)
IMPLEMENTATION_HELPER(long int)
IMPLEMENTATION_HELPER(long long int)
#undef IMPLEMENTATION_HELPER

/******************************************************************************
* Special transformer for nonnegative integers
******************************************************************************/

template<typename I>
struct base_unsigned_integer_transformer {
  typedef integer C;

  // default internal type is 'unsigned int' for speed
  static const nat internal_size=
    sizeof(I) > sizeof(int) ? sizeof(I) : sizeof(int);
  typedef typename unsigned_int_with_size_at_least_helper<
    internal_size>::type J;

  typedef typename Modulus_variant(I) modulus_base_variant;
  typedef modulus<I, modulus_base_variant> M;

  typedef typename Modulus_variant(J) modulus_middle_variant;
  typedef modulus<J, modulus_middle_variant> N;

  typedef C base;
  typedef I modulus_base;

  struct std_J_I {
    typedef J base;
    typedef I modulus_base;
    typedef typename Modulus_variant(I) modulus_base_variant;
  };
  typedef base_naive_transformer<J,std_J_I, base_naive> Baser_I;

  struct std_C_J {
    typedef C base;
    typedef J modulus_base;
    typedef modulus_middle_variant modulus_base_variant;
  };
  typedef base_blocks_transformer<
    Baser_I,
    base_naive_transformer<C,std_C_J,base_naive> > Baser_low;

  typedef base_dicho_transformer<integer, std_base_dicho<integer>,
                                  base_dicho<base_naive> > Baser_high;
  typedef base_blocks_transformer<Baser_low, Baser_high> Baser;

  M p;
  Baser* baser;

  template<typename K> 
  inline base_unsigned_integer_transformer (const K& _p) : p (_p) {
    J p_s= * p; nat s= 1;
    while ((p_s * * p) / * p == p_s) { p_s *= * p; s++; }
    baser= mmx_new<Baser> (1, mmx_new<Baser_low> (1, p, s));
  }

  inline ~base_unsigned_integer_transformer () {
    mmx_delete<Baser> (baser, 1); }

  inline nat direct_transform (I* c, nat n, const C& a) {
    ASSERT (a >= 0, "invalid negative argument");
    return direct_base (c, n, a, * baser); }

  inline void inverse_transform (C& a, const I* c, nat n) {
    return inverse_base (a, c, n, * baser); }
};

#define IMPLEMENTATION_HELPER(I)                                \
  STMPL struct base_transformer_helper<integer,I> {             \
    typedef base_unsigned_integer_transformer<I> Baser; };
IMPLEMENTATION_HELPER(unsigned char)
IMPLEMENTATION_HELPER(unsigned short)
IMPLEMENTATION_HELPER(unsigned int)
IMPLEMENTATION_HELPER(unsigned long int)
IMPLEMENTATION_HELPER(unsigned long long int)
#undef IMPLEMENTATION_HELPER

#define IMPLEMENTATION_HELPER(I)                                \
  STMPL struct base_transformer_helper_unsigned<integer,I> {    \
    typedef base_unsigned_integer_transformer<I> Baser; };
IMPLEMENTATION_HELPER(signed char)
IMPLEMENTATION_HELPER(short int)
IMPLEMENTATION_HELPER(int)
IMPLEMENTATION_HELPER(long int)
IMPLEMENTATION_HELPER(long long int)
#undef IMPLEMENTATION_HELPER

} // namespace mmx
#endif // __MMX_BASE_INTEGER_HPP