1 // cl_divide().
2 
3 // General includes.
4 #include "base/cl_sysdep.h"
5 
6 // Specification.
7 #include "integer/cl_I.h"
8 
9 
10 // Implementation.
11 
12 #include "cln/exception.h"
13 
14 namespace cln {
15 
16 // Dividiert zwei Integers x,y >=0 und liefert Quotient und Rest
17 // der Division x/y. Bei y=0 Error.
18 // cl_divide(x,y)
19 // > x,y: Integers >=0
20 // < q,r: Quotient q, Rest r
cl_divide(const cl_I & x,const cl_I & y)21   const cl_I_div_t cl_divide (const cl_I& x, const cl_I& y)
22     { if (fixnump(x))
23         // x Fixnum >=0
24         { if (fixnump(y))
25             // auch y Fixnum >=0
26             { var uintV x_ = FN_to_UV(x);
27               var uintV y_ = FN_to_UV(y);
28               if (y_==0) { throw division_by_0_exception(); }
29               elif (x_ < y_)
30                 // Trivialfall: q=0, r=x
31                 goto trivial;
32               else
33                 {
34                   #if (intVsize>32)
35                   if (x_ >= bit(32))
36                     { if (y_ < bit(32))
37                         // 64-durch-32-Bit-Division
38                         { var uint64 q;
39                           var uint32 r;
40                           divu_6432_6432(x_,y_,q=,r=);
41                           return cl_I_div_t(
42                             /* result.quotient =  */ UQ_to_I(q),
43                             /* result.remainder = */ UL_to_I(r)
44                             );
45                         }
46                       else
47                         // volle 64-durch-64-Bit-Division
48                         { var uint64 q;
49                           var uint64 r;
50                           divu_6464_6464(x_,y_,q=,r=);
51                           return cl_I_div_t(
52                             /* result.quotient =  */ UQ_to_I(q),
53                             /* result.remainder = */ UQ_to_I(r)
54                             );
55                         }
56                     }
57                   else
58                   #endif
59                     { if (y_ < bit(16))
60                         // 32-durch-16-Bit-Division
61                         { var uint32 q;
62                           var uint16 r;
63                           divu_3216_3216(x_,y_,q=,r=);
64                           return cl_I_div_t(
65                             /* result.quotient =  */ UL_to_I(q),
66                             /* result.remainder = */ L_to_FN((uintL)r)
67                             );
68                         }
69                       else
70                         // volle 32-durch-32-Bit-Division
71                         { var uint32 q;
72                           var uint32 r;
73                           divu_3232_3232(x_,y_,q=,r=);
74                           return cl_I_div_t(
75                             /* result.quotient =  */ UL_to_I(q),
76                             /* result.remainder = */ UL_to_I(r)
77                             );
78                         }
79                     }
80                 }
81             }
82             else
83             // y Bignum >0
84             { trivial:
85               // Trivialfall: q=0, r=x
86               return cl_I_div_t(
87                 /* result.quotient =  */ 0,
88                 /* result.remainder = */ x
89                 );
90             }
91         }
92         else
93         // x Bignum -> allgemeine Division:
94         { CL_ALLOCA_STACK;
95           var const uintD* x_MSDptr;
96           var uintC x_len;
97           var const uintD* x_LSDptr;
98           var const uintD* y_MSDptr;
99           var uintC y_len;
100           var const uintD* y_LSDptr;
101           // x in NDS umwandeln, als UDS auffassen:
102           BN_to_NDS_nocopy(x, x_MSDptr=,x_len=,x_LSDptr=);
103           // y in NDS umwandeln, als UDS auffassen:
104           I_to_NDS_nocopy(y, y_MSDptr=,y_len=,y_LSDptr=,/*true*/false,);
105           // dividieren:
106          {var DS q;
107           var DS r;
108           UDS_divide(x_MSDptr,x_len,x_LSDptr,y_MSDptr,y_len,y_LSDptr, &q,&r);
109           // q in Integer umwandeln:
110           var cl_I quotient = NUDS_to_I(q.MSDptr,q.len);
111           // r in Integer umwandeln (jetzt erst, nachdem q verwertet ist!):
112           return cl_I_div_t(
113             quotient,
114             /* result.remainder = */ NUDS_to_I(r.MSDptr,r.len)
115             );
116         }}
117     }
118 // Bit complexity (N = length(x)): O(M(N)).
119 
120 }  // namespace cln
121