X-Git-Url: https://git.ucc.asn.au/?a=blobdiff_plain;f=src%2Fparanoidnumber.h;h=b15292275c81a23e9f3caa8bc5d39f1e5023d675;hb=03cc1b0a0d0705e0b1d92e13fdb18608c7a00272;hp=a2e8542bc207940591f7325e21dbe6e5ceb63cbf;hpb=dfba002efc3b5f126ddb69e63b9a7dafdd9eacda;p=ipdf%2Fcode.git diff --git a/src/paranoidnumber.h b/src/paranoidnumber.h index a2e8542..b152922 100644 --- a/src/paranoidnumber.h +++ b/src/paranoidnumber.h @@ -6,70 +6,167 @@ #include #include #include "log.h" +#include +#include +#include +#include // it's going to be ok +#include +#define PARANOID_DIGIT_T double // we could theoretically replace this with a template + // but let's not do that... + + +#define PARANOID_CACHE_RESULTS + +//#define PARANOID_USE_ARENA +#define PARANOID_SIZE_LIMIT 0 namespace IPDF { + typedef enum {ADD, SUBTRACT, MULTIPLY, DIVIDE, NOP} Optype; + inline Optype InverseOp(Optype op) + { + return ((op == ADD) ? SUBTRACT : + (op == SUBTRACT) ? ADD : + (op == MULTIPLY) ? DIVIDE : + (op == DIVIDE) ? MULTIPLY : + (op == NOP) ? NOP : NOP); + } + + + inline char OpChar(int op) + { + static char opch[] = {'+','-','*','/'}; + return (op < NOP && op >= 0) ? opch[op] : '?'; + } + + + /** Performs an operation, returning if the result was exact **/ + // NOTE: DIFFERENT to ParanoidOp (although that wraps to this...) + template bool TrustingOp(T & a, const T & b, Optype op); + + /** Performs an operation _only_ if the result would be exact **/ + template bool ParanoidOp(T & a, const T & b, Optype op) + { + T cpy(a); + if (TrustingOp(cpy, b, op)) + { + a = cpy; + return true; + } + return false; + } + template <> bool TrustingOp(float & a, const float & b, Optype op); + template <> bool TrustingOp(double & a, const double & b, Optype op); + template <> bool TrustingOp(int8_t & a, const int8_t & b, Optype op); + + /** + * A ParanoidNumber + * Idea: Perform regular floating point arithmetic but rearrange operations to only ever use exact results + * Memory Usage: O(all of it) + * CPU Usage: O(all of it) + * Accuracy: O(gives better result for 0.3+0.3+0.3, gives same result for everything else, or worse result) + * + * The ParanoidNumber basically stores 4 linked lists which can be split into two "dimensions" + * 1. Terms to ADD and terms to SUBTRACT + * 2. Factors to MULTIPLY and DIVIDE + * Because ADD and SUBTRACT are inverse operations and MULTIPLY and DIVIDE are inverse operations + * See paranoidnumber.cpp and the ParanoidNumber::Operation function + */ class ParanoidNumber { + public: - typedef enum {ADD, SUBTRACT, MULTIPLY, DIVIDE} Optype; - - ParanoidNumber(float value=0, Optype type = ADD) : m_value(value), m_op(type), m_next_term(NULL), m_next_factor(NULL) + typedef PARANOID_DIGIT_T digit_t; + + ParanoidNumber(PARANOID_DIGIT_T value=0) : m_value(value), m_next() { - + #ifdef PARANOID_SIZE_LIMIT + m_size = 0; + #endif + #ifdef PARANOID_CACHE_RESULTS + m_cached_result = value; + #endif } - ParanoidNumber(const ParanoidNumber & cpy) : m_value(cpy.m_value), m_op(cpy.m_op), m_next_term(NULL), m_next_factor(NULL) + ParanoidNumber(const ParanoidNumber & cpy) : m_value(cpy.m_value), m_next() { - if (cpy.m_next_term != NULL) - { - m_next_term = new ParanoidNumber(*(cpy.m_next_term)); - } - if (cpy.m_next_factor != NULL) + + #ifdef PARANOID_SIZE_LIMIT + m_size = cpy.m_size; + #endif + #ifdef PARANOID_CACHE_RESULTS + m_cached_result = cpy.m_cached_result; + #endif + for (int i = 0; i < NOP; ++i) { - m_next_factor = new ParanoidNumber(*(cpy.m_next_factor)); + for (auto next : cpy.m_next[i]) + { + if (next != NULL) // why would this ever be null + m_next[i].push_back(new ParanoidNumber(*next)); // famous last words... + } } + //assert(SanityCheck()); } - ParanoidNumber(const ParanoidNumber & cpy, Optype type) : m_value(cpy.m_value), m_op(type), m_next_term(NULL), m_next_factor(NULL) - { - if (cpy.m_next_term != NULL) - { - m_next_term = new ParanoidNumber(*(cpy.m_next_term)); - } - if (cpy.m_next_factor != NULL) - { - m_next_factor = new ParanoidNumber(*(cpy.m_next_factor)); - } - } + //ParanoidNumber(const char * str); + ParanoidNumber(const std::string & str);// : ParanoidNumber(str.c_str()) {} - ParanoidNumber(const char * str); - ParanoidNumber(const std::string & str) : ParanoidNumber(str.c_str()) {} + virtual ~ParanoidNumber(); + - virtual ~ParanoidNumber() + bool SanityCheck(std::set & visited) const; + bool SanityCheck() const { - if (m_next_term != NULL) - delete m_next_term; - if (m_next_factor != NULL) - delete m_next_factor; + std::set s; + return SanityCheck(s); } template T Convert() const; - double ToDouble() const {return Convert();} - float ToFloat() const {return Convert();} + digit_t GetFactors() const; + digit_t GetTerms() const; + + // This function is declared const purely to trick the compiler. + // It is not actually const, and therefore, none of the other functions that call it are const either. + digit_t Digit() const; - bool Floating() const {return (m_next_term == NULL && m_next_factor == NULL);} + // Like this one. It isn't const. + double ToDouble() const {return (double)Digit();} + + // This one is probably const. + bool Floating() const + { + return NoFactors() && NoTerms(); + } bool Sunken() const {return !Floating();} // I could not resist... + bool NoFactors() const {return (m_next[MULTIPLY].size() == 0 && m_next[DIVIDE].size() == 0);} + bool NoTerms() const {return (m_next[ADD].size() == 0 && m_next[SUBTRACT].size() == 0);} + + ParanoidNumber & operator+=(const ParanoidNumber & a); ParanoidNumber & operator-=(const ParanoidNumber & a); ParanoidNumber & operator*=(const ParanoidNumber & a); ParanoidNumber & operator/=(const ParanoidNumber & a); ParanoidNumber & operator=(const ParanoidNumber & a); + ParanoidNumber & operator+=(const digit_t & a); + ParanoidNumber & operator-=(const digit_t & a); + ParanoidNumber & operator*=(const digit_t & a); + ParanoidNumber & operator/=(const digit_t & a); + ParanoidNumber & operator=(const digit_t & a); + + + ParanoidNumber * OperationTerm(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point = NULL, Optype * mop = NULL); + ParanoidNumber * OperationFactor(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point = NULL, Optype * mop = NULL); + ParanoidNumber * TrivialOp(ParanoidNumber * b, Optype op); + ParanoidNumber * Operation(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point = NULL, Optype * mop = NULL); + bool Simplify(Optype op); + bool FullSimplify(); + + // None of these are actually const bool operator<(const ParanoidNumber & a) const {return ToDouble() < a.ToDouble();} bool operator<=(const ParanoidNumber & a) const {return this->operator<(a) || this->operator==(a);} bool operator>(const ParanoidNumber & a) const {return !(this->operator<=(a));} @@ -77,6 +174,13 @@ namespace IPDF bool operator==(const ParanoidNumber & a) const {return ToDouble() == a.ToDouble();} bool operator!=(const ParanoidNumber & a) const {return !(this->operator==(a));} + ParanoidNumber operator-() const + { + ParanoidNumber neg(0); + neg -= *this; + return neg; + } + ParanoidNumber operator+(const ParanoidNumber & a) const { ParanoidNumber result(*this); @@ -103,68 +207,90 @@ namespace IPDF } std::string Str() const; - static char OpChar(Optype op) - { - static char opch[] = {'+','-','*','/'}; - return opch[(int)op]; - } + + + + + std::string PStr() const; + + #ifdef PARANOID_USE_ARENA + void * operator new(size_t byes); + void operator delete(void * p); + #endif //PARANOID_USE_ARENA private: + void Simplify(); void SimplifyTerms(); void SimplifyFactors(); + digit_t m_value; + #ifdef PARANOID_CACHE_RESULTS + digit_t m_cached_result; + #endif + std::vector m_next[4]; + #ifdef PARANOID_SIZE_LIMIT + int64_t m_size; + #endif //PARANOID_SIZE_LIMIT - float m_value; - Optype m_op; - ParanoidNumber * m_next_term; - ParanoidNumber * m_next_factor; - - - - + #ifdef PARANOID_USE_ARENA + class Arena + { + public: + Arena(int64_t block_size = 10000000); + ~Arena(); + + void * allocate(size_t bytes); + void deallocate(void * p); + + private: + struct Block + { + void * memory; + int64_t used; + }; + + std::vector m_blocks; + int64_t m_block_size; + + void * m_spare; + + }; + static Arena g_arena; + #endif //PARANOID_USE_ARENA + }; + + template T ParanoidNumber::Convert() const { - T value = (m_op == SUBTRACT) ? -m_value : m_value; - const ParanoidNumber * n = m_next_factor; - if (n != NULL) + #ifdef PARANOID_CACHE_RESULTS + if (!isnan((float(m_cached_result)))) + return (T)m_cached_result; + #endif + T value(m_value); + for (auto mul : m_next[MULTIPLY]) { - switch (n->m_op) - { - case MULTIPLY: - value *= n->Convert(); - break; - case DIVIDE: - value /= n->Convert(); - break; - default: - Fatal("Shouldn't happen"); - break; - } + value *= mul->Convert(); } - n = m_next_term; - if (n != NULL) + for (auto div : m_next[DIVIDE]) { - switch (n->m_op) - { - case ADD: - case SUBTRACT: - value += n->Convert(); - break; - default: - Fatal("Shouldn't happen"); - } + value /= div->Convert(); } + for (auto add : m_next[ADD]) + value += add->Convert(); + for (auto sub : m_next[SUBTRACT]) + value -= sub->Convert(); return value; } + } #endif //_PARANOIDNUMBER_H