14 // Dividiert zwei Integers x,y >=0 und liefert Quotient und Rest
15 // der Division x/y. Bei y=0 Error.
17 // > x,y: Integers >=0
18 // < q,r: Quotient q, Rest r
19 const cl_I_div_t cl_divide (const cl_I& x, const cl_I& y)
24 { var uint32 x_ = FN_to_UL(x);
25 var uint32 y_ = FN_to_UL(y);
26 if (y_==0) { cl_error_division_by_0(); }
28 // Trivialfall: q=0, r=x
31 // 32-durch-16-Bit-Division
34 divu_3216_3216(x_,y_,q=,r=);
36 /* result.quotient = */ UL_to_I(q),
37 /* result.remainder = */ L_to_FN((uintL)r)
41 // volle 32-durch-32-Bit-Division
44 divu_3232_3232(x_,y_,q=,r=);
46 /* result.quotient = */ UL_to_I(q),
47 /* result.remainder = */ UL_to_I(r)
54 // Trivialfall: q=0, r=x
56 /* result.quotient = */ 0,
57 /* result.remainder = */ x
62 // x Bignum -> allgemeine Division:
64 var const uintD* x_MSDptr;
66 var const uintD* x_LSDptr;
67 var const uintD* y_MSDptr;
69 var const uintD* y_LSDptr;
70 // x in NDS umwandeln, als UDS auffassen:
71 BN_to_NDS_nocopy(x, x_MSDptr=,x_len=,x_LSDptr=);
72 // y in NDS umwandeln, als UDS auffassen:
73 I_to_NDS_nocopy(y, y_MSDptr=,y_len=,y_LSDptr=,/*cl_true*/cl_false,);
77 UDS_divide(x_MSDptr,x_len,x_LSDptr,y_MSDptr,y_len,y_LSDptr, &q,&r);
78 // q in Integer umwandeln:
79 var cl_I quotient = NUDS_to_I(q.MSDptr,q.len);
80 // r in Integer umwandeln (jetzt erst, nachdem q verwertet ist!):
83 /* result.remainder = */ NUDS_to_I(r.MSDptr,r.len)
87 // Bit complexity (N = length(x)): O(M(N)).