cl_MI_lshift.cc

   1 // operator<< on cl_MI.
   2
   3 // General includes.
   4 #include "cl_sysdep.h"
   5
   6 // Specification.
   7 #include "cln/modinteger.h"
   8
   9
  10 // Implementation.
  11
  12 #include "cln/integer.h"
  13
  14 namespace cln {
  15
  16 const cl_MI operator<< (const cl_MI& x, sintC y) // assume 0 <= y < 2^(intCsize-1)
  17 {
  18         if (y == 0)
  19                 return x;
  20         if (y == 1) // frequent case
  21                 return x+x;
  22         var const cl_modint_ring& R = x.ring();
  23         // Method:
  24         // Algorithm 1: divide (x.rep << y) by m.
  25         //              asymptotical cost: O(y * log m).
  26         // Algorithm 2: x * expt(2 mod m,y) using modular integer operations.
  27         //              asymptotical cost: O(log y * (log m)^2).
  28         // Use algorithm 1 for small y, algorithm 2 for large y.
  29         if ((R->bits < 0) || (y <= 2*R->bits))
  30                 return cl_MI(R, R->reduce_modulo(x.rep << y));
  31         else
  32                 return x * expt_pos(R->canonhom(2), (cl_I)(long)y);
  33 }
  34
  35 }  // namespace cln