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 10
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__)
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;
99 ParanoidNumber(const ParanoidNumber & cpy) : m_value(cpy.m_value), m_next()
102 #ifdef PARANOID_SIZE_LIMIT
105 #ifdef PARANOID_CACHE_RESULTS
106 m_cached_result = cpy.m_cached_result;
108 for (int i = 0; i < NOP; ++i)
110 for (auto next : cpy.m_next[i])
112 if (next != NULL) // why would this ever be null
113 m_next[i].push_back(new ParanoidNumber(*next)); // famous last words...
116 #ifdef PARANOID_COMPARE_EPSILON
117 CompareForSanity(cpy.Digit(), cpy.Digit());
119 //assert(SanityCheck());
122 //ParanoidNumber(const char * str);
123 ParanoidNumber(const std::string & str);// : ParanoidNumber(str.c_str()) {}
125 virtual ~ParanoidNumber();
128 bool SanityCheck(std::set<ParanoidNumber*> & visited) const;
129 bool SanityCheck() const
131 std::set<ParanoidNumber*> s;
132 return SanityCheck(s);
135 template <class T> T Convert() const;
136 digit_t GetFactors() const;
137 digit_t GetTerms() const;
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;
143 // Like this one. It isn't const.
144 double ToDouble() const {return (double)Digit();}
146 // This one is probably const.
147 bool Floating() const
149 return NoFactors() && NoTerms();
151 bool Sunken() const {return !Floating();} // I could not resist...
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);}
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);
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);
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);
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();}
186 ParanoidNumber operator-() const
188 ParanoidNumber neg(*this);
190 #ifdef PARANOID_COMPARE_EPSILON
191 neg.CompareForSanity(-Digit(), Digit());
199 ParanoidNumber operator+(const ParanoidNumber & a) const
201 ParanoidNumber result(*this);
203 #ifdef PARANOID_COMPARE_EPSILON
204 result.CompareForSanity(Digit()+a.Digit(), a.Digit());
208 ParanoidNumber operator-(const ParanoidNumber & a) const
210 ParanoidNumber result(*this);
212 #ifdef PARANOID_COMPARE_EPSILON
213 result.CompareForSanity(Digit()-a.Digit(), a.Digit());
217 ParanoidNumber operator*(const ParanoidNumber & a) const
219 ParanoidNumber result(*this);
221 #ifdef PARANOID_COMPARE_EPSILON
222 result.CompareForSanity(Digit()*a.Digit(), a.Digit());
226 ParanoidNumber operator/(const ParanoidNumber & a) const
228 ParanoidNumber result(*this);
230 #ifdef PARANOID_COMPARE_EPSILON
231 result.CompareForSanity(Digit()/a.Digit(), a.Digit());
236 std::string Str() const;
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)
242 Fatal("This is insane!");
243 if (fabs(Digit() - compare) > eps)
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);
252 std::string PStr() const;
254 #ifdef PARANOID_USE_ARENA
255 void * operator new(size_t byes);
256 void operator delete(void * p);
257 #endif //PARANOID_USE_ARENA
262 void SimplifyTerms();
263 void SimplifyFactors();
266 #ifdef PARANOID_CACHE_RESULTS
267 digit_t m_cached_result;
269 std::vector<ParanoidNumber*> m_next[4];
270 #ifdef PARANOID_SIZE_LIMIT
272 #endif //PARANOID_SIZE_LIMIT
274 #ifdef PARANOID_USE_ARENA
278 Arena(int64_t block_size = 10000000);
281 void * allocate(size_t bytes);
282 void deallocate(void * p);
291 std::vector<Block> m_blocks;
292 int64_t m_block_size;
298 static Arena g_arena;
299 #endif //PARANOID_USE_ARENA
308 T ParanoidNumber::Convert() const
310 #ifdef PARANOID_CACHE_RESULTS
311 if (!isnan((float(m_cached_result))))
312 return (T)m_cached_result;
315 for (auto mul : m_next[MULTIPLY])
317 value *= mul->Convert<T>();
319 for (auto div : m_next[DIVIDE])
321 value /= div->Convert<T>();
323 for (auto add : m_next[ADD])
324 value += add->Convert<T>();
325 for (auto sub : m_next[SUBTRACT])
326 value -= sub->Convert<T>();
334 #endif //_PARANOIDNUMBER_H