src/integer/elem/cl_I_div.cc

   1 // cl_divide().
   2
   3 // General includes.
   4 #include "cl_sysdep.h"
   5
   6 // Specification.
   7 #include "cl_I.h"
   8
   9
  10 // Implementation.
  11
  12 #include "cl_N.h"
  13
  14 // Dividiert zwei Integers x,y >=0 und liefert Quotient und Rest
  15 // der Division x/y. Bei y=0 Error.
  16 // cl_divide(x,y)
  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)
  20     { if (fixnump(x))
  21         // x Fixnum >=0
  22         { if (fixnump(y))
  23             // auch y Fixnum >=0
  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(); }
  27               elif (x_ < y_)
  28                 // Trivialfall: q=0, r=x
  29                 goto trivial;
  30               elif (y_ < bit(16))
  31                 // 32-durch-16-Bit-Division
  32                 { var uint32 q;
  33                   var uint16 r;
  34                   divu_3216_3216(x_,y_,q=,r=);
  35                   return cl_I_div_t(
  36                     /* result.quotient =  */ UL_to_I(q),
  37                     /* result.remainder = */ L_to_FN((uintL)r)
  38                     );
  39                 }
  40               else
  41                 // volle 32-durch-32-Bit-Division
  42                 { var uint32 q;
  43                   var uint32 r;
  44                   divu_3232_3232(x_,y_,q=,r=);
  45                   return cl_I_div_t(
  46                     /* result.quotient =  */ UL_to_I(q),
  47                     /* result.remainder = */ UL_to_I(r)
  48                     );
  49                 }
  50             }
  51             else
  52             // y Bignum >0
  53             { trivial:
  54               // Trivialfall: q=0, r=x
  55               return cl_I_div_t(
  56                 /* result.quotient =  */ 0,
  57                 /* result.remainder = */ x
  58                 );
  59             }
  60         }
  61         else
  62         // x Bignum -> allgemeine Division:
  63         { CL_ALLOCA_STACK;
  64           var const uintD* x_MSDptr;
  65           var uintC x_len;
  66           var const uintD* x_LSDptr;
  67           var const uintD* y_MSDptr;
  68           var uintC y_len;
  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,);
  74           // dividieren:
  75          {var DS q;
  76           var DS r;
  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!):
  81           return cl_I_div_t(
  82             quotient,
  83             /* result.remainder = */ NUDS_to_I(r.MSDptr,r.len)
  84             );
  85         }}
  86     }
  87 // Bit complexity (N = length(x)): O(M(N)).
  88