algebramix: include/algebramix/base_integer.hpp Source File

00001 
00002 /******************************************************************************
00003 * MODULE     : base_integer.hpp
00004 * DESCRIPTION: Change of base for integers
00005 * COPYRIGHT  : (C) 2009  Joris van der Hoeven and Gregoire Lecerf
00006 *******************************************************************************
00007 * This software falls under the GNU general public license and comes WITHOUT
00008 * ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for more details.
00009 * If you don't have this file, write to the Free Software Foundation, Inc.,
00010 * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
00011 ******************************************************************************/
00012 
00013 #ifndef __MMX_BASE_INTEGER_HPP
00014 #define __MMX_BASE_INTEGER_HPP
00015 #include <numerix/modular_integer.hpp>
00016 #include <algebramix/base.hpp>
00017 #include <algebramix/base_blocks.hpp>
00018 #include <algebramix/base_int.hpp>
00019 
00020 namespace mmx {
00021 
00022 /******************************************************************************
00023 * Variants / Note that default is signed
00024 ******************************************************************************/
00025 
00026 DEFINE_VARIANT(base_naive_integer,base_signed<base_naive>)
00027 DEFINE_VARIANT(base_dicho_integer,base_signed<base_dicho<base_naive> >)
00028 
00029 STMPL
00030 struct base_naive_variant_helper<integer> {
00031   typedef base_naive_integer BV;
00032 };
00033 
00034 STMPL
00035 struct base_dicho_variant_helper<integer> {
00036   typedef base_dicho_integer BV;
00037 };
00038 
00039 STMPL
00040 struct base_transformer_helper<integer,integer> {
00041   typedef base_dicho_transformer<integer> Baser;
00042 };
00043 
00044 STMPL
00045 struct base_transformer_helper_unsigned<integer,integer> {
00046   typedef base_dicho_transformer<integer,std_base_dicho<integer>,
00047                                  base_dicho<base_naive> > Baser;
00048 };
00049 
00050 template<typename I>
00051 struct size_bound_in_base_helper<integer,I> {
00052   static inline nat
00053   size (const integer& s, const I& p) {
00054     ASSERT (bit_size (p) > 1, "invalid base");
00055     return 1 + (1 + bit_size (s)) / (bit_size (p) - 1); }
00056 };
00057 
00058 /******************************************************************************
00059 * Threshold
00060 ******************************************************************************/
00061 
00062 STMPL
00063 struct threshold_helper<integer,base_blocks_threshold> {
00064   typedef fixed_value<nat,32> impl;
00065 };
00066 
00067 /******************************************************************************
00068 * Special transformer
00069 ******************************************************************************/
00070 
00071 template<typename I>
00072 struct base_integer_transformer {
00073   typedef integer C;
00074 
00075   // default internal type is 'int' for speed
00076   static const nat internal_size=
00077     sizeof(I) > sizeof(int) ? sizeof(I) : sizeof(int);
00078   typedef typename unsigned_int_with_size_at_least_helper<
00079     internal_size>::type uJ;
00080   typedef typename signed_of_helper<uJ>::type J;
00081 
00082   typedef typename Modulus_variant(I) modulus_base_variant;
00083   typedef modulus<I, modulus_base_variant> M;
00084 
00085   typedef typename Modulus_variant(J) modulus_middle_variant;
00086   typedef modulus<J, modulus_middle_variant> N;
00087 
00088   typedef C base;
00089   typedef I modulus_base;
00090 
00091   struct std_J_I {
00092     typedef J base;
00093     typedef I modulus_base;
00094     typedef typename Modulus_variant(I) modulus_base_variant;
00095   };
00096   typedef base_naive_transformer<J,std_J_I> Baser_I;
00097 
00098   struct std_C_J {
00099     typedef C base;
00100     typedef J modulus_base;
00101     typedef modulus_middle_variant modulus_base_variant;
00102   };
00103   typedef base_blocks_transformer<
00104     Baser_I,
00105     base_naive_transformer<C,std_C_J> > Baser_low;
00106 
00107   typedef base_dicho_transformer<integer,
00108                                  std_base_dicho<integer> > Baser_high;
00109   typedef base_blocks_transformer<Baser_low, Baser_high> Baser;
00110 
00111   M p;
00112   Baser* baser;
00113 
00114   template<typename K> 
00115   inline base_integer_transformer (const K& _p) : p (_p) {
00116     J p_s= * p, q_s = square (* p); nat s= 1;
00117     while (quo (q_s, * p) == p_s) {
00118       p_s = q_s; q_s= p_s * * p; s++; }
00119     baser= mmx_new<Baser> (1, mmx_new<Baser_low> (1, p, s));
00120   }
00121 
00122   inline ~base_integer_transformer () {
00123     mmx_delete<Baser> (baser, 1); }
00124 
00125   inline nat direct_transform (I* c, nat n, const C& a) {
00126     return direct_base (c, n, a, * baser); }
00127 
00128   inline void inverse_transform (C& a, const I* c, nat n) {
00129     return inverse_base (a, c, n, * baser); }
00130 };
00131 
00132 #define IMPLEMENTATION_HELPER(I)                                \
00133   STMPL struct base_transformer_helper<integer,I> {             \
00134     typedef base_integer_transformer<I> Baser; };
00135 IMPLEMENTATION_HELPER(signed char)
00136 IMPLEMENTATION_HELPER(short int)
00137 IMPLEMENTATION_HELPER(int)
00138 IMPLEMENTATION_HELPER(long int)
00139 IMPLEMENTATION_HELPER(long long int)
00140 #undef IMPLEMENTATION_HELPER
00141 
00142 /******************************************************************************
00143 * Special transformer for nonnegative integers
00144 ******************************************************************************/
00145 
00146 template<typename I>
00147 struct base_unsigned_integer_transformer {
00148   typedef integer C;
00149 
00150   // default internal type is 'unsigned int' for speed
00151   static const nat internal_size=
00152     sizeof(I) > sizeof(int) ? sizeof(I) : sizeof(int);
00153   typedef typename unsigned_int_with_size_at_least_helper<
00154     internal_size>::type J;
00155 
00156   typedef typename Modulus_variant(I) modulus_base_variant;
00157   typedef modulus<I, modulus_base_variant> M;
00158 
00159   typedef typename Modulus_variant(J) modulus_middle_variant;
00160   typedef modulus<J, modulus_middle_variant> N;
00161 
00162   typedef C base;
00163   typedef I modulus_base;
00164 
00165   struct std_J_I {
00166     typedef J base;
00167     typedef I modulus_base;
00168     typedef typename Modulus_variant(I) modulus_base_variant;
00169   };
00170   typedef base_naive_transformer<J,std_J_I, base_naive> Baser_I;
00171 
00172   struct std_C_J {
00173     typedef C base;
00174     typedef J modulus_base;
00175     typedef modulus_middle_variant modulus_base_variant;
00176   };
00177   typedef base_blocks_transformer<
00178     Baser_I,
00179     base_naive_transformer<C,std_C_J,base_naive> > Baser_low;
00180 
00181   typedef base_dicho_transformer<integer, std_base_dicho<integer>,
00182                                   base_dicho<base_naive> > Baser_high;
00183   typedef base_blocks_transformer<Baser_low, Baser_high> Baser;
00184 
00185   M p;
00186   Baser* baser;
00187 
00188   template<typename K> 
00189   inline base_unsigned_integer_transformer (const K& _p) : p (_p) {
00190     J p_s= * p, q_s = square (* p); nat s= 1;
00191     while (quo (q_s, * p) == p_s) {
00192       p_s = q_s; q_s= p_s * * p; s++; }
00193     baser= mmx_new<Baser> (1, mmx_new<Baser_low> (1, p, s));
00194   }
00195 
00196   inline ~base_unsigned_integer_transformer () {
00197     mmx_delete<Baser> (baser, 1); }
00198 
00199   inline nat direct_transform (I* c, nat n, const C& a) {
00200     ASSERT (a >= 0, "invalid negative argument");
00201     return direct_base (c, n, a, * baser); }
00202 
00203   inline void inverse_transform (C& a, const I* c, nat n) {
00204     return inverse_base (a, c, n, * baser); }
00205 };
00206 
00207 #define IMPLEMENTATION_HELPER(I)                                \
00208   STMPL struct base_transformer_helper<integer,I> {             \
00209     typedef base_unsigned_integer_transformer<I> Baser; };
00210 IMPLEMENTATION_HELPER(unsigned char)
00211 IMPLEMENTATION_HELPER(unsigned short)
00212 IMPLEMENTATION_HELPER(unsigned int)
00213 IMPLEMENTATION_HELPER(unsigned long int)
00214 IMPLEMENTATION_HELPER(unsigned long long int)
00215 #undef IMPLEMENTATION_HELPER
00216 
00217 #define IMPLEMENTATION_HELPER(I)                                \
00218   STMPL struct base_transformer_helper_unsigned<integer,I> {    \
00219     typedef base_unsigned_integer_transformer<I> Baser; };
00220 IMPLEMENTATION_HELPER(signed char)
00221 IMPLEMENTATION_HELPER(short int)
00222 IMPLEMENTATION_HELPER(int)
00223 IMPLEMENTATION_HELPER(long int)
00224 IMPLEMENTATION_HELPER(long long int)
00225 #undef IMPLEMENTATION_HELPER
00226 
00227 } // namespace mmx
00228 #endif // __MMX_BASE_INTEGER_HPP