1 // cl_recip2adic().
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
cl_recip2adic(uintL n,const cl_I & x)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
44