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

UCC git Repository :: git.ucc.asn.au