src/integer/2adic/cl_I_2adic_div.cc

   1 // cl_div2adic().
   2
   3 // General includes.
   4 #include "base/cl_sysdep.h"
   5
   6 // Specification.
   7 #include "cln/integer.h"
   8
   9
  10 // Implementation.
  11
  12 #include "base/digitseq/cl_DS.h"
  13 #include "base/digitseq/cl_2DS.h"
  14 #include "integer/bitwise/cl_I_log.h"
  15
  16 namespace cln {
  17
  18 const cl_I cl_div2adic (uintL n, const cl_I& x, const cl_I& y)
  19 {
  20         var uintL len = ceiling(n,intDsize);
  21         CL_ALLOCA_STACK;
  22         var const uintD* x_LSDptr;
  23         var const uintD* y_LSDptr;
  24         if (bignump(x) && TheBignum(x)->length >= len)
  25                 // no need to copy x
  26                 x_LSDptr = BN_LSDptr(x);
  27         else {  // copy x
  28                 var uintL x_len = I_to_DS_need(x);
  29                 if (x_len < len) { x_len = len; }
  30                 I_to_DS_n(x,x_len,x_LSDptr=);
  31                 x_LSDptr = x_LSDptr mspop x_len;
  32         }
  33         if (bignump(y) && TheBignum(y)->length >= len)
  34                 // no need to copy y
  35                 y_LSDptr = BN_LSDptr(y);
  36         else {  // copy y
  37                 var uintL y_len = I_to_DS_need(y);
  38                 if (y_len < len) { y_len = len; }
  39                 I_to_DS_n(y,y_len,y_LSDptr=);
  40                 y_LSDptr = y_LSDptr mspop y_len;
  41         }
  42         var uintD* z_LSDptr;
  43         num_stack_alloc_1(len,,z_LSDptr=);
  44         // Compute quotient mod 2^(intDsize*len).
  45         div2adic(len,x_LSDptr,y_LSDptr,z_LSDptr);
  46         // Reduce mod 2^n.
  47         if ((n % intDsize) != 0)
  48                 lspref(z_LSDptr,floor(n,intDsize)) &= (bit(n % intDsize) - 1);
  49         return UDS_to_I(z_LSDptr lspop len,len);
  50 }
  51 // Bit complexity (N := n): O(M(N)).
  52
  53 }  // namespace cln