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 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
  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 uint32 x_ = FN_to_UL(x);
  27               var uint32 y_ = FN_to_UL(y);
  28               if (y_==0) { cl_error_division_by_0(); }
  29               elif (x_ < y_)
  30                 // Trivialfall: q=0, r=x
  31                 goto trivial;
  32               elif (y_ < bit(16))
  33                 // 32-durch-16-Bit-Division
  34                 { var uint32 q;
  35                   var uint16 r;
  36                   divu_3216_3216(x_,y_,q=,r=);
  37                   return cl_I_div_t(
  38                     /* result.quotient =  */ UL_to_I(q),
  39                     /* result.remainder = */ L_to_FN((uintL)r)
  40                     );
  41                 }
  42               else
  43                 // volle 32-durch-32-Bit-Division
  44                 { var uint32 q;
  45                   var uint32 r;
  46                   divu_3232_3232(x_,y_,q=,r=);
  47                   return cl_I_div_t(
  48                     /* result.quotient =  */ UL_to_I(q),
  49                     /* result.remainder = */ UL_to_I(r)
  50                     );
  51                 }
  52             }
  53             else
  54             // y Bignum >0
  55             { trivial:
  56               // Trivialfall: q=0, r=x
  57               return cl_I_div_t(
  58                 /* result.quotient =  */ 0,
  59                 /* result.remainder = */ x
  60                 );
  61             }
  62         }
  63         else
  64         // x Bignum -> allgemeine Division:
  65         { CL_ALLOCA_STACK;
  66           var const uintD* x_MSDptr;
  67           var uintC x_len;
  68           var const uintD* x_LSDptr;
  69           var const uintD* y_MSDptr;
  70           var uintC y_len;
  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,);
  76           // dividieren:
  77          {var DS q;
  78           var DS r;
  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!):
  83           return cl_I_div_t(
  84             quotient,
  85             /* result.remainder = */ NUDS_to_I(r.MSDptr,r.len)
  86             );
  87         }}
  88     }
  89 // Bit complexity (N = length(x)): O(M(N)).
  90
  91 }  // namespace cln