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 "cl_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 const cl_I cl_recip2adic (uintL n, const cl_I& x)
  17 {
  18         var uintL len = ceiling(n,intDsize);
  19         CL_ALLOCA_STACK;
  20         var const uintD* x_LSDptr;
  21         if (bignump(x) && TheBignum(x)->length >= len)
  22                 // no need to copy x
  23                 x_LSDptr = BN_LSDptr(x);
  24         else {  // copy x
  25                 var uintL x_len = I_to_DS_need(x);
  26                 if (x_len < len) { x_len = len; }
  27                 I_to_DS_n(x,x_len,x_LSDptr=);
  28                 x_LSDptr = x_LSDptr mspop x_len;
  29         }
  30         var uintD* y_LSDptr;
  31         num_stack_alloc_1(len,,y_LSDptr=);
  32         // Compute inverse mod 2^(intDsize*len).
  33         recip2adic(len,x_LSDptr,y_LSDptr);
  34         // Reduce mod 2^n.
  35         if ((n % intDsize) != 0)
  36                 lspref(y_LSDptr,floor(n,intDsize)) &= (bit(n % intDsize) - 1);
  37         return UDS_to_I(y_LSDptr lspop len,len);
  38 }
  39 // Bit complexity (N := n): O(M(N)).
  40