X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fcode.git;a=blobdiff_plain;f=src%2Fparanoidnumber.cpp;h=60802eb432a7acc0f17c530a42bf7b0461c17f0b;hp=173026c252f1a82e2f9eabb5247a381379a66079;hb=64b7c42c71c35d520424cf4ca5ecaa99faef8b26;hpb=ea748154f1bc7dbc81cb52611a52865e63109439 diff --git a/src/paranoidnumber.cpp b/src/paranoidnumber.cpp index 173026c..60802eb 100644 --- a/src/paranoidnumber.cpp +++ b/src/paranoidnumber.cpp @@ -6,15 +6,19 @@ #include #include +// here be many copy paste bugs + using namespace std; namespace IPDF { -int64_t ParanoidNumber::g_count = 0; +#ifdef PARANOID_USE_ARENA +ParanoidNumber::Arena ParanoidNumber::g_arena; +#endif //PARANOID_USE_ARENA + ParanoidNumber::~ParanoidNumber() { - g_count--; for (int i = 0; i < NOP; ++i) { for (auto n : m_next[i]) @@ -22,11 +26,23 @@ ParanoidNumber::~ParanoidNumber() } } -ParanoidNumber::ParanoidNumber(const string & str) : m_value(0), m_cached_result(0), m_cache_valid(false), m_next() +ParanoidNumber::ParanoidNumber(const string & str) : m_value(0), m_next() { - Construct(); + #ifdef PARANOID_SIZE_LIMIT + m_size = 1; + #endif + #ifdef PARANOID_CACHE_RESULTS + m_cache_valid = false; + #endif + int dp = 0; int end = 0; + bool negate = str[0] == '-'; + if (negate) + { + dp++; + end++; + } while (str[dp] != '\0' && str[dp] != '.') { ++dp; @@ -35,7 +51,7 @@ ParanoidNumber::ParanoidNumber(const string & str) : m_value(0), m_cached_result while (str[end] != '\0') ++end; ParanoidNumber m(1); - for (int i = dp-1; i >= 0; --i) + for (int i = dp-1; i >= negate; --i) { ParanoidNumber b(str[i]-'0'); b*=m; @@ -50,13 +66,29 @@ ParanoidNumber::ParanoidNumber(const string & str) : m_value(0), m_cached_result b*=n; this->operator+=(b); } + + if (negate) + Negate(); + + #ifdef PARANOID_COMPARE_EPSILON + double d = strtod(str.c_str(), NULL); + CompareForSanity(d, d); + #endif } ParanoidNumber & ParanoidNumber::operator=(const ParanoidNumber & a) { - assert(this != NULL); + //assert(this != NULL); + + #ifdef PARANOID_SIZE_LIMIT + m_size = a.m_size; + #endif + m_value = a.m_value; + #ifdef PARANOID_CACHE_RESULTS m_cached_result = a.m_cached_result; + m_cache_valid = a.m_cache_valid; + #endif for (int i = 0; i < NOP; ++i) { for (auto n : m_next[i]) @@ -65,20 +97,9 @@ ParanoidNumber & ParanoidNumber::operator=(const ParanoidNumber & a) for (auto n : a.m_next[i]) m_next[i].push_back(new ParanoidNumber(*n)); } - /* - for (unsigned j = 0; j < m_next[i].size() && j < a.m_next[i].size(); ++j) - { - if (a.m_next[i][j] != NULL) - m_next[i][j]->operator=(*(a.m_next[i][j])); - } - - for (unsigned j = a.m_next[i].size(); j < m_next[i].size(); ++j) - { - delete m_next[i][j]; - } - m_next[i].resize(a.m_next[i].size()); - */ - //} + #ifdef PARANOID_COMPARE_EPSILON + CompareForSanity(a.Digit(),a.Digit()); + #endif return *this; } @@ -86,7 +107,7 @@ ParanoidNumber & ParanoidNumber::operator=(const ParanoidNumber & a) string ParanoidNumber::Str() const { - assert(this != NULL); + //assert(this != NULL); string result(""); stringstream s; s << (double)m_value; @@ -132,6 +153,7 @@ string ParanoidNumber::Str() const template <> bool TrustingOp(float & a, const float & b, Optype op) { + feclearexcept(FE_ALL_EXCEPT); switch (op) @@ -189,6 +211,41 @@ bool TrustingOp(double & a, const double & b, Optype op) return !fetestexcept(FE_ALL_EXCEPT); } + + +template <> +bool TrustingOp(long double & a, const long double & b, Optype op) +{ + + + feclearexcept(FE_ALL_EXCEPT); + switch (op) + { + case ADD: + a += b; + break; + case SUBTRACT: + a -= b; + break; + case MULTIPLY: + a *= b; + break; + case DIVIDE: + if (b == 0) + { + a = (a >= 0) ? INFINITY : -INFINITY; + return false; + } + + a /= b; + break; + case NOP: + break; + } + return !fetestexcept(FE_ALL_EXCEPT); +} + + template <> bool TrustingOp(int8_t & a, const int8_t & b, Optype op) { @@ -220,52 +277,179 @@ bool TrustingOp(int8_t & a, const int8_t & b, Optype op) } -ParanoidNumber & ParanoidNumber::operator+=(const ParanoidNumber & a) +ParanoidNumber & ParanoidNumber::operator+=(const digit_t & a) { - - assert(this != NULL); - delete Operation(SafeConstruct(a), ADD); + #ifdef PARANOID_COMPARE_EPSILON + digit_t compare = Digit(); + compare += a; + #endif + delete Operation(new ParanoidNumber(a), ADD); + Simplify(SUBTRACT); + Simplify(ADD); + #ifdef PARANOID_COMPARE_EPSILON + CompareForSanity(compare, a); + #endif + return *this; +} + + +ParanoidNumber & ParanoidNumber::operator-=(const digit_t & a) +{ + #ifdef PARANOID_COMPARE_EPSILON + digit_t compare = Digit(); + compare -= a; + #endif + delete Operation(new ParanoidNumber(a), SUBTRACT); Simplify(ADD); Simplify(SUBTRACT); + #ifdef PARANOID_COMPARE_EPSILON + CompareForSanity(compare, a); + #endif return *this; } +ParanoidNumber & ParanoidNumber::operator*=(const digit_t & a) +{ + #ifdef PARANOID_COMPARE_EPSILON + digit_t compare = Digit(); + compare *= a; + #endif + delete Operation(new ParanoidNumber(a), MULTIPLY); + Simplify(DIVIDE); + Simplify(MULTIPLY); + #ifdef PARANOID_COMPARE_EPSILON + CompareForSanity(compare, a); + #endif + return *this; +} -ParanoidNumber & ParanoidNumber::operator-=(const ParanoidNumber & a) + +ParanoidNumber & ParanoidNumber::operator/=(const digit_t & a) +{ + #ifdef PARANOID_COMPARE_EPSILON + digit_t compare = Digit(); + compare /= a; + #endif + delete Operation(new ParanoidNumber(a), DIVIDE); + Simplify(MULTIPLY); + Simplify(DIVIDE); + #ifdef PARANOID_COMPARE_EPSILON + CompareForSanity(compare, a); + #endif + return *this; +} + + +ParanoidNumber & ParanoidNumber::operator+=(const ParanoidNumber & a) { - delete Operation(SafeConstruct(a), SUBTRACT); + #ifdef PARANOID_COMPARE_EPSILON + digit_t compare = Digit(); + compare += a.Digit(); + #endif + delete Operation(new ParanoidNumber(a), ADD); Simplify(SUBTRACT); Simplify(ADD); + #ifdef PARANOID_COMPARE_EPSILON + CompareForSanity(compare, a.Digit()); + #endif + return *this; +} + + +ParanoidNumber & ParanoidNumber::operator-=(const ParanoidNumber & a) +{ + #ifdef PARANOID_COMPARE_EPSILON + digit_t compare = Digit(); + compare -= a.Digit(); + #endif + delete Operation(new ParanoidNumber(a), SUBTRACT); + Simplify(ADD); + Simplify(SUBTRACT); + #ifdef PARANOID_COMPARE_EPSILON + CompareForSanity(compare, a.Digit()); + #endif return *this; } ParanoidNumber & ParanoidNumber::operator*=(const ParanoidNumber & a) { - delete Operation(SafeConstruct(a), MULTIPLY); + #ifdef PARANOID_COMPARE_EPSILON + digit_t compare = Digit(); + compare *= a.Digit(); + #endif + delete Operation(new ParanoidNumber(a), MULTIPLY); + Simplify(DIVIDE); Simplify(MULTIPLY); - Simplify(DIVIDE); + #ifdef PARANOID_COMPARE_EPSILON + CompareForSanity(compare, a.Digit()); + #endif return *this; } ParanoidNumber & ParanoidNumber::operator/=(const ParanoidNumber & a) { - delete Operation(SafeConstruct(a), DIVIDE); + #ifdef PARANOID_COMPARE_EPSILON + digit_t compare = Digit(); + compare /= a.Digit(); + #endif + delete Operation(new ParanoidNumber(a), DIVIDE); Simplify(MULTIPLY); Simplify(DIVIDE); + #ifdef PARANOID_COMPARE_EPSILON + CompareForSanity(compare, a.Digit()); + #endif return *this; } -// a + b -ParanoidNumber * ParanoidNumber::OperationTerm(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point, Optype * merge_op) +ParanoidNumber & ParanoidNumber::operator=(const digit_t & a) { - if (!SanityCheck()) + + for (int i = 0; i < NOP; ++i) { - Fatal("What..."); + for (auto n : m_next[i]) + delete n; + m_next[i].clear(); } - assert(b->SanityCheck()); + m_value = a; + #ifdef PARANOID_CACHE_RESULTS + m_cached_result = a; + m_cache_valid = true; + #endif + + #ifdef PARANOID_COMPARE_EPSILON + CompareForSanity(a,a); + #endif + + return *this; +} + +// a + b +ParanoidNumber * ParanoidNumber::OperationTerm(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point, Optype * merge_op) +{ + ////assert(b->SanityCheck()); + #ifdef PARANOID_CACHE_RESULTS + m_cache_valid = false; + #endif + #ifdef PARANOID_SIZE_LIMIT + if (m_size + b->m_size >= PARANOID_SIZE_LIMIT) + { + this->operator=(this->Digit()); + if (op == ADD) + m_value += b->Digit(); + else + m_value -= b->Digit(); + m_size = 1; + #ifdef PARANOID_CACHE_RESULTS + m_cached_result = m_value; + m_cache_valid = true; + #endif + return b; + } + //Debug("At size limit %d", m_size); + #endif - m_cached_result = nan(""); + if (Floating() && m_value == 0) // 0 + b = b { m_value = b->m_value; @@ -281,7 +465,7 @@ ParanoidNumber * ParanoidNumber::OperationTerm(ParanoidNumber * b, Optype op, Pa b->m_next[i].clear(); } - assert(SanityCheck()); + //assert(SanityCheck()); return b; } if (b->Floating() && b->m_value == 0) // a + 0 = a @@ -297,15 +481,15 @@ ParanoidNumber * ParanoidNumber::OperationTerm(ParanoidNumber * b, Optype op, Pa Optype addop = (op == ADD) ? ADD : SUBTRACT; for (auto add : b->m_next[ADD]) { - delete OperationTerm(add, addop); + delete (OperationTerm(add, addop)); } Optype subop = (op == ADD) ? SUBTRACT : ADD; for (auto sub : b->m_next[SUBTRACT]) - delete OperationTerm(sub, subop); + delete (OperationTerm(sub, subop)); b->m_next[ADD].clear(); b->m_next[SUBTRACT].clear(); - assert(SanityCheck()); + //assert(SanityCheck()); return b; } } @@ -315,7 +499,7 @@ ParanoidNumber * ParanoidNumber::OperationTerm(ParanoidNumber * b, Optype op, Pa bool parent = (merge_point == NULL); ParanoidNumber * merge = this; Optype mop = op; - assert(mop != NOP); // silence compiler warning + //assert(mop != NOP); // silence compiler warning if (parent) { merge_point = &merge; @@ -340,7 +524,7 @@ ParanoidNumber * ParanoidNumber::OperationTerm(ParanoidNumber * b, Optype op, Pa { if (prev->OperationTerm(b, rev, merge_point, merge_op) == b) { - assert(SanityCheck()); + //assert(SanityCheck()); return b; } @@ -349,7 +533,7 @@ ParanoidNumber * ParanoidNumber::OperationTerm(ParanoidNumber * b, Optype op, Pa { if (next->OperationTerm(b, fwd, merge_point, merge_op) == b) { - assert(SanityCheck()); + //assert(SanityCheck()); return b; } } @@ -361,6 +545,9 @@ ParanoidNumber * ParanoidNumber::OperationTerm(ParanoidNumber * b, Optype op, Pa { //merge->m_next[*merge_op].push_back(b); m_next[op].push_back(b); + #ifdef PARANOID_SIZE_LIMIT + m_size += b->m_size; + #endif } else { @@ -371,15 +558,35 @@ ParanoidNumber * ParanoidNumber::OperationTerm(ParanoidNumber * b, Optype op, Pa } } - assert(SanityCheck()); + //assert(SanityCheck()); + return NULL; } ParanoidNumber * ParanoidNumber::OperationFactor(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point, Optype * merge_op) { - assert(SanityCheck()); - assert(b->SanityCheck()); - m_cached_result = nan(""); + #ifdef PARANOID_CACHE_RESULTS + m_cache_valid = false; + #endif + #ifdef PARANOID_SIZE_LIMIT + if (m_size + b->m_size >= PARANOID_SIZE_LIMIT) + { + this->operator=(this->Digit()); + if (op == MULTIPLY) + m_value *= b->Digit(); + else + m_value /= b->Digit(); + m_size = 1; + #ifdef PARANOID_CACHE_RESULTS + m_cached_result = m_value; + m_cache_valid = true; + #endif + //Debug("Cut off %p", this); + return b; + + } + #endif + if (Floating() && m_value == 0) { return b; @@ -391,16 +598,20 @@ ParanoidNumber * ParanoidNumber::OperationFactor(ParanoidNumber * b, Optype op, for (int i = 0; i < NOP; ++i) { for (auto n : m_next[i]) - delete n; + delete (n); m_next[i].clear(); swap(m_next[i], b->m_next[i]); } - assert(SanityCheck()); + //assert(SanityCheck()); return b; } if (b->Floating() && b->m_value == 1) return b; - + if (b->Floating() && b->m_value == 0 && op == MULTIPLY) + { + operator=(*b); + return b; + } if (NoTerms() && b->NoTerms()) @@ -410,17 +621,14 @@ ParanoidNumber * ParanoidNumber::OperationFactor(ParanoidNumber * b, Optype op, Optype mulop = (op == MULTIPLY) ? MULTIPLY : DIVIDE; for (auto mul : b->m_next[MULTIPLY]) { - delete OperationFactor(mul, mulop); + delete(OperationFactor(mul, mulop)); } Optype divop = (op == MULTIPLY) ? DIVIDE : MULTIPLY; for (auto div : b->m_next[DIVIDE]) - delete OperationFactor(div, divop); + delete(OperationFactor(div, divop)); b->m_next[DIVIDE].clear(); b->m_next[MULTIPLY].clear(); - - - assert(SanityCheck()); return b; } } @@ -449,24 +657,17 @@ ParanoidNumber * ParanoidNumber::OperationFactor(ParanoidNumber * b, Optype op, rev = DIVIDE; } - ParanoidNumber * cpy_b = NULL; - - if (m_next[ADD].size() > 0 || m_next[SUBTRACT].size() > 0) - { - cpy_b = SafeConstruct(*b); - } - + ParanoidNumber * cpy_b = new ParanoidNumber(*b); for (auto prev : m_next[invop]) { if (prev->OperationFactor(b, rev, merge_point, merge_op) == b) { for (auto add : m_next[ADD]) - delete add->OperationFactor(SafeConstruct(*cpy_b), op); + delete(add->OperationFactor(new ParanoidNumber(*cpy_b), op)); for (auto sub : m_next[SUBTRACT]) - delete sub->OperationFactor(SafeConstruct(*cpy_b), op); + delete(sub->OperationFactor(new ParanoidNumber(*cpy_b), op)); - delete cpy_b; - assert(SanityCheck()); + delete(cpy_b); return b; } } @@ -476,28 +677,34 @@ ParanoidNumber * ParanoidNumber::OperationFactor(ParanoidNumber * b, Optype op, { for (auto add : m_next[ADD]) { - delete add->OperationFactor(SafeConstruct(*cpy_b), op); + delete(add->OperationFactor(new ParanoidNumber(*cpy_b), op)); } for (auto sub : m_next[SUBTRACT]) { - delete sub->OperationFactor(SafeConstruct(*cpy_b), op); + delete(sub->OperationFactor(new ParanoidNumber(*cpy_b), op)); } - delete cpy_b; - assert(SanityCheck()); + delete(cpy_b); return b; } } if (parent) { - assert(b != NULL); + //assert(b != NULL); m_next[op].push_back(b); for (auto add : m_next[ADD]) - delete add->OperationFactor(SafeConstruct(*cpy_b), op); + delete(add->OperationFactor(new ParanoidNumber(*cpy_b), op)); for (auto sub : m_next[SUBTRACT]) - delete sub->OperationFactor(SafeConstruct(*cpy_b), op); + delete(sub->OperationFactor(new ParanoidNumber(*cpy_b), op)); + + #ifdef PARANOID_SIZE_LIMIT + m_size += b->m_size; + #endif } - assert(SanityCheck()); + //assert(SanityCheck()); + + + return NULL; } @@ -542,22 +749,30 @@ string ParanoidNumber::PStr() const bool ParanoidNumber::Simplify(Optype op) { + if (Floating()) return false; - assert(SanityCheck()); + //assert(SanityCheck()); vector next; next.clear(); swap(m_next[op], next); m_next[op].clear(); - assert(m_next[op].size() == 0); - assert(SanityCheck()); + //assert(m_next[op].size() == 0); + //assert(SanityCheck()); Optype fwd = op; if (op == DIVIDE) fwd = MULTIPLY; else if (op == SUBTRACT) fwd = ADD; + + vector hold[2]; + if (op == MULTIPLY || op == DIVIDE) + { + swap(m_next[ADD], hold[0]); + swap(m_next[SUBTRACT], hold[1]); + } for (vector::iterator n = next.begin(); n != next.end(); ++n) { @@ -575,18 +790,44 @@ bool ParanoidNumber::Simplify(Optype op) ParanoidNumber * result = (*n)->Operation(*m, fwd, &parent, &mop); if (result != NULL) { + #ifdef PARANOID_SIZE_LIMIT + m_size -= result->m_size; + #endif *m = NULL; - delete result; + delete(result); } } - if (*n != NULL) - delete Operation(*n, op); } - set s; - if (!SanityCheck(s)) + + + + for (auto n : next) + { + if (n != NULL) + { + #ifdef PARANOID_SIZE_LIMIT + if (Operation(n, op) == n) + { + m_size -= n->m_size; + delete n; + } + #else + delete(Operation(n, op)); + #endif + } + } + + if (op == MULTIPLY || op == DIVIDE) { - Error("Simplify broke Sanity"); + swap(m_next[ADD], hold[0]); + swap(m_next[SUBTRACT], hold[1]); } + + set s; + //if (!SanityCheck(s)) + //{ + // Error("Simplify broke Sanity"); + //} return (next.size() > m_next[op].size()); } @@ -602,15 +843,17 @@ bool ParanoidNumber::FullSimplify() ParanoidNumber::digit_t ParanoidNumber::Digit() const { - if (!SanityCheck()) - { - Fatal("Blargh"); - } - //if (!isnan(m_cached_result)) - // return m_cached_result; - + // Get around the absurd requirement that const correctness be observed. - digit_t result;// = ((ParanoidNumber*)(this))->m_cached_result; + #ifdef PARANOID_CACHE_RESULTS + if (m_cache_valid) // le sigh ambiguous function compiler warnings + return m_cached_result; + + digit_t & result = ((ParanoidNumber*)(this))->m_cached_result; + + #else + digit_t result; + #endif result = m_value; for (auto mul : m_next[MULTIPLY]) { @@ -624,6 +867,10 @@ ParanoidNumber::digit_t ParanoidNumber::Digit() const result += add->Digit(); for (auto sub : m_next[SUBTRACT]) result -= sub->Digit(); + + #ifdef PARANOID_CACHE_RESULTS + ((ParanoidNumber*)(this))->m_cache_valid = true; + #endif return result; } @@ -685,8 +932,74 @@ bool ParanoidNumber::SanityCheck(set & visited) const { if (!div->SanityCheck(visited)) return false; + if (div->Digit() == 0) + { + Error("Divide by zero"); + return false; + } } return true; } +void ParanoidNumber::Negate() +{ + swap(m_next[ADD], m_next[SUBTRACT]); + m_value = -m_value; + #ifdef PARANOID_CACHE_RESULTS + m_cached_result = -m_cached_result; + #endif +} + +#ifdef PARANOID_USE_ARENA + +void * ParanoidNumber::operator new(size_t s) +{ + return g_arena.allocate(s); +} + +void ParanoidNumber::operator delete(void * p) +{ + g_arena.deallocate(p); +} + +ParanoidNumber::Arena::Arena(int64_t block_size) : m_block_size(block_size), m_spare(NULL) +{ + m_blocks.push_back({malloc(block_size*sizeof(ParanoidNumber)),0}); +} + +ParanoidNumber::Arena::~Arena() +{ + for (auto block : m_blocks) + { + free(block.memory); + } + m_blocks.clear(); +} + +void * ParanoidNumber::Arena::allocate(size_t s) +{ + if (m_spare != NULL) + { + void * result = m_spare; + m_spare = NULL; + return result; + } + + Block & b = m_blocks.back(); + void * result = (ParanoidNumber*)(b.memory) + (b.used++); + if (b.used >= m_block_size) + { + m_block_size *= 2; + Debug("Add block of size %d", m_block_size); + m_blocks.push_back({malloc(m_block_size*sizeof(ParanoidNumber)), 0}); + } + return result; +} + +void ParanoidNumber::Arena::deallocate(void * p) +{ + m_spare = p; +} +#endif //PARANOID_USE_ARENA + }