src/integer/2adic/cl_I_2adic_recip.cc

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