src/integer/algebraic/cl_I_sqrt.cc

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