4 #include "base/cl_sysdep.h"
7 #include "cln/integer.h"
12 #include "base/digitseq/cl_DS.h"
13 #include "base/digitseq/cl_2DS.h"
14 #include "integer/bitwise/cl_I_log.h"
18 const cl_I cl_recip2adic (uintL n, const cl_I& x)
20 var uintL len = ceiling(n,intDsize);
22 var const uintD* x_LSDptr;
23 if (bignump(x) && TheBignum(x)->length >= len)
25 x_LSDptr = BN_LSDptr(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;
33 num_stack_alloc_1(len,,y_LSDptr=);
34 // Compute inverse mod 2^(intDsize*len).
35 recip2adic(len,x_LSDptr,y_LSDptr);
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);
41 // Bit complexity (N := n): O(M(N)).