src/integer/misc/cl_I_exptpos_I.cc

   1 // expt_pos().
   2
   3 // General includes.
   4 #include "base/cl_sysdep.h"
   5
   6 // Specification.
   7 #include "cln/integer.h"
   8
   9
  10 // Implementation.
  11
  12 #include "integer/cl_I.h"
  13
  14 namespace cln {
  15
  16 const cl_I expt_pos (const cl_I& x, const cl_I& y)
  17 {
  18   // Methode:
  19   //   a:=x, b:=y, c:=1. [a^b*c bleibt invariant, = x^y.]
  20   //   Solange b>1,
  21   //     falls b ungerade, setze c:=a*c,
  22   //     setze b:=floor(b/2),
  23   //     setze a:=a*a.
  24   //   Wenn b=1, setze c:=a*c.
  25   //   Liefere c.
  26   // Oder optimiert:
  27   //   a:=x, b:=y.
  28   //   Solange b gerade, setze a:=a*a, b:=b/2. [a^b bleibt invariant, = x^y.]
  29   //   c:=a.
  30   //   Solange b:=floor(b/2) >0 ist,
  31   //     setze a:=a*a, und falls b ungerade, setze c:=a*c.
  32   //   Liefere c.
  33   #if 0 // unoptimiert
  34     var cl_I a = x;
  35     var cl_I b = y;
  36     var cl_I c = 1;
  37     until (eq(b,1))
  38       { if (oddp(b))
  39           { c = a * c; }
  40         b = b >> 1; // b := (floor b 2)
  41         a = square(a);
  42       }
  43     return a * c;
  44   #else // optimiert
  45     var cl_I a = x;
  46     var cl_I b = y;
  47     while (!oddp(b)) { a = square(a); b = b >> 1; }
  48     var cl_I c = a;
  49     until (eq(b,1))
  50       { b = b >> 1;
  51         a = square(a);
  52         if (oddp(b)) { c = a * c; }
  53       }
  54     return c;
  55   #endif
  56 }
  57 // Bit complexity (x of length N): O(M(N*y)).
  58
  59 }  // namespace cln