[fc732a9] | 1 | /* emacs edit mode for this file is -*- C++ -*- */ |
---|
| 2 | |
---|
[a34bee4] | 3 | /** |
---|
[b52d27] | 4 | * |
---|
| 5 | * @file int_intdiv.cc |
---|
| 6 | * |
---|
| 7 | * 'InternalInteger' division algorithms. |
---|
| 8 | * |
---|
| 9 | **/ |
---|
[fc732a9] | 10 | |
---|
[9f7665] | 11 | |
---|
[e4fe2b] | 12 | #include "config.h" |
---|
[9f7665] | 13 | |
---|
[fc732a9] | 14 | |
---|
[64df343] | 15 | #include "canonicalform.h" |
---|
[fc732a9] | 16 | #include "imm.h" |
---|
| 17 | #include "int_cf.h" |
---|
| 18 | #include "int_int.h" |
---|
| 19 | #include "int_rat.h" |
---|
[fb1675] | 20 | #include "factory/cf_gmp.h" |
---|
[fc732a9] | 21 | #include "gmpext.h" |
---|
[6db552] | 22 | #include "templates/ftmpl_functions.h" |
---|
[fc732a9] | 23 | |
---|
[b52d27] | 24 | /** |
---|
| 25 | * @sa CanonicalForm::operator /(), InternalInteger::dividecoeff() |
---|
| 26 | **/ |
---|
[fc732a9] | 27 | InternalCF * |
---|
| 28 | InternalInteger::dividesame ( InternalCF * c ) |
---|
| 29 | { |
---|
| 30 | ASSERT( ! ::is_imm( c ) && c->levelcoeff() == IntegerDomain, |
---|
[806c18] | 31 | "type error: InternalInteger expected" ); |
---|
[fc732a9] | 32 | |
---|
| 33 | if ( c == this ) { |
---|
[806c18] | 34 | if ( deleteObject() ) delete this; |
---|
| 35 | return int2imm( 1 ); |
---|
[fc732a9] | 36 | } |
---|
| 37 | |
---|
| 38 | if ( cf_glob_switches.isOn( SW_RATIONAL ) ) { |
---|
[a52291] | 39 | mpz_t n, d; |
---|
| 40 | mpz_init_set( n, thempi ); |
---|
| 41 | mpz_init_set( d, MPI( c ) ); |
---|
[806c18] | 42 | if ( deleteObject() ) delete this; |
---|
| 43 | InternalRational * result = new InternalRational( n, d ); |
---|
| 44 | return result->normalize_myself(); |
---|
[fc732a9] | 45 | } |
---|
| 46 | |
---|
| 47 | if ( getRefCount() > 1 ) { |
---|
[806c18] | 48 | decRefCount(); |
---|
[a52291] | 49 | mpz_t mpiResult; |
---|
| 50 | mpz_init( mpiResult ); |
---|
| 51 | if ( mpz_sgn( MPI( c ) ) > 0 ) |
---|
| 52 | mpz_fdiv_q( mpiResult, thempi, MPI( c ) ); |
---|
[806c18] | 53 | else |
---|
[a52291] | 54 | mpz_cdiv_q( mpiResult, thempi, MPI( c ) ); |
---|
[806c18] | 55 | return normalizeMPI( mpiResult ); |
---|
[fc732a9] | 56 | } else { |
---|
[a52291] | 57 | if ( mpz_sgn( MPI( c ) ) > 0 ) |
---|
| 58 | mpz_fdiv_q( thempi, thempi, MPI( c ) ); |
---|
[806c18] | 59 | else |
---|
[a52291] | 60 | mpz_cdiv_q( thempi, thempi, MPI( c ) ); |
---|
[806c18] | 61 | return normalizeMyself(); |
---|
[fc732a9] | 62 | } |
---|
| 63 | } |
---|
| 64 | |
---|
[b52d27] | 65 | /** |
---|
| 66 | * @sa CanonicalForm::operator /(), InternalInteger::dividesame() |
---|
| 67 | **/ |
---|
[fc732a9] | 68 | InternalCF * |
---|
| 69 | InternalInteger::dividecoeff ( InternalCF * c, bool invert ) |
---|
| 70 | { |
---|
| 71 | ASSERT( ::is_imm( c ) == INTMARK, |
---|
[806c18] | 72 | "type error: immediate integer expected" ); |
---|
[fc732a9] | 73 | ASSERT( invert || imm2int( c ) != 0, |
---|
[806c18] | 74 | "math error: divide by zero" ); |
---|
[fc732a9] | 75 | |
---|
[8710ff0] | 76 | long intC = imm2int( c ); |
---|
[fc732a9] | 77 | |
---|
| 78 | if ( cf_glob_switches.isOn( SW_RATIONAL ) ) { |
---|
[a52291] | 79 | mpz_t n, d; |
---|
[806c18] | 80 | if ( invert ) { |
---|
[a52291] | 81 | mpz_init_set_si( n, intC ); |
---|
| 82 | mpz_init_set( d, thempi ); |
---|
[806c18] | 83 | } else { |
---|
[a52291] | 84 | mpz_init_set( n, thempi ); |
---|
| 85 | mpz_init_set_si( d, intC ); |
---|
[806c18] | 86 | } |
---|
| 87 | if ( deleteObject() ) delete this; |
---|
| 88 | InternalRational * result = new InternalRational( n, d ); |
---|
| 89 | return result->normalize_myself(); |
---|
[fc732a9] | 90 | } |
---|
| 91 | |
---|
| 92 | if ( invert ) { |
---|
[a52291] | 93 | int mpiSign = mpz_sgn( thempi ); |
---|
[806c18] | 94 | if ( deleteObject() ) delete this; |
---|
| 95 | if ( intC >= 0 ) |
---|
| 96 | return int2imm( 0 ); |
---|
| 97 | else |
---|
| 98 | return int2imm( -mpiSign ); |
---|
[fc732a9] | 99 | } else if ( getRefCount() > 1 ) { |
---|
[806c18] | 100 | decRefCount(); |
---|
[a52291] | 101 | mpz_t mpiResult; |
---|
| 102 | mpz_init( mpiResult ); |
---|
[806c18] | 103 | if ( intC > 0 ) |
---|
[a52291] | 104 | mpz_fdiv_q_ui( mpiResult, thempi, intC ); |
---|
[806c18] | 105 | else { |
---|
[a52291] | 106 | mpz_fdiv_q_ui( mpiResult, thempi, -intC ); |
---|
| 107 | mpz_neg( mpiResult, mpiResult ); |
---|
[806c18] | 108 | } |
---|
| 109 | return normalizeMPI( mpiResult ); |
---|
[fc732a9] | 110 | } else { |
---|
[806c18] | 111 | if ( intC > 0 ) |
---|
[a52291] | 112 | mpz_fdiv_q_ui( thempi, thempi, intC ); |
---|
[806c18] | 113 | else { |
---|
[a52291] | 114 | mpz_fdiv_q_ui( thempi, thempi, -intC ); |
---|
| 115 | mpz_neg( thempi, thempi ); |
---|
[806c18] | 116 | } |
---|
| 117 | return normalizeMyself(); |
---|
[fc732a9] | 118 | } |
---|
| 119 | } |
---|
| 120 | |
---|
[b52d27] | 121 | /** |
---|
| 122 | * @sa CanonicalForm::div(), InternalInteger::divcoeff() |
---|
| 123 | **/ |
---|
[fc732a9] | 124 | InternalCF * |
---|
| 125 | InternalInteger::divsame ( InternalCF * c ) |
---|
| 126 | { |
---|
| 127 | ASSERT( ! ::is_imm( c ) && c->levelcoeff() == IntegerDomain, |
---|
[806c18] | 128 | "type error: InternalInteger expected" ); |
---|
[fc732a9] | 129 | |
---|
[b391de] | 130 | if ( c == this ) { |
---|
[806c18] | 131 | if ( deleteObject() ) delete this; |
---|
| 132 | return int2imm( 1 ); |
---|
[b391de] | 133 | } |
---|
| 134 | |
---|
[fc732a9] | 135 | if ( getRefCount() > 1 ) { |
---|
[806c18] | 136 | deleteObject(); |
---|
[a52291] | 137 | mpz_t mpiResult; |
---|
| 138 | mpz_init( mpiResult ); |
---|
| 139 | mpz_divexact( mpiResult, thempi, MPI( c ) ); |
---|
[806c18] | 140 | return normalizeMPI( mpiResult ); |
---|
[fc732a9] | 141 | } else { |
---|
[a52291] | 142 | mpz_divexact( thempi, thempi, MPI( c ) ); |
---|
[806c18] | 143 | return normalizeMyself(); |
---|
[fc732a9] | 144 | } |
---|
| 145 | } |
---|
| 146 | |
---|
[b52d27] | 147 | /** |
---|
| 148 | * @sa CanonicalForm::div(), InternalInteger::divsame() |
---|
| 149 | **/ |
---|
[fc732a9] | 150 | InternalCF * |
---|
| 151 | InternalInteger::divcoeff ( InternalCF * c, bool invert ) |
---|
| 152 | { |
---|
| 153 | ASSERT( ::is_imm( c ) == INTMARK, |
---|
[806c18] | 154 | "type error: immediate integer expected" ); |
---|
[b391de] | 155 | ASSERT( invert || imm2int( c ) != 0, |
---|
[806c18] | 156 | "math error: divide by zero" ); |
---|
[b391de] | 157 | ASSERT( ! invert || imm2int( c ) == 0, |
---|
[806c18] | 158 | "math error: c does not divide CO" ); |
---|
[fc732a9] | 159 | |
---|
| 160 | if ( invert ) { |
---|
[806c18] | 161 | if ( deleteObject() ) delete this; |
---|
| 162 | // this may happen iff `c' == 0 |
---|
| 163 | return int2imm( 0 ); |
---|
[fc732a9] | 164 | } else if ( getRefCount() > 1 ) { |
---|
[806c18] | 165 | deleteObject(); |
---|
[a52291] | 166 | mpz_t mpiC; |
---|
| 167 | mpz_t mpiResult; |
---|
| 168 | mpz_init_set_si( mpiC, imm2int( c ) ); |
---|
| 169 | mpz_init( mpiResult ); |
---|
| 170 | mpz_divexact( mpiResult, thempi, mpiC ); |
---|
| 171 | mpz_clear( mpiC ); |
---|
[806c18] | 172 | return normalizeMPI( mpiResult ); |
---|
[fc732a9] | 173 | } else { |
---|
[a52291] | 174 | mpz_t mpiC; |
---|
| 175 | mpz_init_set_si( mpiC, imm2int( c ) ); |
---|
| 176 | mpz_divexact( thempi, thempi, mpiC ); |
---|
| 177 | mpz_clear( mpiC ); |
---|
[806c18] | 178 | return normalizeMyself(); |
---|
[fc732a9] | 179 | } |
---|
| 180 | } |
---|
| 181 | |
---|
[b52d27] | 182 | /** |
---|
| 183 | * @sa CanonicalForm::operator %(), InternalInteger::modulocoeff() |
---|
| 184 | **/ |
---|
[fc732a9] | 185 | InternalCF * |
---|
| 186 | InternalInteger::modulosame ( InternalCF * c ) |
---|
| 187 | { |
---|
| 188 | ASSERT( ! ::is_imm( c ) && c->levelcoeff() == IntegerDomain, |
---|
[806c18] | 189 | "type error: InternalInteger expected" ); |
---|
[fc732a9] | 190 | |
---|
[b391de] | 191 | if ( (c == this) || cf_glob_switches.isOn( SW_RATIONAL ) ) { |
---|
[806c18] | 192 | if ( deleteObject() ) delete this; |
---|
| 193 | return int2imm( 0 ); |
---|
[fc732a9] | 194 | } |
---|
| 195 | |
---|
| 196 | if ( getRefCount() > 1 ) { |
---|
[806c18] | 197 | decRefCount(); |
---|
[a52291] | 198 | mpz_t mpiResult; |
---|
| 199 | mpz_init( mpiResult ); |
---|
| 200 | mpz_mod( mpiResult, thempi, MPI( c ) ); |
---|
[806c18] | 201 | return uiNormalizeMPI( mpiResult ); |
---|
[fc732a9] | 202 | } else { |
---|
[a52291] | 203 | mpz_mod( thempi, thempi, MPI( c ) ); |
---|
[806c18] | 204 | return uiNormalizeMyself(); |
---|
[fc732a9] | 205 | } |
---|
| 206 | } |
---|
| 207 | |
---|
[b52d27] | 208 | /** |
---|
| 209 | * @sa CanonicalForm::operator %(), InternalInteger::modulosame() |
---|
| 210 | **/ |
---|
[fc732a9] | 211 | InternalCF * |
---|
| 212 | InternalInteger::modulocoeff ( InternalCF * c, bool invert ) |
---|
| 213 | { |
---|
| 214 | ASSERT( ::is_imm( c ) == INTMARK, |
---|
[806c18] | 215 | "type error: immediate integer expected" ); |
---|
[fc732a9] | 216 | ASSERT( invert || imm2int( c ) != 0, |
---|
[806c18] | 217 | "math error: divide by zero" ); |
---|
[fc732a9] | 218 | |
---|
| 219 | if ( cf_glob_switches.isOn( SW_RATIONAL ) ) { |
---|
[806c18] | 220 | if ( deleteObject() ) delete this; |
---|
| 221 | return int2imm( 0 ); |
---|
[fc732a9] | 222 | } |
---|
| 223 | |
---|
[8710ff0] | 224 | long intC = imm2int( c ); |
---|
[fc732a9] | 225 | |
---|
| 226 | if ( invert ) { |
---|
[806c18] | 227 | if ( intC >= 0 ) { |
---|
| 228 | if ( deleteObject() ) delete this; |
---|
| 229 | return c; |
---|
| 230 | } else { |
---|
| 231 | // no checks for refCount == 1 are done. It is not worth ... |
---|
[a52291] | 232 | mpz_t mpiResult; |
---|
| 233 | mpz_init_set( mpiResult, thempi ); |
---|
| 234 | mpz_abs( mpiResult, mpiResult ); |
---|
| 235 | mpz_sub_ui( mpiResult, mpiResult, -intC ); |
---|
[806c18] | 236 | if ( deleteObject() ) delete this; |
---|
| 237 | return uiNormalizeMPI( mpiResult ); |
---|
| 238 | } |
---|
[fc732a9] | 239 | } else { |
---|
[a52291] | 240 | mpz_t dummy; |
---|
| 241 | mpz_init( dummy ); |
---|
| 242 | InternalCF * result = int2imm( mpz_mod_ui( dummy, thempi, tabs( intC ) ) ); |
---|
| 243 | mpz_clear( dummy ); |
---|
[806c18] | 244 | if ( deleteObject() ) delete this; |
---|
| 245 | return result; |
---|
[fc732a9] | 246 | } |
---|
| 247 | } |
---|
| 248 | |
---|
[b52d27] | 249 | /** |
---|
| 250 | * @sa see CanonicalForm::mod(), InternalInteger::modcoeff() |
---|
| 251 | **/ |
---|
[fc732a9] | 252 | InternalCF * |
---|
| 253 | InternalInteger::modsame ( InternalCF * c ) |
---|
| 254 | { |
---|
| 255 | return modulosame( c ); |
---|
| 256 | } |
---|
| 257 | |
---|
[b52d27] | 258 | /** |
---|
| 259 | * @sa see CanonicalForm::mod(), InternalInteger::modsame() |
---|
| 260 | **/ |
---|
[fc732a9] | 261 | InternalCF * |
---|
| 262 | InternalInteger::modcoeff ( InternalCF * c, bool invert ) |
---|
| 263 | { |
---|
| 264 | return modulocoeff( c, invert ); |
---|
| 265 | } |
---|
| 266 | |
---|
[b52d27] | 267 | /** |
---|
| 268 | * @sa CanonicalForm::divrem(), InternalInteger::divremcoeff() |
---|
| 269 | **/ |
---|
[fc732a9] | 270 | void |
---|
| 271 | InternalInteger::divremsame ( InternalCF * c, InternalCF * & quot, InternalCF * & rem ) |
---|
| 272 | { |
---|
[b391de] | 273 | ASSERT( ! ::is_imm( c ) && c->levelcoeff() == IntegerDomain, |
---|
[806c18] | 274 | "type error: InternalInteger expected" ); |
---|
[b391de] | 275 | |
---|
| 276 | if ( c == this ) { |
---|
[806c18] | 277 | quot = int2imm( 1 ); |
---|
| 278 | rem = int2imm( 0 ); |
---|
| 279 | return; |
---|
[fc732a9] | 280 | } |
---|
[b391de] | 281 | |
---|
| 282 | if ( cf_glob_switches.isOn( SW_RATIONAL ) ) { |
---|
[a52291] | 283 | mpz_t n, d; |
---|
| 284 | mpz_init_set( n, thempi ); |
---|
| 285 | mpz_init_set( d, MPI( c ) ); |
---|
[806c18] | 286 | InternalRational * result = new InternalRational( n, d ); |
---|
| 287 | quot = result->normalize_myself(); |
---|
| 288 | rem = int2imm( 0 ); |
---|
| 289 | return; |
---|
[fc732a9] | 290 | } |
---|
[b391de] | 291 | |
---|
[a52291] | 292 | mpz_t q; |
---|
| 293 | mpz_t r; |
---|
| 294 | mpz_init( q ); mpz_init( r ); |
---|
| 295 | if ( mpz_sgn( MPI( c ) ) > 0 ) |
---|
| 296 | mpz_fdiv_qr( q, r, thempi, MPI( c ) ); |
---|
[b391de] | 297 | else |
---|
[a52291] | 298 | mpz_cdiv_qr( q, r, thempi, MPI( c ) ); |
---|
[b391de] | 299 | |
---|
| 300 | quot = normalizeMPI( q ); |
---|
| 301 | rem = uiNormalizeMPI( r ); |
---|
[fc732a9] | 302 | } |
---|
| 303 | |
---|
[b52d27] | 304 | /** |
---|
| 305 | * @sa CanonicalForm::divrem(), InternalInteger::divremsame() |
---|
| 306 | **/ |
---|
[fc732a9] | 307 | void |
---|
| 308 | InternalInteger::divremcoeff ( InternalCF * c, InternalCF * & quot, InternalCF * & rem, bool invert ) |
---|
| 309 | { |
---|
[b391de] | 310 | ASSERT( ::is_imm( c ) == INTMARK, |
---|
[806c18] | 311 | "type error: immediate integer expected" ); |
---|
[b391de] | 312 | ASSERT( invert || imm2int( c ) != 0, |
---|
[806c18] | 313 | "math error: divide by zero" ); |
---|
[b391de] | 314 | |
---|
[8710ff0] | 315 | long intC = imm2int( c ); |
---|
[fc732a9] | 316 | |
---|
| 317 | if ( cf_glob_switches.isOn( SW_RATIONAL ) ) { |
---|
[a52291] | 318 | mpz_t n, d; |
---|
[806c18] | 319 | if ( invert ) { |
---|
[a52291] | 320 | mpz_init_set_si( n, intC ); |
---|
| 321 | mpz_init_set( d, thempi ); |
---|
[806c18] | 322 | } else { |
---|
[a52291] | 323 | mpz_init_set( n, thempi ); |
---|
| 324 | mpz_init_set_si( d, intC ); |
---|
[806c18] | 325 | } |
---|
| 326 | InternalRational * result = new InternalRational( n, d ); |
---|
| 327 | quot = result->normalize_myself(); |
---|
| 328 | rem = int2imm( 0 ); |
---|
| 329 | return; |
---|
[fc732a9] | 330 | } |
---|
| 331 | |
---|
| 332 | if ( invert ) { |
---|
[806c18] | 333 | if ( intC >= 0 ) { |
---|
| 334 | rem = c; |
---|
| 335 | quot = int2imm( 0 ); |
---|
| 336 | } else { |
---|
[a52291] | 337 | mpz_t mpiResult; |
---|
| 338 | mpz_init_set( mpiResult, thempi ); |
---|
| 339 | mpz_abs( mpiResult, mpiResult ); |
---|
| 340 | mpz_sub_ui( mpiResult, mpiResult, -intC ); |
---|
[806c18] | 341 | rem = uiNormalizeMPI( mpiResult ); |
---|
[a52291] | 342 | quot = int2imm( -mpz_sgn( thempi ) ); |
---|
[806c18] | 343 | } |
---|
[b391de] | 344 | } else { |
---|
[a52291] | 345 | mpz_t q; |
---|
| 346 | mpz_t dummy; |
---|
| 347 | mpz_init( q ); mpz_init( dummy ); |
---|
[806c18] | 348 | if ( intC > 0 ) { |
---|
[a52291] | 349 | rem = int2imm( mpz_fdiv_qr_ui( q, dummy, thempi, intC ) ); |
---|
[806c18] | 350 | quot = normalizeMPI( q ); |
---|
| 351 | } else { |
---|
[a52291] | 352 | rem = int2imm( mpz_fdiv_qr_ui( q, dummy, thempi, -intC ) ); |
---|
| 353 | mpz_neg( q, q ); |
---|
[806c18] | 354 | quot = normalizeMPI( q ); |
---|
| 355 | } |
---|
[a52291] | 356 | mpz_clear( dummy ); |
---|
[fc732a9] | 357 | } |
---|
| 358 | } |
---|
| 359 | |
---|
[b52d27] | 360 | /** |
---|
[a34bee4] | 361 | * @sa CanonicalForm::divremt(), InternalInteger::divremcoefft() |
---|
[b52d27] | 362 | **/ |
---|
[fc732a9] | 363 | bool |
---|
| 364 | InternalInteger::divremsamet ( InternalCF * c, InternalCF * & quot, InternalCF * & rem ) |
---|
| 365 | { |
---|
| 366 | divremsame( c, quot, rem ); |
---|
| 367 | return true; |
---|
| 368 | } |
---|
| 369 | |
---|
[b52d27] | 370 | /** |
---|
[a34bee4] | 371 | * @sa CanonicalForm::divremt(), InternalInteger::divremsamet() |
---|
[b52d27] | 372 | **/ |
---|
[fc732a9] | 373 | bool |
---|
| 374 | InternalInteger::divremcoefft ( InternalCF * c, InternalCF * & quot, InternalCF * & rem, bool invert ) |
---|
| 375 | { |
---|
| 376 | divremcoeff( c, quot, rem, invert ); |
---|
| 377 | return true; |
---|
| 378 | } |
---|