src/paranoidnumber.h

   1 #ifndef _PARANOIDNUMBER_H
   2 #define _PARANOIDNUMBER_H
   3
   4 #include <list>
   5 #include <cfloat>
   6 #include <map>
   7 #include <string>
   8 #include "log.h"
   9 #include <fenv.h>
  10 #include <vector>
  11 #include <cmath>
  12
  13 #define PARANOID_DIGIT_T float // we could theoretically replace this with a template
  14                                                                 // but let's not do that...
  15
  16 namespace IPDF
  17 {
  18         typedef enum {ADD, SUBTRACT, MULTIPLY, DIVIDE, NOP} Optype;
  19         inline Optype InverseOp(Optype op)
  20         {
  21                 return ((op == ADD) ? SUBTRACT :
  22                                 (op == SUBTRACT) ? ADD :
  23                                 (op == MULTIPLY) ? DIVIDE :
  24                                 (op == DIVIDE) ? MULTIPLY :
  25                                 (op == NOP) ? NOP : NOP);
  26         }
  27
  28
  29         inline char OpChar(int op)
  30         {
  31                 static char opch[] = {'+','-','*','/'};
  32                 return (op < NOP && op >= 0) ? opch[op] : '?';
  33         }
  34
  35
  36         /** Performs an operation, returning if the result was exact **/
  37         // NOTE: DIFFERENT to ParanoidOp (although that wraps to this...)
  38         template <class T> bool TrustingOp(T & a, const T & b, Optype op);
  39
  40         /** Performs an operation _only_ if the result would be exact **/
  41         template <class T> bool ParanoidOp(T & a, const T & b, Optype op)
  42         {
  43                 T cpy(a);
  44                 if (TrustingOp<T>(cpy, b, op))
  45                 {
  46                         a = cpy;
  47                         return true;
  48                 }
  49                 return false;
  50         }
  51         template <> bool TrustingOp<float>(float & a, const float & b, Optype op);
  52         template <> bool TrustingOp<double>(double & a, const double & b, Optype op);
  53         template <> bool TrustingOp<int8_t>(int8_t & a, const int8_t & b, Optype op);
  54
  55         /**
  56          * A ParanoidNumber
  57          * Idea: Perform regular floating point arithmetic but rearrange operations to only ever use exact results
  58          * Memory Usage: O(all of it)
  59          * CPU Usage: O(all of it)
  60          * Accuracy: O(gives better result for 0.3+0.3+0.3, gives same result for everything else, or worse result)
  61          *
  62          * The ParanoidNumber basically stores 4 linked lists which can be split into two "dimensions"
  63          *  1. Terms to ADD and terms to SUBTRACT
  64          *  2. Factors to MULTIPLY and DIVIDE
  65          * Because ADD and SUBTRACT are inverse operations and MULTIPLY and DIVIDE are inverse operations
  66          * See paranoidnumber.cpp and the ParanoidNumber::Operation function
  67          */
  68         class ParanoidNumber
  69         {
  70
  71                 public:
  72                         typedef PARANOID_DIGIT_T digit_t;
  73
  74                         ParanoidNumber(digit_t value=0) : m_value(value), m_cached_result(value)
  75                         {
  76                                 Construct();
  77                         }
  78
  79                         ParanoidNumber(const ParanoidNumber & cpy) : m_value(cpy.m_value), m_cached_result(cpy.m_cached_result)
  80                         {
  81                                 Construct();
  82                                 for (int i = 0; i < NOP; ++i)
  83                                 {
  84                                         for (auto next : cpy.m_next[i])
  85                                                 m_next[i].push_back(new ParanoidNumber(*next));
  86                                 }
  87                         }
  88
  89                         ParanoidNumber(const char * str);
  90                         ParanoidNumber(const std::string & str) : ParanoidNumber(str.c_str()) {}
  91
  92                         virtual ~ParanoidNumber();
  93
  94                         inline void Construct()
  95                         {
  96                                 g_count++;
  97                         }
  98
  99
 100                         template <class T> T Convert() const;
 101                         digit_t GetFactors();
 102                         digit_t GetTerms();
 103
 104
 105                         double ToDouble() {return (double)Digit();}
 106                         digit_t Digit();
 107
 108                         bool Floating() const
 109                         {
 110                                 return NoFactors() && NoTerms();
 111                         }
 112                         bool Sunken() const {return !Floating();} // I could not resist...
 113
 114                         bool NoFactors() const {return (m_next[MULTIPLY].size() == 0 && m_next[DIVIDE].size() == 0);}
 115                         bool NoTerms() const {return (m_next[ADD].size() == 0 && m_next[SUBTRACT].size() == 0);}
 116
 117                         ParanoidNumber & operator+=(const ParanoidNumber & a);
 118                         ParanoidNumber & operator-=(const ParanoidNumber & a);
 119                         ParanoidNumber & operator*=(const ParanoidNumber & a);
 120                         ParanoidNumber & operator/=(const ParanoidNumber & a);
 121                         ParanoidNumber & operator=(const ParanoidNumber & a);
 122
 123                         ParanoidNumber * OperationTerm(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point = NULL, Optype * mop = NULL);
 124                         ParanoidNumber * OperationFactor(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point = NULL, Optype * mop = NULL);
 125                         ParanoidNumber * TrivialOp(ParanoidNumber * b, Optype op);
 126                         ParanoidNumber * Operation(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point = NULL, Optype * mop = NULL);
 127                         bool Simplify(Optype op);
 128                         bool FullSimplify();
 129
 130                         bool operator<(ParanoidNumber & a) {return ToDouble() < a.ToDouble();}
 131                         bool operator<=(ParanoidNumber & a) {return this->operator<(a) || this->operator==(a);}
 132                         bool operator>(ParanoidNumber & a) {return !(this->operator<=(a));}
 133                         bool operator>=(ParanoidNumber & a) {return !(this->operator<(a));}
 134                         bool operator==(ParanoidNumber & a) {return ToDouble() == a.ToDouble();}
 135                         bool operator!=(ParanoidNumber & a) {return !(this->operator==(a));}
 136
 137                         ParanoidNumber operator+(const ParanoidNumber & a) const
 138                         {
 139                                 ParanoidNumber result(*this);
 140                                 result += a;
 141                                 return result;
 142                         }
 143                         ParanoidNumber operator-(const ParanoidNumber & a) const
 144                         {
 145                                 ParanoidNumber result(*this);
 146                                 result -= a;
 147                                 return result;
 148                         }
 149                         ParanoidNumber operator*(const ParanoidNumber & a) const
 150                         {
 151                                 ParanoidNumber result(*this);
 152                                 result *= a;
 153                                 return result;
 154                         }
 155                         ParanoidNumber operator/(const ParanoidNumber & a) const
 156                         {
 157                                 ParanoidNumber result(*this);
 158                                 result /= a;
 159                                 return result;
 160                         }
 161
 162                         std::string Str() const;
 163
 164                         ParanoidNumber * CopyTerms()
 165                         {
 166                                 ParanoidNumber * copy = new ParanoidNumber(*this);
 167                                 copy->m_value = 0;
 168                                 copy->Simplify(ADD);
 169                                 copy->Simplify(SUBTRACT);
 170                                 return copy;
 171                         }
 172
 173                         ParanoidNumber * CopyFactors()
 174                         {
 175                                 ParanoidNumber * copy = new ParanoidNumber(*this);
 176                                 copy->m_value = 1;
 177                                 copy->Simplify(MULTIPLY);
 178                                 copy->Simplify(DIVIDE);
 179                                 return copy;
 180                         }
 181
 182
 183                         static int64_t Paranoia() {return g_count;}
 184
 185                         std::string PStr() const;
 186
 187                 private:
 188                         static int64_t g_count;
 189                         void Simplify();
 190                         void SimplifyTerms();
 191                         void SimplifyFactors();
 192
 193
 194                         digit_t m_value;
 195                         Optype m_op;
 196                         std::vector<ParanoidNumber*> m_next[4];
 197                         digit_t m_cached_result;
 198                         bool m_cache_valid;
 199         };
 200
 201
 202
 203
 204 template <class T>
 205 T ParanoidNumber::Convert() const
 206 {
 207         if (!isnan(m_cached_result))
 208                 return (T)m_cached_result;
 209         T value(m_value);
 210         for (auto mul : m_next[MULTIPLY])
 211         {
 212                 value *= mul->Convert<T>();
 213         }
 214         for (auto div : m_next[DIVIDE])
 215         {
 216                 value /= div->Convert<T>();
 217         }
 218         for (auto add : m_next[ADD])
 219                 value += add->Convert<T>();
 220         for (auto sub : m_next[SUBTRACT])
 221                 value -= sub->Convert<T>();
 222         return value;
 223 }
 224
 225
 226
 227 }
 228
 229 #endif //_PARANOIDNUMBER_H
 230