src/integer/misc/cl_I_exptpos.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 namespace cln {
  13
  14 const cl_I expt_pos (const cl_I& x, uintL y)
  15 {
  16   // Methode:
  17   //   a:=x, b:=y, c:=1. [a^b*c bleibt invariant, = x^y.]
  18   //   Solange b>1,
  19   //     falls b ungerade, setze c:=a*c,
  20   //     setze b:=floor(b/2),
  21   //     setze a:=a*a.
  22   //   Wenn b=1, setze c:=a*c.
  23   //   Liefere c.
  24   // Oder optimiert:
  25   //   a:=x, b:=y.
  26   //   Solange b gerade, setze a:=a*a, b:=b/2. [a^b bleibt invariant, = x^y.]
  27   //   c:=a.
  28   //   Solange b:=floor(b/2) >0 ist,
  29   //     setze a:=a*a, und falls b ungerade, setze c:=a*c.
  30   //   Liefere c.
  31   #if 0 // unoptimiert
  32     var cl_I a = x;
  33     var uintL b = y;
  34     var cl_I c = 1;
  35     until (b == 1)
  36       { if (b % 2) // b ungerade?
  37           { c = a * c; }
  38         b = b >> 1; // b := (floor b 2)
  39         a = square(a);
  40       }
  41     return a * c;
  42   #else // optimiert
  43     var cl_I a = x;
  44     var uintL b = y;
  45     while (!(b % 2)) { a = square(a); b = b >> 1; }
  46     var cl_I c = a;
  47     until (b == 1)
  48       { b = b >> 1;
  49         a = square(a);
  50         if (b % 2) { c = a * c; }
  51       }
  52     return c;
  53   #endif
  54 }
  55 // Bit complexity (x of length N): O(M(N*y)).
  56
  57 }  // namespace cln