Initial revision

[cln.git] / src / integer / 2adic / cl_I_2adic_div.cc

diff --git a/src/integer/2adic/cl_I_2adic_div.cc b/src/integer/2adic/cl_I_2adic_div.cc
new file mode 100644 (file)
index 0000000..97791fe
--- /dev/null
+++ b/src/integer/2adic/cl_I_2adic_div.cc
@@ -0,0 +1,50 @@
+// cl_div2adic().
+
+// General includes.
+#include "cl_sysdep.h"
+
+// Specification.
+#include "cl_integer.h"
+
+
+// Implementation.
+
+#include "cl_DS.h"
+#include "cl_2DS.h"
+#include "cl_I_log.h"
+
+const cl_I cl_div2adic (uintL n, const cl_I& x, const cl_I& y)
+{
+       var uintL len = ceiling(n,intDsize);
+       CL_ALLOCA_STACK;
+       var const uintD* x_LSDptr;
+       var const uintD* y_LSDptr;
+       if (bignump(x) && TheBignum(x)->length >= len)
+               // no need to copy x
+               x_LSDptr = BN_LSDptr(x);
+       else {  // copy x
+               var uintL x_len = I_to_DS_need(x);
+               if (x_len < len) { x_len = len; }
+               I_to_DS_n(x,x_len,x_LSDptr=);
+               x_LSDptr = x_LSDptr mspop x_len;
+       }
+       if (bignump(y) && TheBignum(y)->length >= len)
+               // no need to copy y
+               y_LSDptr = BN_LSDptr(y);
+       else {  // copy y
+               var uintL y_len = I_to_DS_need(y);
+               if (y_len < len) { y_len = len; }
+               I_to_DS_n(y,y_len,y_LSDptr=);
+               y_LSDptr = y_LSDptr mspop y_len;
+       }
+       var uintD* z_LSDptr;
+       num_stack_alloc_1(len,,z_LSDptr=);
+       // Compute quotient mod 2^(intDsize*len).
+       div2adic(len,x_LSDptr,y_LSDptr,z_LSDptr);
+       // Reduce mod 2^n.
+       if ((n % intDsize) != 0)
+               lspref(z_LSDptr,floor(n,intDsize)) &= (bit(n % intDsize) - 1);
+       return UDS_to_I(z_LSDptr lspop len,len);
+}
+// Bit complexity (N := n): O(M(N)).
+