1 #ifndef _PARANOIDNUMBER_H
2 #define _PARANOIDNUMBER_H
12 #include <cassert> // it's going to be ok
15 #define PARANOID_DIGIT_T double // we could theoretically replace this with a template
16 // but let's not do that...
19 //#define PARANOID_CACHE_RESULTS
21 //#define PARANOID_USE_ARENA
22 #define PARANOID_SIZE_LIMIT 0
25 // Define to compare all ops against double ops and check within epsilon
26 #define PARANOID_COMPARE_EPSILON 1e-6
27 #define CompareForSanity(...) ParanoidNumber::CompareForSanityEx(__func__, __FILE__, __LINE__, __VA_ARGS__)
31 typedef enum {ADD, SUBTRACT, MULTIPLY, DIVIDE, NOP} Optype;
32 inline Optype InverseOp(Optype op)
34 return ((op == ADD) ? SUBTRACT :
35 (op == SUBTRACT) ? ADD :
36 (op == MULTIPLY) ? DIVIDE :
37 (op == DIVIDE) ? MULTIPLY :
38 (op == NOP) ? NOP : NOP);
42 inline char OpChar(int op)
44 static char opch[] = {'+','-','*','/'};
45 return (op < NOP && op >= 0) ? opch[op] : '?';
49 /** Performs an operation, returning if the result was exact **/
50 // NOTE: DIFFERENT to ParanoidOp (although that wraps to this...)
51 template <class T> bool TrustingOp(T & a, const T & b, Optype op);
53 /** Performs an operation _only_ if the result would be exact **/
54 template <class T> bool ParanoidOp(T & a, const T & b, Optype op)
57 if (TrustingOp<T>(cpy, b, op))
64 template <> bool TrustingOp<float>(float & a, const float & b, Optype op);
65 template <> bool TrustingOp<double>(double & a, const double & b, Optype op);
66 template <> bool TrustingOp<int8_t>(int8_t & a, const int8_t & b, Optype op);
70 * Idea: Perform regular floating point arithmetic but rearrange operations to only ever use exact results
71 * Memory Usage: O(all of it)
72 * CPU Usage: O(all of it)
73 * Accuracy: O(gives better result for 0.3+0.3+0.3, gives same result for everything else, or worse result)
75 * The ParanoidNumber basically stores 4 linked lists which can be split into two "dimensions"
76 * 1. Terms to ADD and terms to SUBTRACT
77 * 2. Factors to MULTIPLY and DIVIDE
78 * Because ADD and SUBTRACT are inverse operations and MULTIPLY and DIVIDE are inverse operations
79 * See paranoidnumber.cpp and the ParanoidNumber::Operation function
85 typedef PARANOID_DIGIT_T digit_t;
87 ParanoidNumber(PARANOID_DIGIT_T value=0) : m_value(value), m_next()
89 #ifdef PARANOID_SIZE_LIMIT
92 #ifdef PARANOID_CACHE_RESULTS
93 m_cached_result = value;
97 ParanoidNumber(const ParanoidNumber & cpy) : m_value(cpy.m_value), m_next()
100 #ifdef PARANOID_SIZE_LIMIT
103 #ifdef PARANOID_CACHE_RESULTS
104 m_cached_result = cpy.m_cached_result;
106 for (int i = 0; i < NOP; ++i)
108 for (auto next : cpy.m_next[i])
110 if (next != NULL) // why would this ever be null
111 m_next[i].push_back(new ParanoidNumber(*next)); // famous last words...
114 #ifdef PARANOID_COMPARE_EPSILON
115 CompareForSanity(cpy.Digit(), cpy.Digit());
117 //assert(SanityCheck());
120 //ParanoidNumber(const char * str);
121 ParanoidNumber(const std::string & str);// : ParanoidNumber(str.c_str()) {}
123 virtual ~ParanoidNumber();
126 bool SanityCheck(std::set<ParanoidNumber*> & visited) const;
127 bool SanityCheck() const
129 std::set<ParanoidNumber*> s;
130 return SanityCheck(s);
133 template <class T> T Convert() const;
134 digit_t GetFactors() const;
135 digit_t GetTerms() const;
137 // This function is declared const purely to trick the compiler.
138 // It is not actually const, and therefore, none of the other functions that call it are const either.
139 digit_t Digit() const;
141 // Like this one. It isn't const.
142 double ToDouble() const {return (double)Digit();}
144 // This one is probably const.
145 bool Floating() const
147 return NoFactors() && NoTerms();
149 bool Sunken() const {return !Floating();} // I could not resist...
151 bool NoFactors() const {return (m_next[MULTIPLY].size() == 0 && m_next[DIVIDE].size() == 0);}
152 bool NoTerms() const {return (m_next[ADD].size() == 0 && m_next[SUBTRACT].size() == 0);}
155 ParanoidNumber & operator+=(const ParanoidNumber & a);
156 ParanoidNumber & operator-=(const ParanoidNumber & a);
157 ParanoidNumber & operator*=(const ParanoidNumber & a);
158 ParanoidNumber & operator/=(const ParanoidNumber & a);
159 ParanoidNumber & operator=(const ParanoidNumber & a);
161 ParanoidNumber & operator+=(const digit_t & a);
162 ParanoidNumber & operator-=(const digit_t & a);
163 ParanoidNumber & operator*=(const digit_t & a);
164 ParanoidNumber & operator/=(const digit_t & a);
165 ParanoidNumber & operator=(const digit_t & a);
168 ParanoidNumber * OperationTerm(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point = NULL, Optype * mop = NULL);
169 ParanoidNumber * OperationFactor(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point = NULL, Optype * mop = NULL);
170 ParanoidNumber * TrivialOp(ParanoidNumber * b, Optype op);
171 ParanoidNumber * Operation(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point = NULL, Optype * mop = NULL);
172 bool Simplify(Optype op);
176 // None of these are actually const
177 bool operator<(const ParanoidNumber & a) const {return Digit() < a.Digit();}
178 bool operator<=(const ParanoidNumber & a) const {return Digit() <= a.Digit();}
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();}
184 ParanoidNumber operator-() const
186 ParanoidNumber neg(*this);
188 #ifdef PARANOID_COMPARE_EPSILON
189 neg.CompareForSanity(-Digit(), Digit());
197 ParanoidNumber operator+(const ParanoidNumber & a) const
199 ParanoidNumber result(*this);
201 #ifdef PARANOID_COMPARE_EPSILON
202 result.CompareForSanity(Digit()+a.Digit(), a.Digit());
206 ParanoidNumber operator-(const ParanoidNumber & a) const
208 ParanoidNumber result(*this);
210 #ifdef PARANOID_COMPARE_EPSILON
211 result.CompareForSanity(Digit()-a.Digit(), a.Digit());
215 ParanoidNumber operator*(const ParanoidNumber & a) const
217 ParanoidNumber result(*this);
219 #ifdef PARANOID_COMPARE_EPSILON
220 result.CompareForSanity(Digit()*a.Digit(), a.Digit());
224 ParanoidNumber operator/(const ParanoidNumber & a) const
226 ParanoidNumber result(*this);
228 #ifdef PARANOID_COMPARE_EPSILON
229 result.CompareForSanity(Digit()/a.Digit(), a.Digit());
234 std::string Str() const;
236 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)
238 if (fabs(Digit() - compare) > eps)
240 Error("Called via %s(%lf) (%s:%d)", func, arg, file, line);
241 Error("Failed: %s", Str().c_str());
242 Fatal("This: %.30lf vs Expected: %.30lf", Digit(), compare);
247 std::string PStr() const;
249 #ifdef PARANOID_USE_ARENA
250 void * operator new(size_t byes);
251 void operator delete(void * p);
252 #endif //PARANOID_USE_ARENA
257 void SimplifyTerms();
258 void SimplifyFactors();
261 #ifdef PARANOID_CACHE_RESULTS
262 digit_t m_cached_result;
264 std::vector<ParanoidNumber*> m_next[4];
265 #ifdef PARANOID_SIZE_LIMIT
267 #endif //PARANOID_SIZE_LIMIT
269 #ifdef PARANOID_USE_ARENA
273 Arena(int64_t block_size = 10000000);
276 void * allocate(size_t bytes);
277 void deallocate(void * p);
286 std::vector<Block> m_blocks;
287 int64_t m_block_size;
293 static Arena g_arena;
294 #endif //PARANOID_USE_ARENA
303 T ParanoidNumber::Convert() const
305 #ifdef PARANOID_CACHE_RESULTS
306 if (!isnan((float(m_cached_result))))
307 return (T)m_cached_result;
310 for (auto mul : m_next[MULTIPLY])
312 value *= mul->Convert<T>();
314 for (auto div : m_next[DIVIDE])
316 value /= div->Convert<T>();
318 for (auto add : m_next[ADD])
319 value += add->Convert<T>();
320 for (auto sub : m_next[SUBTRACT])
321 value -= sub->Convert<T>();
329 #endif //_PARANOIDNUMBER_H