1 #ifndef _PARANOIDNUMBER_H
2 #define _PARANOIDNUMBER_H
12 #include <cassert> // it's going to be ok
15 #define PARANOID_DIGIT_T float // 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 3
25 // Define to compare all ops against double ops and check within epsilon
26 //#define PARANOID_COMPARE_EPSILON 1e-6
27 #ifdef PARANOID_COMPARE_EPSILON
28 #define CompareForSanity(...) ParanoidNumber::CompareForSanityEx(__func__, __FILE__, __LINE__, __VA_ARGS__)
33 typedef enum {ADD, SUBTRACT, MULTIPLY, DIVIDE, NOP} Optype;
34 inline Optype InverseOp(Optype op)
36 return ((op == ADD) ? SUBTRACT :
37 (op == SUBTRACT) ? ADD :
38 (op == MULTIPLY) ? DIVIDE :
39 (op == DIVIDE) ? MULTIPLY :
40 (op == NOP) ? NOP : NOP);
44 inline char OpChar(int op)
46 static char opch[] = {'+','-','*','/'};
47 return (op < NOP && op >= 0) ? opch[op] : '?';
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);
55 /** Performs an operation _only_ if the result would be exact **/
56 template <class T> bool ParanoidOp(T & a, const T & b, Optype op)
59 if (TrustingOp<T>(cpy, b, op))
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);
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)
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
87 typedef PARANOID_DIGIT_T digit_t;
89 ParanoidNumber(PARANOID_DIGIT_T value=0) : m_value(value), m_next()
91 #ifdef PARANOID_SIZE_LIMIT
94 #ifdef PARANOID_CACHE_RESULTS
95 m_cached_result = value;
100 ParanoidNumber(const ParanoidNumber & cpy) : m_value(cpy.m_value), m_next()
103 #ifdef PARANOID_SIZE_LIMIT
106 #ifdef PARANOID_CACHE_RESULTS
107 m_cached_result = cpy.m_cached_result;
108 m_cache_valid = cpy.m_cache_valid;
110 for (int i = 0; i < NOP; ++i)
112 for (auto next : cpy.m_next[i])
114 if (next != NULL) // why would this ever be null
115 m_next[i].push_back(new ParanoidNumber(*next)); // famous last words...
118 #ifdef PARANOID_COMPARE_EPSILON
119 CompareForSanity(cpy.Digit(), cpy.Digit());
121 //assert(SanityCheck());
124 //ParanoidNumber(const char * str);
125 ParanoidNumber(const std::string & str);// : ParanoidNumber(str.c_str()) {}
127 virtual ~ParanoidNumber();
130 bool SanityCheck(std::set<ParanoidNumber*> & visited) const;
131 bool SanityCheck() const
133 std::set<ParanoidNumber*> s;
134 return SanityCheck(s);
137 template <class T> T Convert() const;
138 digit_t GetFactors() const;
139 digit_t GetTerms() const;
141 // This function is declared const purely to trick the compiler.
142 // It is not actually const, and therefore, none of the other functions that call it are const either.
143 digit_t Digit() const;
145 // Like this one. It isn't const.
146 double ToDouble() const {return (double)Digit();}
148 // This one is probably const.
149 bool Floating() const
151 return NoFactors() && NoTerms();
153 bool Sunken() const {return !Floating();} // I could not resist...
155 bool NoFactors() const {return (m_next[MULTIPLY].size() == 0 && m_next[DIVIDE].size() == 0);}
156 bool NoTerms() const {return (m_next[ADD].size() == 0 && m_next[SUBTRACT].size() == 0);}
159 ParanoidNumber & operator+=(const ParanoidNumber & a);
160 ParanoidNumber & operator-=(const ParanoidNumber & a);
161 ParanoidNumber & operator*=(const ParanoidNumber & a);
162 ParanoidNumber & operator/=(const ParanoidNumber & a);
163 ParanoidNumber & operator=(const ParanoidNumber & a);
165 ParanoidNumber & operator+=(const digit_t & a);
166 ParanoidNumber & operator-=(const digit_t & a);
167 ParanoidNumber & operator*=(const digit_t & a);
168 ParanoidNumber & operator/=(const digit_t & a);
169 ParanoidNumber & operator=(const digit_t & a);
172 ParanoidNumber * OperationTerm(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point = NULL, Optype * mop = NULL);
173 ParanoidNumber * OperationFactor(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point = NULL, Optype * mop = NULL);
174 ParanoidNumber * TrivialOp(ParanoidNumber * b, Optype op);
175 ParanoidNumber * Operation(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point = NULL, Optype * mop = NULL);
176 bool Simplify(Optype op);
180 // None of these are actually const
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 bool operator==(const ParanoidNumber & a) const {return Digit() == a.Digit();}
186 bool operator!=(const ParanoidNumber & a) const {return Digit() != a.Digit();}
188 ParanoidNumber operator-() const
190 ParanoidNumber neg(*this);
192 #ifdef PARANOID_COMPARE_EPSILON
193 neg.CompareForSanity(-Digit(), Digit());
201 ParanoidNumber operator+(const ParanoidNumber & a) const
203 ParanoidNumber result(*this);
205 #ifdef PARANOID_COMPARE_EPSILON
206 result.CompareForSanity(Digit()+a.Digit(), a.Digit());
210 ParanoidNumber operator-(const ParanoidNumber & a) const
212 ParanoidNumber result(*this);
214 #ifdef PARANOID_COMPARE_EPSILON
215 result.CompareForSanity(Digit()-a.Digit(), a.Digit());
219 ParanoidNumber operator*(const ParanoidNumber & a) const
221 ParanoidNumber result(*this);
223 #ifdef PARANOID_COMPARE_EPSILON
224 result.CompareForSanity(Digit()*a.Digit(), a.Digit());
228 ParanoidNumber operator/(const ParanoidNumber & a) const
230 ParanoidNumber result(*this);
232 #ifdef PARANOID_COMPARE_EPSILON
233 result.CompareForSanity(Digit()/a.Digit(), a.Digit());
238 std::string Str() const;
240 #ifdef PARANOID_COMPARE_EPSILON
241 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)
244 Fatal("This is insane!");
245 if (fabs(Digit() - compare) > eps)
247 Error("Called via %s(%lf) (%s:%d)", func, arg, file, line);
248 Error("Failed: %s", Str().c_str());
249 Fatal("This: %.30lf vs Expected: %.30lf", Digit(), compare);
254 std::string PStr() const;
256 #ifdef PARANOID_USE_ARENA
257 void * operator new(size_t byes);
258 void operator delete(void * p);
259 #endif //PARANOID_USE_ARENA
264 void SimplifyTerms();
265 void SimplifyFactors();
268 #ifdef PARANOID_CACHE_RESULTS
269 digit_t m_cached_result;
272 std::vector<ParanoidNumber*> m_next[4];
273 #ifdef PARANOID_SIZE_LIMIT
275 #endif //PARANOID_SIZE_LIMIT
277 #ifdef PARANOID_USE_ARENA
281 Arena(int64_t block_size = 10000);
284 void * allocate(size_t bytes);
285 void deallocate(void * p);
294 std::vector<Block> m_blocks;
295 int64_t m_block_size;
301 static Arena g_arena;
302 #endif //PARANOID_USE_ARENA
311 T ParanoidNumber::Convert() const
313 #ifdef PARANOID_CACHE_RESULTS
315 return (T)m_cached_result;
318 for (auto mul : m_next[MULTIPLY])
320 value *= mul->Convert<T>();
322 for (auto div : m_next[DIVIDE])
324 value /= div->Convert<T>();
326 for (auto add : m_next[ADD])
327 value += add->Convert<T>();
328 for (auto sub : m_next[SUBTRACT])
329 value -= sub->Convert<T>();
337 #endif //_PARANOIDNUMBER_H