src/integer/algebraic/cl_I_sqrt.cc

   1 // isqrt().
   2
   3 // General includes.
   4 #include "cl_sysdep.h"
   5
   6 // Specification.
   7 #include "cln/integer.h"
   8
   9
  10 // Implementation.
  11
  12 #include "cln/number.h"
  13 #include "cln/io.h"
  14 #include "cln/integer_io.h"
  15 #include "cln/exception.h"
  16 #include "cl_I.h"
  17 #include "cl_DS.h"
  18 #include <sstream>
  19
  20 namespace cln {
  21
  22 cl_boolean isqrt (const cl_I& x, cl_I* w)
  23 {
  24         if (minusp(x)) {
  25                 std::ostringstream buf;
  26                 fprint(buf, "isqrt: applied to negative number: ");
  27                 fprint(buf, x);
  28                 throw runtime_exception(buf.str());
  29         }
  30         CL_ALLOCA_STACK;
  31         var const uintD* x_MSDptr;
  32         var uintC x_len;
  33         var const uintD* x_LSDptr;
  34         I_to_NDS_nocopy(x, x_MSDptr=,x_len=,x_LSDptr=,cl_true,); // Digit sequence >=0 zu x
  35         var DS y;
  36         var cl_boolean squarep;
  37         UDS_sqrt(x_MSDptr,x_len,x_LSDptr, &y, squarep=); // Wurzel ziehen
  38         *w = NUDS_to_I(y.MSDptr,y.len); // als Integer
  39         return squarep;
  40 }
  41 // Bit complexity (x of length N): O(M(N)).
  42
  43 }  // namespace cln