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