mul_mod_helper< C, void > Struct Template Reference

#include <modular_int.hpp>

List of all members.

Static Public Member Functions

Static Public Attributes

Detailed Description

template<typename V>
template<typename C>
struct mmx::modulus_mul_int_naive< V >::mul_mod_helper< C, void >

Definition at line 263 of file modular_int.hpp.

Member Function Documentation

static void half_lshift_mod ( C &  dest,
const C &  p,
const C &  lo_p,
const C &  hi_p,
C &  carry 
) [inline, static]

Definition at line 288 of file modular_int.hpp.

References mmx::C.

00289                               {
00290       // p = hi_p * B + lo_p, return (dest * B) % p and (dest * B) / p
00291       // It is required that hi_p != 0
00292       C q = dest / hi_p, c = 0; carry = q;
00293       C r = dest - q * hi_p;
00294       q *= lo_p; carry -= (q / p);
00295       q %= p;
00296       dest = r << half_size;
00297       V::sub_mod_core (dest, q, p, c);
00298       if (c != 0) carry--;
00299     }

static void half_lshift_mod ( C &  dest,
const C &  p,
const C &  lo_p,
const C &  hi_p 
) [inline, static]

Definition at line 276 of file modular_int.hpp.

References mmx::C.

00276                                                                       {
00277       // p = hi_p * B + lo_p, return (dest * B) % p
00278       // It is required that hi_p != 0
00279       C q = dest / hi_p;
00280       C r = dest - q * hi_p;
00281       q *= lo_p;
00282       q %= p;
00283       dest = r << half_size;
00284       V::sub_mod_core (dest, q, p);
00285     }

static C hi ( const C &  s  )  [inline, static]

Definition at line 273 of file modular_int.hpp.

00273 { return (s & hi_mask) >> half_size; }

static C lo ( const C &  s  )  [inline, static]

Definition at line 270 of file modular_int.hpp.

00270 { return s & lo_mask; }

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

Definition at line 328 of file modular_int.hpp.

References mmx::C.

00328                                                                       {
00329       C hi_p = hi (p);
00330       if (hi_p) {
00331         C lo_p = lo (p);
00332         C lo_dest = lo (dest);
00333         C lo_s = lo (s);
00334         C hi_dest = hi (dest);
00335         C hi_s = hi (s);
00336         C c= 0, cc= 0;
00337         dest = lo_dest * lo_s;
00338         reduce_mod_core (dest, p, cc);
00339         C t = lo_dest * hi_s;
00340         half_lshift_mod (t, p, lo_p, hi_p, c); cc += c; c= 0;
00341         V::add_mod_core (dest, t, p, c);       cc += c; c= 0;
00342         t = hi_dest * lo_s;
00343         half_lshift_mod (t, p, lo_p, hi_p, c); cc += c; c= 0;
00344         V::add_mod_core(dest, t, p, c);        cc += c; c= 0;
00345         t = hi_dest * hi_s;
00346         half_lshift_mod (t, p, lo_p, hi_p, c); cc += c << half_size; c= 0;
00347         half_lshift_mod (t, p, lo_p, hi_p, c); cc += c; c= 0;
00348         V::add_mod_core(dest, t, p, c);        cc += c; c= 0;
00349         V::add_mod_core(dest, carry, p, c);    carry = cc + c;
00350       }
00351       else {
00352         dest = dest * s + carry;
00353         if (p != 0) { carry= dest / p; dest %= p; }
00354       }
00355     }

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

Definition at line 301 of file modular_int.hpp.

References mmx::C.

00301                                                             {
00302       C hi_p = hi (p);
00303       if (hi_p) {
00304         C lo_p = lo (p);
00305         C lo_dest = lo (dest);
00306         C lo_s = lo (s);
00307         C hi_dest = hi (dest);
00308         C hi_s = hi (s);
00309         dest = lo_dest * lo_s;
00310         V::reduce_mod_core (dest, p);
00311         C t = lo_dest * hi_s;
00312         half_lshift_mod (t, p, lo_p, hi_p);
00313         V::add_mod_core (dest, t, p);
00314         t = hi_dest * lo_s;
00315         half_lshift_mod (t, p, lo_p, hi_p);
00316         V::add_mod_core(dest, t, p);
00317         t = hi_dest * hi_s;
00318         half_lshift_mod (t, p, lo_p, hi_p);
00319         half_lshift_mod (t, p, lo_p, hi_p);
00320         V::add_mod_core(dest, t, p);
00321       }
00322       else {
00323         dest *= s;
00324         if (p != 0) dest %= p;
00325       }
00326     }

Member Data Documentation

const nat half_size = 4 * sizeof (C) [static]

Definition at line 264 of file modular_int.hpp.

const C hi_mask = ((C) -1) << half_size [static]

Definition at line 267 of file modular_int.hpp.

const C lo_mask = ((C) -1) >> half_size [static]

Definition at line 266 of file modular_int.hpp.

const nat size = 2 * half_size [static]

Definition at line 265 of file modular_int.hpp.

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