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