modulus_int_naive< size > Struct Template Reference

#include <modular_int.hpp>

Inheritance diagram for modulus_int_naive< size >:
modulus_encoding_int_naive< modulus_div_int_naive< modulus_inv_int_naive< modulus_mul_int_naive< modulus_add_int_naive< modulus_reduction_int_naive< modulus_normalization_int_naive< modulus_maximum_size_int< size > > > > > > > > modulus_div_int_naive< modulus_inv_int_naive< modulus_mul_int_naive< modulus_add_int_naive< modulus_reduction_int_naive< modulus_normalization_int_naive< modulus_maximum_size_int< size > > > > > > > modulus_inv_int_naive< modulus_mul_int_naive< modulus_add_int_naive< modulus_reduction_int_naive< modulus_normalization_int_naive< modulus_maximum_size_int< size > > > > > > modulus_mul_int_naive< modulus_add_int_naive< modulus_reduction_int_naive< modulus_normalization_int_naive< modulus_maximum_size_int< size > > > > > modulus_add_int_naive< modulus_reduction_int_naive< modulus_normalization_int_naive< modulus_maximum_size_int< size > > > > modulus_reduction_int_naive< modulus_normalization_int_naive< modulus_maximum_size_int< size > > > modulus_normalization_int_naive< modulus_maximum_size_int< size > > modulus_maximum_size_int< size >

List of all members.

Static Public Member Functions

Detailed Description

template<int size>
struct mmx::modulus_int_naive< size >

Definition at line 511 of file modular_int.hpp.

Member Function Documentation

static void add_mod ( C &  dest,
const C &  s1,
const C &  s2,
const M &  m,
C &  carry 
) [inline, static, inherited]

Definition at line 208 of file modular_int.hpp.

References modulus_add_int_naive< V >::add_mod().

00208                                                                     {
00209     dest = s1;
00210     add_mod (dest, s2, m, carry); }

static void add_mod ( C &  dest,
const C &  s1,
const C &  s2,
const M &  m 
) [inline, static, inherited]

Definition at line 203 of file modular_int.hpp.

References modulus_add_int_naive< V >::add_mod().

00203                                                           {
00204     dest = s1;
00205     add_mod (dest, s2, m); }

static void add_mod ( C &  dest,
const C &  s,
const M &  m,
C &  carry 
) [inline, static, inherited]

Definition at line 199 of file modular_int.hpp.

References modulus_add_int_naive< V >::add_mod_core().

00199                                                       {
00200     add_mod_core (dest, s, m.p, carry); }

static void add_mod ( C &  dest,
const C &  s,
const M &  m 
) [inline, static, inherited]

Definition at line 195 of file modular_int.hpp.

References modulus_add_int_naive< V >::add_mod_core().

00195                                             {
00196     add_mod_core (dest, s, m.p); }

static void add_mod_core ( C &  dest,
const C &  s,
const C &  p,
C &  carry 
) [inline, static, inherited]

Definition at line 191 of file modular_int.hpp.

00191                                                            {
00192     add_mod_helper<C,is_signed_helper<C>::value>::op (dest, s, p, carry); }

static void add_mod_core ( C &  dest,
const C &  s,
const C &  p 
) [inline, static, inherited]

Definition at line 187 of file modular_int.hpp.

00187                                                  {
00188     add_mod_helper<C,is_signed_helper<C>::value>::op (dest, s, p); }

static void add_mod_with_overflow ( C &  dest,
const C &  s,
const C &  p,
C &  carry 
) [inline, static, inherited]

Definition at line 146 of file modular_int.hpp.

References VERIFY.

00146                                                                     {
00147     VERIFY (carry == 0 || carry == 1, "unexpected large carry");
00148     dest += s + carry;
00149     if (dest < s || dest >= p) { dest -= p; carry= 1; }
00150     else carry= 0; }

static void add_mod_with_overflow ( C &  dest,
const C &  s,
const C &  p 
) [inline, static, inherited]

Definition at line 140 of file modular_int.hpp.

00140                                                           {
00141     dest += s;
00142     if (dest < s) { dest -= p; return; }
00143     if (dest >= p) dest -= p; }

static void add_mod_without_overflow ( C &  dest,
const C &  s,
const C &  p,
C &  carry 
) [inline, static, inherited]

Definition at line 134 of file modular_int.hpp.

References VERIFY.

00134                                                                        {
00135     VERIFY (carry == 0 || carry == 1, "unexpected large carry");
00136     dest += s + carry;
00137     if (dest >= p) { dest -= p; carry= 1; } else carry= 0; }

static void add_mod_without_overflow ( C &  dest,
const C &  s,
const C &  p 
) [inline, static, inherited]

Definition at line 129 of file modular_int.hpp.

00129                                                              {
00130     dest += s;
00131     if (dest >= p) dest -= p; }

static void decode_mod ( C &  dest,
const C &  s,
const M &  m 
) [inline, static, inherited]

Definition at line 505 of file modular_int.hpp.

00505                                                {
00506     (void) m;
00507     dest = s; }

static void div_mod ( C &  dest,
const C &  s1,
const C &  s2,
const M &  m 
) [inline, static, inherited]

Definition at line 485 of file modular_int.hpp.

References modulus_div_int_naive< V >::div_mod().

00485                                                           {
00486     dest = s1;
00487     div_mod (dest, s2, m); }

static void div_mod ( C &  dest,
const C &  s,
const M &  m 
) [inline, static, inherited]

Definition at line 479 of file modular_int.hpp.

References mmx::C.

00479                                             {
00480     C t = s;
00481     V::inv_mod (t, m);
00482     V::mul_mod (dest, t, m); }

static void encode_mod ( C &  dest,
const C &  s,
const M &  m 
) [inline, static, inherited]

Definition at line 493 of file modular_int.hpp.

References mmx::C, and mmx::sign().

00493                                                {
00494     typedef typename unsigned_of_helper<C>::type uC;
00495     if (sign (s) < 0) {
00496       uC tmp = - ((uC) s);
00497       V::reduce_mod (tmp, m);
00498       dest = (C) (((uC) m.p) - tmp);
00499     }
00500     else
00501       dest = s;
00502       V::reduce_mod (dest, m);
00503   }

static void inv_mod ( C &  dest,
const C &  s,
const M &  m 
) [inline, static, inherited]

Definition at line 470 of file modular_int.hpp.

References modulus_inv_int_naive< V >::inv_mod().

00470                                             {
00471     dest = s;
00472     inv_mod (dest, m); }

static void inv_mod ( C &  a,
const M &  m 
) [inline, static, inherited]

Definition at line 463 of file modular_int.hpp.

References mmx::C, modulus_inv_int_naive< V >::inv_mod_signed(), and modulus_inv_int_naive< V >::inv_mod_unsigned().

00463                              {
00464     if (V::template maximum_size_helper<C>::value >= 8*sizeof(C))
00465       inv_mod_unsigned(a, m.p);
00466     else
00467       inv_mod_signed(a, m.p); }

static void inv_mod_signed ( C &  a,
const C &  p 
) [inline, static, inherited]

Definition at line 402 of file modular_int.hpp.

References ERROR.

00402                                     {
00403     typedef typename unsigned_of_helper<C>::type uC;
00404     typedef typename signed_of_helper<C>::type sC;
00405     sC coa0=0, coa1=1, r0=p, r1=a, q, t;        
00406     if ((p == 0) && (r1 != 0)) {
00407       q = (((uC) r0) - ((uC) r1)) / ((uC) r1) + 1;
00408       t = r0 - q * r1;
00409       r0 = r1;
00410       r1 = t;
00411       t = coa1;
00412       coa1 = coa0 - q * coa1;
00413       coa0 = t;
00414     }
00415     while (r1 != 0) {
00416       q = r0 / r1;
00417       t = r0 - q * r1;
00418       r0 = r1;
00419       r1 = t;
00420       t = coa1;
00421       coa1 = coa0 - q * coa1;
00422       coa0 = t;
00423     }
00424     if (r0 != 1)
00425       ERROR ("inv_mod: argument is not invertible");
00426     a = coa0 < 0 ? p+coa0 : coa0;
00427   }

static void inv_mod_unsigned ( C &  a,
const C &  p 
) [inline, static, inherited]

Definition at line 430 of file modular_int.hpp.

References mmx::C, and ERROR.

00430                                       {
00431     C coa0=0, coa1=1, r0=p, r1=a, q, t; 
00432     bool toggle = true;
00433     if ((p == 0) && (r1 != 0)) {
00434       q = (r0-r1) / r1 + 1;
00435       t = r0 - q * r1;
00436       r0 = r1;
00437       r1 = t;
00438       t = coa1;
00439       coa1 = coa0 - q * coa1;
00440       coa0 = t;
00441       toggle = !toggle;
00442     }
00443     while (r1 != 0) {
00444       q = r0 / r1;
00445       t = r0 - q * r1;
00446       r0 = r1;
00447       r1 = t;
00448       t = coa1;
00449       coa1 = coa0 - q * coa1;
00450       coa0 = t;
00451       toggle = !toggle;
00452     }
00453     if (r0 != 1)
00454       ERROR ("inv_mod: argument is not invertible");
00455     a = (toggle && (coa0 != 0)) ? p+coa0 : coa0;
00456   }

static bool is_invertible_mod ( const C &  s,
const M &  m 
) [inline, static, inherited]

Definition at line 459 of file modular_int.hpp.

References mmx::abs(), and mmx::gcd().

00459                                              {
00460     return abs (gcd (s, m.p)) == 1; }

static void mul_mod ( C &  dest,
const C &  s1,
const C &  s2,
const M &  m,
C &  carry 
) [inline, static, inherited]

Definition at line 392 of file modular_int.hpp.

References modulus_mul_int_naive< V >::mul_mod().

00392                                                                     {
00393     dest = s1;
00394     mul_mod (dest, s2, m, carry); }

static void mul_mod ( C &  dest,
const C &  s1,
const C &  s2,
const M &  m 
) [inline, static, inherited]

Definition at line 387 of file modular_int.hpp.

References modulus_mul_int_naive< V >::mul_mod().

00387                                                           {
00388     dest = s1;
00389     mul_mod (dest, s2, m); }

static void mul_mod ( C &  dest,
const C &  s,
const M &  m,
C &  carry 
) [inline, static, inherited]

Definition at line 373 of file modular_int.hpp.

References modulus_mul_int_naive< V >::mul_mod(), and mul_mod_helper< C, D >::op().

00373                                                       {
00374     if (is_signed_helper<C>::value) {
00375       typedef typename unsigned_of_helper<C>::type uC;
00376       uC t = dest, ucarry= carry;
00377       mul_mod (t, (uC) s, m, ucarry);
00378       dest = t; carry= ucarry;
00379     }
00380     else {
00381       typedef typename unsigned_int_with_double_size_helper<C>::type D;
00382       mul_mod_helper<C,D>::op (dest, s, m.p, carry);
00383     }
00384   }

static void mul_mod ( C &  dest,
const C &  s,
const M &  m 
) [inline, static, inherited]

Definition at line 359 of file modular_int.hpp.

References modulus_mul_int_naive< V >::mul_mod(), and mul_mod_helper< C, D >::op().

00359                                             {
00360     if (is_signed_helper<C>::value) {
00361       typedef typename unsigned_of_helper<C>::type uC;
00362       uC t = dest;
00363       mul_mod (t, (uC) s, m);
00364       dest = t;
00365     }
00366     else {
00367       typedef typename unsigned_int_with_double_size_helper<C>::type D;
00368       mul_mod_helper<C,D>::op (dest, s, m.p);
00369     }
00370   }

static void neg_mod ( C &  dest,
const C &  s,
const M &  m,
C &  carry 
) [inline, static, inherited]

Definition at line 123 of file modular_int.hpp.

References VERIFY.

00123                                                       {
00124     VERIFY (carry == 0 || carry == 1, "unexpected large carry");
00125     if (s != 0 || carry != 0) { dest= m.p - s - carry; carry= 1; }
00126     else dest= 0; }

static void neg_mod ( C &  dest,
const C &  s,
const M &  m 
) [inline, static, inherited]

Definition at line 119 of file modular_int.hpp.

00119                                             {
00120     if (s != 0) dest = m.p - s; else dest = s; }

static void neg_mod ( C &  dest,
const M &  m,
C &  carry 
) [inline, static, inherited]

Definition at line 114 of file modular_int.hpp.

References VERIFY.

00114                                           {
00115     VERIFY (carry == 0 || carry == 1, "unexpected large carry");
00116     if (dest != 0 || carry != 0) { dest= m.p - dest - carry; carry= 1; } }

static void neg_mod ( C &  dest,
const M &  m 
) [inline, static, inherited]

Definition at line 110 of file modular_int.hpp.

00110                                 {
00111     if (dest != 0) dest = m.p - dest; }

static bool normalize ( C &  p  )  [inline, static, inherited]

Definition at line 66 of file modular_int.hpp.

References mmx::abs(), and MMX_SAFE_LEFT_SHIFT_INT.

00066                    {
00067     typedef typename unsigned_of_helper<C>::type uC;
00068     static const uC a = MMX_SAFE_LEFT_SHIFT_INT(uC, 1,
00069                          V::template maximum_size_helper<C>::value);
00070     p = abs (p);
00071     if ((uC) p == a || p == 0) { p = a; return true; }
00072     return p <= V::template maximum_value_helper<C>::dyn_value ();
00073   }

static void reduce_mod ( C &  dest,
const C &  s,
const M &  m,
C &  carry 
) [inline, static, inherited]

Definition at line 101 of file modular_int.hpp.

References mmx::C, and modulus_reduction_int_naive< V >::reduce_mod_core().

00101                                                          {
00102     dest = s;
00103     reduce_mod_core (dest, (C) m.p, carry); }

static void reduce_mod ( C &  dest,
const C &  s,
const M &  m 
) [inline, static, inherited]

Definition at line 96 of file modular_int.hpp.

References mmx::C, and modulus_reduction_int_naive< V >::reduce_mod_core().

00096                                                {
00097     dest = s;
00098     reduce_mod_core (dest, (C) m.p); }

static void reduce_mod ( C &  dest,
const M &  m,
C &  carry 
) [inline, static, inherited]

Definition at line 92 of file modular_int.hpp.

References mmx::C, and modulus_reduction_int_naive< V >::reduce_mod_core().

00092                                              {
00093     reduce_mod_core (dest, (C) m.p, carry); }

static void reduce_mod ( C &  dest,
const M &  m 
) [inline, static, inherited]

Definition at line 88 of file modular_int.hpp.

References mmx::C, and modulus_reduction_int_naive< V >::reduce_mod_core().

00088                                    {
00089     reduce_mod_core (dest, (C) m.p); }

static void reduce_mod_core ( C &  dest,
const C &  p,
C &  carry 
) [inline, static, inherited]

Definition at line 83 of file modular_int.hpp.

00083                                                   {
00084     if (p != 0) { carry= dest / p; dest %= p; }
00085     else carry = 0; }

static void reduce_mod_core ( C &  dest,
const C &  p 
) [inline, static, inherited]

Definition at line 79 of file modular_int.hpp.

00079                                         {
00080     if (p != 0) dest %= p; }

static void sub_mod ( C &  dest,
const C &  s1,
const C &  s2,
const M &  m,
C &  carry 
) [inline, static, inherited]

Definition at line 238 of file modular_int.hpp.

References modulus_add_int_naive< V >::sub_mod().

00238                                                                     {
00239     dest = s1;
00240     sub_mod (dest, s2, m, carry); }

static void sub_mod ( C &  dest,
const C &  s1,
const C &  s2,
const M &  m 
) [inline, static, inherited]

Definition at line 233 of file modular_int.hpp.

References modulus_add_int_naive< V >::sub_mod().

00233                                                           {
00234     dest = s1;
00235     sub_mod (dest, s2, m); }

static void sub_mod ( C &  dest,
const C &  s,
const M &  m,
C &  carry 
) [inline, static, inherited]

Definition at line 229 of file modular_int.hpp.

References modulus_add_int_naive< V >::sub_mod_core().

00229                                                       {
00230     sub_mod_core (dest, s, m.p, carry); }

static void sub_mod ( C &  dest,
const C &  s,
const M &  m 
) [inline, static, inherited]

Definition at line 225 of file modular_int.hpp.

References modulus_add_int_naive< V >::sub_mod_core().

00225                                             {
00226     sub_mod_core (dest, s, m.p); }

static void sub_mod_core ( C &  dest,
const C &  s,
const C &  p,
C &  carry 
) [inline, static, inherited]

Definition at line 218 of file modular_int.hpp.

References mmx::C, and VERIFY.

00218                                                            {
00219     VERIFY (carry == 0 || carry == 1, "unexpected large carry");
00220     C t = s + carry;
00221     if (t == p || dest < t) { dest += p; carry= 1; } else carry= 0;
00222     dest -= t; }

static void sub_mod_core ( C &  dest,
const C &  s,
const C &  p 
) [inline, static, inherited]

Definition at line 213 of file modular_int.hpp.

00213                                                  {
00214     if (dest < s) dest += p;
00215     dest -= s; }

The documentation for this struct was generated from the following file:
Generated on 6 Dec 2012 for numerix by  doxygen 1.6.1