diff options
author | lianah <lianahady@gmail.com> | 2013-02-01 19:43:37 -0500 |
---|---|---|
committer | lianah <lianahady@gmail.com> | 2013-02-01 19:43:37 -0500 |
commit | 764bda53ed154495286d7ff117aa7182a8ce5f7b (patch) | |
tree | ad0466a34055b19b1d91e0590415f7e93cee8f27 /src/util/integer_gmp_imp.h | |
parent | f0988a89ecc0e5f2995dc8d390b5e9df2fa5421f (diff) | |
parent | 8c5e895525ec87ba0285c281b45144eab79b66f9 (diff) |
merged master into branch
Diffstat (limited to 'src/util/integer_gmp_imp.h')
-rw-r--r-- | src/util/integer_gmp_imp.h | 79 |
1 files changed, 71 insertions, 8 deletions
diff --git a/src/util/integer_gmp_imp.h b/src/util/integer_gmp_imp.h index d6882b6ac..85d49f921 100644 --- a/src/util/integer_gmp_imp.h +++ b/src/util/integer_gmp_imp.h @@ -199,16 +199,16 @@ public: mpz_class res = d_value; for (unsigned i = size; i < size + amount; ++i) { - mpz_setbit(res.get_mpz_t(), i); + mpz_setbit(res.get_mpz_t(), i); } - - return Integer(res); + + return Integer(res); } - + uint32_t toUnsignedInt() const { return mpz_get_ui(d_value.get_mpz_t()); } - + /** See GMP Documentation. */ Integer extractBitRange(uint32_t bitCount, uint32_t low) const { // bitCount = high-low+1 @@ -265,6 +265,61 @@ public: } /** + * Computes a quoitent and remainder according to Boute's Euclidean definition. + * euclidianDivideQuotient, euclidianDivideRemainder. + * + * Boute, Raymond T. (April 1992). + * The Euclidean definition of the functions div and mod. + * ACM Transactions on Programming Languages and Systems (TOPLAS) + * ACM Press. 14 (2): 127 - 144. doi:10.1145/128861.128862. + */ + static void euclidianQR(Integer& q, Integer& r, const Integer& x, const Integer& y) { + // compute the floor and then fix the value up if needed. + floorQR(q,r,x,y); + + if(r.strictlyNegative()){ + // if r < 0 + // abs(r) < abs(y) + // - abs(y) < r < 0, then 0 < r + abs(y) < abs(y) + // n = y * q + r + // n = y * q - abs(y) + r + abs(y) + if(r.sgn() >= 0){ + // y = abs(y) + // n = y * q - y + r + y + // n = y * (q-1) + (r+y) + q -= 1; + r += y; + }else{ + // y = -abs(y) + // n = y * q + y + r - y + // n = y * (q+1) + (r-y) + q += 1; + r -= y; + } + } + } + /** + * Returns the quoitent according to Boute's Euclidean definition. + * See the documentation for euclidianQR. + */ + Integer euclidianDivideQuotient(const Integer& y) const { + Integer q,r; + euclidianQR(q,r, *this, y); + return q; + } + + /** + * Returns the remainfing according to Boute's Euclidean definition. + * See the documentation for euclidianQR. + */ + Integer euclidianDivideRemainder(const Integer& y) const { + Integer q,r; + euclidianQR(q,r, *this, y); + return r; + } + + + /** * If y divides *this, then exactQuotient returns (this/y) */ Integer exactQuotient(const Integer& y) const { @@ -278,7 +333,7 @@ public: * Returns y mod 2^exp */ Integer modByPow2(uint32_t exp) const { - mpz_class res; + mpz_class res; mpz_fdiv_r_2exp(res.get_mpz_t(), d_value.get_mpz_t(), exp); return Integer(res); } @@ -292,12 +347,20 @@ public: return Integer(res); } - + int sgn() const { return mpz_sgn(d_value.get_mpz_t()); } - bool isZero() const { + inline bool strictlyPositive() const { + return sgn() > 0; + } + + inline bool strictlyNegative() const { + return sgn() < 0; + } + + inline bool isZero() const { return sgn() == 0; } |