4 #include "base/cl_sysdep.h"
7 #include "cln/integer.h"
12 #include "cln/number.h"
14 #include "cln/integer_io.h"
15 #include "cln/exception.h"
16 #include "integer/cl_I.h"
17 #include "base/digitseq/cl_DS.h"
22 bool isqrt (const cl_I& x, cl_I* w)
25 std::ostringstream buf;
26 fprint(buf, "isqrt: applied to negative number: ");
28 throw runtime_exception(buf.str());
31 var const uintD* x_MSDptr;
33 var const uintD* x_LSDptr;
34 I_to_NDS_nocopy(x, x_MSDptr=,x_len=,x_LSDptr=,true,); // Digit sequence >=0 zu x
37 UDS_sqrt(x_MSDptr,x_len,x_LSDptr, &y, squarep=); // Wurzel ziehen
38 *w = NUDS_to_I(y.MSDptr,y.len); // als Integer
41 // Bit complexity (x of length N): O(M(N)).