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 1
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)
239 Fatal("This is insane!");
240 if (fabs(Digit() - compare) > eps)
242 Error("Called via %s(%lf) (%s:%d)", func, arg, file, line);
243 Error("Failed: %s", Str().c_str());
244 Fatal("This: %.30lf vs Expected: %.30lf", Digit(), compare);
249 std::string PStr() const;
251 #ifdef PARANOID_USE_ARENA
252 void * operator new(size_t byes);
253 void operator delete(void * p);
254 #endif //PARANOID_USE_ARENA
259 void SimplifyTerms();
260 void SimplifyFactors();
263 #ifdef PARANOID_CACHE_RESULTS
264 digit_t m_cached_result;
266 std::vector<ParanoidNumber*> m_next[4];
267 #ifdef PARANOID_SIZE_LIMIT
269 #endif //PARANOID_SIZE_LIMIT
271 #ifdef PARANOID_USE_ARENA
275 Arena(int64_t block_size = 10000000);
278 void * allocate(size_t bytes);
279 void deallocate(void * p);
288 std::vector<Block> m_blocks;
289 int64_t m_block_size;
295 static Arena g_arena;
296 #endif //PARANOID_USE_ARENA
305 T ParanoidNumber::Convert() const
307 #ifdef PARANOID_CACHE_RESULTS
308 if (!isnan((float(m_cached_result))))
309 return (T)m_cached_result;
312 for (auto mul : m_next[MULTIPLY])
314 value *= mul->Convert<T>();
316 for (auto div : m_next[DIVIDE])
318 value /= div->Convert<T>();
320 for (auto add : m_next[ADD])
321 value += add->Convert<T>();
322 for (auto sub : m_next[SUBTRACT])
323 value -= sub->Convert<T>();
331 #endif //_PARANOIDNUMBER_H