From 5be9822d180df6c9f26584387af7ab054aad0cc1 Mon Sep 17 00:00:00 2001 From: Richard Kreckel Date: Tue, 30 Apr 2002 23:42:41 +0000 Subject: [PATCH] * Globalize the hash-value-space. --- ginac/add.cpp | 5 ----- ginac/add.h | 1 - ginac/basic.cpp | 27 +++++++++++++-------------- ginac/constant.cpp | 6 ++---- ginac/expairseq.cpp | 15 ++++++--------- ginac/function.pl | 4 ++-- ginac/matrix.cpp | 2 +- ginac/mul.cpp | 21 ++++++++------------- ginac/mul.h | 1 - ginac/numeric.cpp | 2 +- ginac/numeric.h | 3 --- ginac/relational.cpp | 7 ++----- ginac/symbol.cpp | 5 +---- ginac/utils.h | 39 +++++++++++++++------------------------ 14 files changed, 51 insertions(+), 87 deletions(-) diff --git a/ginac/add.cpp b/ginac/add.cpp index e6fb727e..bde5b2b7 100644 --- a/ginac/add.cpp +++ b/ginac/add.cpp @@ -420,11 +420,6 @@ int add::compare_same_type(const basic & other) const return inherited::compare_same_type(other); } -bool add::is_equal_same_type(const basic & other) const -{ - return inherited::is_equal_same_type(other); -} - unsigned add::return_type(void) const { if (seq.empty()) diff --git a/ginac/add.h b/ginac/add.h index 92888919..032267e6 100644 --- a/ginac/add.h +++ b/ginac/add.h @@ -62,7 +62,6 @@ public: ex simplify_ncmul(const exvector & v) const; protected: ex derivative(const symbol & s) const; - bool is_equal_same_type(const basic & other) const; unsigned return_type(void) const; unsigned return_type_tinfo(void) const; ex thisexpairseq(const epvector & v, const ex & oc) const; diff --git a/ginac/basic.cpp b/ginac/basic.cpp index d4f06fe8..1b810926 100644 --- a/ginac/basic.cpp +++ b/ginac/basic.cpp @@ -639,13 +639,10 @@ unsigned basic::calchash(void) const { unsigned v = golden_ratio_hash(tinfo()); for (unsigned i=0; i(this))->op(i).gethash(); } - - // mask out numeric hashes: - v &= 0x7FFFFFFFU; - + // store calculated hash value only if object is already evaluated if (flags & status_flags::evaluated) { setflag(status_flags::hash_calculated); @@ -707,7 +704,9 @@ ex basic::subs(const ex & e, bool no_pattern) const return subs(ls, lr, no_pattern); } -/** Compare objects to establish canonical ordering. +extern "C" { int putchar(int c); } // FIXME: removeme + +/** Compare objects syntactically to establish canonical ordering. * All compare functions return: -1 for *this less than other, 0 equal, * 1 greater. */ int basic::compare(const basic & other) const @@ -722,7 +721,7 @@ int basic::compare(const basic & other) const if (typeid_this==typeid_other) { GINAC_ASSERT(typeid(*this)==typeid(other)); // int cmpval = compare_same_type(other); -// if ((cmpval!=0) && (hash_this<0x80000000U)) { +// if (cmpval!=0) { // std::cout << "hash collision, same type: " // << *this << " and " << other << std::endl; // this->print(print_tree(std::cout)); @@ -733,17 +732,17 @@ int basic::compare(const basic & other) const // return cmpval; return compare_same_type(other); } else { -// std::cout << "hash collision, different types: " -// << *this << " and " << other << std::endl; -// this->print(print_tree(std::cout)); -// std::cout << " and "; -// other.print(print_tree(std::cout)); -// std::cout << std::endl; +// std::cout << "hash collision, different types: " +// << *this << " and " << other << std::endl; +// this->print(print_tree(std::cout)); +// std::cout << " and "; +// other.print(print_tree(std::cout)); +// std::cout << std::endl; return (typeid_thisrest.gethash(); #if !EXPAIRSEQ_USE_HASHTAB // rotation spoils commutativity! - v = rotate_left_31(v); + v = rotate_left(v); v ^= i->coeff.gethash(); #endif // !EXPAIRSEQ_USE_HASHTAB ++i; } - + v ^= overall_coeff.gethash(); - v &= 0x7FFFFFFFU; - + // store calculated hash value only if object is already evaluated if (flags &status_flags::evaluated) { setflag(status_flags::hash_calculated); @@ -1122,7 +1121,7 @@ unsigned expairseq::calc_hashtabsize(unsigned sz) const size = nearest_power_of_2/hashtabfactor; if (size(e)) { hashindex = hashmask; } else { - hashindex = hash &hashmask; + hashindex = e.gethash() & hashmask; // last hashtab entry is reserved for numerics if (hashindex==hashmask) hashindex = 0; } - GINAC_ASSERT(hashindex>=0); GINAC_ASSERT((hashindexop(i).gethash(); } - v &= 0x7FFFFFFFU; + if (flags & status_flags::evaluated) { setflag(status_flags::hash_calculated); hashvalue = v; diff --git a/ginac/matrix.cpp b/ginac/matrix.cpp index 5a68f132..7421e149 100644 --- a/ginac/matrix.cpp +++ b/ginac/matrix.cpp @@ -1288,7 +1288,7 @@ int matrix::fraction_free_elimination(const bool det) // // Bareiss (fraction-free) elimination in addition divides that element // by m[k-1](k-1,k-1) for k>1, where it can be shown by means of the - // Sylvester determinant that this really divides m[k+1](r,c). + // Sylvester identity that this really divides m[k+1](r,c). // // We also allow rational functions where the original prove still holds. // However, we must care for numerator and denominator separately and diff --git a/ginac/mul.cpp b/ginac/mul.cpp index cc7d41ae..8127c316 100644 --- a/ginac/mul.cpp +++ b/ginac/mul.cpp @@ -507,11 +507,6 @@ int mul::compare_same_type(const basic & other) const return inherited::compare_same_type(other); } -bool mul::is_equal_same_type(const basic & other) const -{ - return inherited::is_equal_same_type(other); -} - unsigned mul::return_type(void) const { if (seq.empty()) { @@ -590,7 +585,7 @@ expair mul::combine_ex_with_coeff_to_pair(const ex & e, // expression like (4^(1/3))^(3/2) if (are_ex_trivially_equal(c,_ex1)) return split_ex_to_pair(e); - + return split_ex_to_pair(power(e,c)); } @@ -603,7 +598,7 @@ expair mul::combine_pair_with_coeff_to_pair(const expair & p, // expression like (4^(1/3))^(3/2) if (are_ex_trivially_equal(c,_ex1)) return p; - + return split_ex_to_pair(power(recombine_pair_to_ex(p),c)); } @@ -612,25 +607,25 @@ ex mul::recombine_pair_to_ex(const expair & p) const if (ex_to(p.coeff).is_equal(_num1)) return p.rest; else - return power(p.rest,p.coeff); + return (new power(p.rest,p.coeff))->setflag(status_flags::dynallocated); } bool mul::expair_needs_further_processing(epp it) { - if (is_exactly_a((*it).rest) && - ex_to((*it).coeff).is_integer()) { + if (is_exactly_a(it->rest) && + ex_to(it->coeff).is_integer()) { // combined pair is product with integer power -> expand it *it = split_ex_to_pair(recombine_pair_to_ex(*it)); return true; } - if (is_exactly_a((*it).rest)) { - expair ep=split_ex_to_pair(recombine_pair_to_ex(*it)); + if (is_exactly_a(it->rest)) { + expair ep = split_ex_to_pair(recombine_pair_to_ex(*it)); if (!ep.is_equal(*it)) { // combined pair is a numeric power which can be simplified *it = ep; return true; } - if (ex_to((*it).coeff).is_equal(_num1)) { + if (it->coeff.is_equal(_ex1)) { // combined pair has coeff 1 and must be moved to the end return true; } diff --git a/ginac/mul.h b/ginac/mul.h index 65a291b7..f2862dcb 100644 --- a/ginac/mul.h +++ b/ginac/mul.h @@ -65,7 +65,6 @@ public: ex simplify_ncmul(const exvector & v) const; protected: ex derivative(const symbol & s) const; - bool is_equal_same_type(const basic & other) const; unsigned return_type(void) const; unsigned return_type_tinfo(void) const; ex thisexpairseq(const epvector & v, const ex & oc) const; diff --git a/ginac/numeric.cpp b/ginac/numeric.cpp index 1d9c78ba..7bdca344 100644 --- a/ginac/numeric.cpp +++ b/ginac/numeric.cpp @@ -584,7 +584,7 @@ unsigned numeric::calchash(void) const // equivalence relation on numbers). As a consequence, 3 and 3.0 share // the same hashvalue. That shouldn't really matter, though. setflag(status_flags::hash_calculated); - hashvalue = golden_ratio_hash(cln::equal_hashcode(cln::the(value))) | 0x80000000U; + hashvalue = golden_ratio_hash(cln::equal_hashcode(cln::the(value))); return hashvalue; } diff --git a/ginac/numeric.h b/ginac/numeric.h index 3c7dba2c..2d6d2959 100644 --- a/ginac/numeric.h +++ b/ginac/numeric.h @@ -170,9 +170,6 @@ protected: extern const numeric I; extern _numeric_digits Digits; -// deprecated macro, for internal use only -#define is_a_numeric_hash(x) ((x)&0x80000000U) - // global functions const numeric exp(const numeric &x); diff --git a/ginac/relational.cpp b/ginac/relational.cpp index 4f4dc9ff..9ff452be 100644 --- a/ginac/relational.cpp +++ b/ginac/relational.cpp @@ -249,7 +249,7 @@ unsigned relational::calchash(void) const unsigned lhash = lh.gethash(); unsigned rhash = rh.gethash(); - v = rotate_left_31(v); + v = rotate_left(v); switch(o) { case equal: case not_equal: @@ -270,12 +270,9 @@ unsigned relational::calchash(void) const lhash = rhash; break; } - v = rotate_left_31(v); + v = rotate_left(v); v ^= lhash; - // mask out numeric hashes: - v &= 0x7FFFFFFFU; - // store calculated hash value only if object is already evaluated if (flags & status_flags::evaluated) { setflag(status_flags::hash_calculated); diff --git a/ginac/symbol.cpp b/ginac/symbol.cpp index dae17b34..e393e95d 100644 --- a/ginac/symbol.cpp +++ b/ginac/symbol.cpp @@ -223,10 +223,7 @@ bool symbol::is_equal_same_type(const basic & other) const unsigned symbol::calchash(void) const { - // this is where the schoolbook method - // (golden_ratio_hash(tinfo()) ^ serial) - // is not good enough yet... - hashvalue = golden_ratio_hash(golden_ratio_hash(tinfo()) ^ serial); + hashvalue = golden_ratio_hash(tinfo() ^ serial); setflag(status_flags::hash_calculated); return hashvalue; } diff --git a/ginac/utils.h b/ginac/utils.h index a161ee2b..392efd40 100644 --- a/ginac/utils.h +++ b/ginac/utils.h @@ -65,46 +65,37 @@ inline int compare_pointers(const void * a, const void * b) return 0; } -/** Rotate lower 31 bits of unsigned value by one bit to the left - * (upper bit gets cleared). */ -inline unsigned rotate_left_31(unsigned n) +/** Rotate bits of unsigned value by one bit to the left. */ +inline unsigned rotate_left(unsigned n) { - // clear highest bit and shift 1 bit to the left - n = (n & 0x7FFFFFFFU) << 1; - - // overflow? clear highest bit and set lowest bit if (n & 0x80000000U) - n = (n & 0x7FFFFFFFU) | 0x00000001U; - - GINAC_ASSERT(n<0x80000000U); - + n = n << 1 | 0x00000001U; + else + n = n << 1; return n; } -/** Golden ratio hash function for the 31 least significant bits. */ +/** Truncated multiplication with golden ratio, for computing hash values. */ inline unsigned golden_ratio_hash(unsigned n) { // This function requires arithmetic with at least 64 significant bits #if SIZEOF_LONG >= 8 // So 'long' has 64 bits. Excellent! We prefer it because it might be // more efficient than 'long long'. - unsigned long l = n * 0x4f1bbcddL; - return (l & 0x7fffffffU) ^ (l >> 32); + unsigned long l = n * 0x4f1bbcddUL; + return (unsigned)l; #elif SIZEOF_LONG_LONG >= 8 // This requires 'long long' (or an equivalent 64 bit type)---which is, // unfortunately, not ANSI-C++-compliant. // (Yet C99 demands it, which is reason for hope.) - unsigned long long l = n * 0x4f1bbcddL; - return (l & 0x7fffffffU) ^ (l >> 32); -#elif SIZEOF_LONG_DOUBLE > 8 - // If 'long double' is bigger than 64 bits, we assume that the mantissa - // has at least 64 bits. This is not guaranteed but it's a good guess. - // Unfortunately, it may lead to horribly slow code. - const static long double golden_ratio = .618033988749894848204586834370; - long double m = golden_ratio * n; - return unsigned((m - int(m)) * 0x80000000); + unsigned long long l = n * 0x4f1bbcddULL; + return (unsigned)l; #else -#error "No 64 bit data type. You lose." + // Do the multiplication manually by splitting n up into the lower and + // upper two bytes. + const unsigned n0 = (n & 0x0000ffffU); + const unsigned n1 = (n & 0xffff0000U) >> 16; + return (n0 * 0x0000bcddU) + ((n1 * 0x0000bcddU + n0 * 0x00004f1bU) << 16); #endif } -- 2.47.0