src/base/digit/cl_2D_exptpos.cc

   1 // expt_pos().
   2
   3 // General includes.
   4 #include "cl_sysdep.h"
   5
   6 // Specification.
   7 #include "cl_2D.h"
   8
   9
  10 // Implementation.
  11
  12 namespace cln {
  13
  14 uintD expt_pos (uintD a, uintL b)
  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       while ((b & bit(0)) == 0) { a = mul2adic(a,a); b = b>>1; }
  32       var uintD c = a;
  33       until ((b = b>>1) == 0)
  34         { a = mul2adic(a,a);
  35           if (b & bit(0)) { c = mul2adic(a,c); }
  36         }
  37       return c;
  38 }
  39
  40 }  // namespace cln