_dynamic_inverse_helper< C, void > Struct Template Reference

#include <modular_int.hpp>

List of all members.

Public Types

• typedef unsigned_of_helper< C >
  ::type uC
• typedef long_int_mul_op< C > long_mul
• typedef long_int_rshift_op< C > long_rshift
• typedef long_int_sub_op< C > long_sub

Static Public Member Functions

• static uC _q0 (const uC &p, nat r, nat s, nat t, nat s0, nat s1)
• static uC op (const uC &p, nat r, nat s, nat t)

Static Public Attributes

• static const nat n2 = 4 * sizeof(C)
• static const nat n = 8 * sizeof(C)
• static const nat m = V::template maximum_size_helper<C>::value

---

Detailed Description

template<typename V>
template<typename C>
struct mmx::modulus_mul_int_preinverse< V >::_dynamic_inverse_helper< C, void >

Definition at line 550 of file modular_int.hpp.

---

Member Typedef Documentation

typedef long_int_mul_op<C> long_mul

Definition at line 555 of file modular_int.hpp.

typedef long_int_rshift_op<C> long_rshift

Definition at line 556 of file modular_int.hpp.

typedef long_int_sub_op<C> long_sub

Definition at line 557 of file modular_int.hpp.

typedef unsigned_of_helper<C>::type uC

Definition at line 554 of file modular_int.hpp.

---

Member Function Documentation

static uC _q0	(	const uC &	p,
		nat	r,
		nat	s,
		nat	t,
		nat	s0,
		nat	s1
	)			[inline, static]

Definition at line 560 of file modular_int.hpp.

References n.

                                                           {
      // p != 1 or 2
      uC q0;
      if (r <= s0)
        q0 = (((uC) 1) << (s0+r-1)) / p;
      else {
        uC p1 = (p == 0) ? ((uC) 1) << s0 : p >> (r-s0);
        uC p0 = p & (((uC) -1) >> (n+s0-r));
        uC d = ((uC) 1) << s1;
        q0 = d / p1;
        uC b = (d % p1) << (r-s0);
        uC c = q0 * p0;
        if (c >= p) { q0--; c -= p; }
        if (b < c) q0--;
      }
      return q0;
    }

static uC op	(	const uC &	p,
		nat	r,
		nat	s,
		nat	t
	)			[inline, static]

Definition at line 579 of file modular_int.hpp.

References _dynamic_inverse_helper< C, D >::m, n, and _dynamic_inverse_helper< C, D >::op().

                                          {
      // If p is 1 or 2 then s0 == 0.
      // p must be normalized.
      if (p == 1) {
        if (m+2 <= n) return 2;
        if (m+1 <= n) return 1;
        return 0;
      }
      if (p == 2) {
        if (m+2 <= n) return 4;
        if (m+1 <= n) return 2;
        return 1;
      }
      nat s0 = (s+t-(r-1)) >> 1;
      nat s1 = 2*s0 - 1;
      uC q0 = _q0 (p, r, s, t, s0, s1);
      uC a0 = 0, a1 = 0;
      long_mul::op (a1, a0, q0 * q0, p);
      if (long_rshift::op_b (a1, a0, r)) a0++;
      uC c = (q0 << s0) - a0;
      uC d;
      if (m+1 <= n || s1+r <= n) {
        if (s1+r-1 >= n) d = 0; else d = (((uC) 1) << (s1+r-1));
        d -= c*p;
        if (d >= p) { c++; d-=p; }
      }
      else {
        uC d1, e0, e1;
        long_mul::op (e1, e0, c, p);
        d = 0;
        d1 = ((uC) 1) << (s1+r-1-n);
        long_sub::op (d1, d, e1, e0);
        if ((d1 != 0) || (d >= p)) { c++; d-=p; }
      }
      uC d2 = d << 1;
      c <<= 1;
      if ((d2 >= p) || (d2 < d)) { c++; d = d2-p; } else d = d2;
      if (s1+1 == s+t-(r-1)) return c;
      d2 = d << 1;
      c <<= 1;
      if ((d2 >= p) || (d2 < d)) c++;
      return c;
    }

---

Member Data Documentation

const nat m = V::template maximum_size_helper<C>::value [static]

Definition at line 553 of file modular_int.hpp.

const nat n = 8 * sizeof(C) [static]

Definition at line 552 of file modular_int.hpp.

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

Definition at line 551 of file modular_int.hpp.

---

The documentation for this struct was generated from the following file:

• include/numerix/modular_int.hpp