X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fcode.git;a=blobdiff_plain;f=src%2Fparanoidnumber.h;h=77a8d441caa24f7cabbc7225df390ece5b512a53;hp=4c481bd7f6207d582d2f2a1e3fd2fa72ee172bcc;hb=bb659698bba26042232c038065b7edaa72541f61;hpb=6472d20ee58d2ecc0aee8bc1a12a071b2afc8a27 diff --git a/src/paranoidnumber.h b/src/paranoidnumber.h index 4c481bd..77a8d44 100644 --- a/src/paranoidnumber.h +++ b/src/paranoidnumber.h @@ -5,42 +5,134 @@ #include #include #include +#include "log.h" +#include + +#define PARANOID_DIGIT_T float // we could theoretically replace this with a template + // but let's not do that... 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 Optype AdjacentOp(Optype op) + { + return ((op == ADD) ? MULTIPLY : + (op == SUBTRACT) ? DIVIDE : + (op == MULTIPLY) ? ADD : + (op == DIVIDE) ? SUBTRACT : + (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(NULL) + typedef PARANOID_DIGIT_T digit_t; + + ParanoidNumber(digit_t value=0) : m_value(value) { - + Construct(); } - ParanoidNumber(const ParanoidNumber & cpy) : m_value(cpy.m_value), m_op(cpy.m_op), m_next(NULL) + ParanoidNumber(const ParanoidNumber & cpy) : m_value(cpy.m_value) { - if (cpy.m_next != NULL) + Construct(); + for (int i = 0; i < NOP; ++i) { - m_next = new ParanoidNumber(*(cpy.m_next)); + if (cpy.m_next[i] != NULL) + m_next[i] = new ParanoidNumber(*(cpy.m_next[i])); } } - ParanoidNumber(const ParanoidNumber & cpy, Optype type) : ParanoidNumber(cpy) + ParanoidNumber(const char * str); + ParanoidNumber(const std::string & str) : ParanoidNumber(str.c_str()) {Construct();} + + virtual ~ParanoidNumber(); + + inline void Construct() { - m_op = type; + for (int i = 0; i < NOP; ++i) + m_next[i] = NULL; + g_count++; } - ParanoidNumber(const char * str); - virtual ~ParanoidNumber() + template T Convert() const; + template T AddTerms(T value = T(0)) const; + template T MultiplyFactors(T value = T(1)) const; + template T Head() const {return (m_op == SUBTRACT) ? T(-m_value) : T(m_value);} + + + + + double ToDouble() const {return Convert();} + float ToFloat() const {return Convert();} + digit_t Digit() const {return Convert();} + + bool Floating() const { - if (m_next != NULL) - delete m_next; + for (int i = 0; i < NOP; ++i) + { + if (m_next[i] != NULL) + return false; + } + return true; } + bool Sunken() const {return !Floating();} // I could not resist... - - double ToDouble() const; + bool Pure(Optype op) const + { + if (op == ADD || op == SUBTRACT) + return (m_next[MULTIPLY] == NULL && m_next[DIVIDE] == NULL); + return (m_next[ADD] == NULL && m_next[SUBTRACT] == NULL); + } ParanoidNumber & operator+=(const ParanoidNumber & a); ParanoidNumber & operator-=(const ParanoidNumber & a); @@ -49,6 +141,10 @@ namespace IPDF ParanoidNumber & operator=(const ParanoidNumber & a); + ParanoidNumber * Operation(ParanoidNumber * b, Optype op, ParanoidNumber ** parent = NULL); + bool Simplify(Optype op); + + 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));} @@ -82,20 +178,82 @@ namespace IPDF } std::string Str() const; + + + static int64_t Paranoia() {return g_count;} + + std::string PStr() const; private: + static int64_t g_count; void Simplify(); - ParanoidNumber * InsertAfter(ParanoidNumber * insert); - ParanoidNumber * InsertAfter(float value, Optype op); + void SimplifyTerms(); + void SimplifyFactors(); - float m_value; + + digit_t m_value; Optype m_op; - ParanoidNumber * m_next; + ParanoidNumber * m_next[4]; // Next by Operation + }; - - +template +T ParanoidNumber::AddTerms(T value) const +{ + ParanoidNumber * add = m_next[ADD]; + ParanoidNumber * sub = m_next[SUBTRACT]; + while (add != NULL && sub != NULL) + { + value += add->m_value * add->MultiplyFactors(); + value -= sub->m_value * sub->MultiplyFactors(); + add = add->m_next[ADD]; + sub = sub->m_next[SUBTRACT]; + } + while (add != NULL) + { + value += add->m_value * add->MultiplyFactors(); + add = add->m_next[ADD]; + } + while (sub != NULL) + { + value -= sub->m_value * sub->MultiplyFactors(); + sub = sub->m_next[SUBTRACT];; + } + return value; +} + +template +T ParanoidNumber::MultiplyFactors(T value) const +{ + ParanoidNumber * mul = m_next[MULTIPLY]; + ParanoidNumber * div = m_next[DIVIDE]; + while (mul != NULL && div != NULL) + { + value *= (mul->m_value + mul->AddTerms()); + value /= (div->m_value + div->AddTerms()); + mul = mul->m_next[MULTIPLY]; + div = div->m_next[DIVIDE]; + } + while (mul != NULL) + { + value *= (mul->m_value + mul->AddTerms()); + mul = mul->m_next[MULTIPLY]; + } + while (div != NULL) + { + value /= (div->m_value + div->AddTerms()); + div = div->m_next[DIVIDE]; + } + return value; +} + + + +template +T ParanoidNumber::Convert() const +{ + return MultiplyFactors(m_value) + AddTerms(0); +} - }; }