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 uint32 x_ = FN_to_UL(x);
27 var uint32 y_ = FN_to_UL(y);
28 if (y_==0) { cl_error_division_by_0(); }
30 // Trivialfall: q=0, r=x
33 // 32-durch-16-Bit-Division
36 divu_3216_3216(x_,y_,q=,r=);
38 /* result.quotient = */ UL_to_I(q),
39 /* result.remainder = */ L_to_FN((uintL)r)
43 // volle 32-durch-32-Bit-Division
46 divu_3232_3232(x_,y_,q=,r=);
48 /* result.quotient = */ UL_to_I(q),
49 /* result.remainder = */ UL_to_I(r)
56 // Trivialfall: q=0, r=x
58 /* result.quotient = */ 0,
59 /* result.remainder = */ x
64 // x Bignum -> allgemeine Division:
66 var const uintD* x_MSDptr;
68 var const uintD* x_LSDptr;
69 var const uintD* y_MSDptr;
71 var const uintD* y_LSDptr;
72 // x in NDS umwandeln, als UDS auffassen:
73 BN_to_NDS_nocopy(x, x_MSDptr=,x_len=,x_LSDptr=);
74 // y in NDS umwandeln, als UDS auffassen:
75 I_to_NDS_nocopy(y, y_MSDptr=,y_len=,y_LSDptr=,/*cl_true*/cl_false,);
79 UDS_divide(x_MSDptr,x_len,x_LSDptr,y_MSDptr,y_len,y_LSDptr, &q,&r);
80 // q in Integer umwandeln:
81 var cl_I quotient = NUDS_to_I(q.MSDptr,q.len);
82 // r in Integer umwandeln (jetzt erst, nachdem q verwertet ist!):
85 /* result.remainder = */ NUDS_to_I(r.MSDptr,r.len)
89 // Bit complexity (N = length(x)): O(M(N)).