12 #include "cln/exception.h"
16 // Dividiert zwei Integers x,y >=0 und liefert Quotient und Rest
17 // der Division x/y. Bei y=0 Error.
19 // > x,y: Integers >=0
20 // < q,r: Quotient q, Rest r
21 const cl_I_div_t cl_divide (const cl_I& x, const cl_I& y)
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(); }
30 // Trivialfall: q=0, r=x
37 // 64-durch-32-Bit-Division
40 divu_6432_6432(x_,y_,q=,r=);
42 /* result.quotient = */ UQ_to_I(q),
43 /* result.remainder = */ UL_to_I(r)
47 // volle 64-durch-64-Bit-Division
50 divu_6464_6464(x_,y_,q=,r=);
52 /* result.quotient = */ UQ_to_I(q),
53 /* result.remainder = */ UQ_to_I(r)
60 // 32-durch-16-Bit-Division
63 divu_3216_3216(x_,y_,q=,r=);
65 /* result.quotient = */ UL_to_I(q),
66 /* result.remainder = */ L_to_FN((uintL)r)
70 // volle 32-durch-32-Bit-Division
73 divu_3232_3232(x_,y_,q=,r=);
75 /* result.quotient = */ UL_to_I(q),
76 /* result.remainder = */ UL_to_I(r)
85 // Trivialfall: q=0, r=x
87 /* result.quotient = */ 0,
88 /* result.remainder = */ x
93 // x Bignum -> allgemeine Division:
95 var const uintD* x_MSDptr;
97 var const uintD* x_LSDptr;
98 var const uintD* y_MSDptr;
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=,/*cl_true*/cl_false,);
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!):
114 /* result.remainder = */ NUDS_to_I(r.MSDptr,r.len)
118 // Bit complexity (N = length(x)): O(M(N)).