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(...) this->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 //assert(SanityCheck());
117 //ParanoidNumber(const char * str);
118 ParanoidNumber(const std::string & str);// : ParanoidNumber(str.c_str()) {}
120 virtual ~ParanoidNumber();
123 bool SanityCheck(std::set<ParanoidNumber*> & visited) const;
124 bool SanityCheck() const
126 std::set<ParanoidNumber*> s;
127 return SanityCheck(s);
130 template <class T> T Convert() const;
131 digit_t GetFactors() const;
132 digit_t GetTerms() const;
134 // This function is declared const purely to trick the compiler.
135 // It is not actually const, and therefore, none of the other functions that call it are const either.
136 digit_t Digit() const;
138 // Like this one. It isn't const.
139 double ToDouble() const {return (double)Digit();}
141 // This one is probably const.
142 bool Floating() const
144 return NoFactors() && NoTerms();
146 bool Sunken() const {return !Floating();} // I could not resist...
148 bool NoFactors() const {return (m_next[MULTIPLY].size() == 0 && m_next[DIVIDE].size() == 0);}
149 bool NoTerms() const {return (m_next[ADD].size() == 0 && m_next[SUBTRACT].size() == 0);}
152 ParanoidNumber & operator+=(const ParanoidNumber & a);
153 ParanoidNumber & operator-=(const ParanoidNumber & a);
154 ParanoidNumber & operator*=(const ParanoidNumber & a);
155 ParanoidNumber & operator/=(const ParanoidNumber & a);
156 ParanoidNumber & operator=(const ParanoidNumber & a);
158 ParanoidNumber & operator+=(const digit_t & a);
159 ParanoidNumber & operator-=(const digit_t & a);
160 ParanoidNumber & operator*=(const digit_t & a);
161 ParanoidNumber & operator/=(const digit_t & a);
162 ParanoidNumber & operator=(const digit_t & a);
165 ParanoidNumber * OperationTerm(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point = NULL, Optype * mop = NULL);
166 ParanoidNumber * OperationFactor(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point = NULL, Optype * mop = NULL);
167 ParanoidNumber * TrivialOp(ParanoidNumber * b, Optype op);
168 ParanoidNumber * Operation(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point = NULL, Optype * mop = NULL);
169 bool Simplify(Optype op);
173 // None of these are actually const
174 bool operator<(const ParanoidNumber & a) const {return ToDouble() < a.ToDouble();}
175 bool operator<=(const ParanoidNumber & a) const {return this->operator<(a) || this->operator==(a);}
176 bool operator>(const ParanoidNumber & a) const {return !(this->operator<=(a));}
177 bool operator>=(const ParanoidNumber & a) const {return !(this->operator<(a));}
178 bool operator==(const ParanoidNumber & a) const {return ToDouble() == a.ToDouble();}
179 bool operator!=(const ParanoidNumber & a) const {return !(this->operator==(a));}
181 ParanoidNumber operator-() const
183 ParanoidNumber neg(0);
188 ParanoidNumber operator+(const ParanoidNumber & a) const
190 ParanoidNumber result(*this);
195 ParanoidNumber operator-(const ParanoidNumber & a) const
197 ParanoidNumber result(*this);
201 ParanoidNumber operator*(const ParanoidNumber & a) const
203 ParanoidNumber result(*this);
205 if (!result.SanityCheck())
211 ParanoidNumber operator/(const ParanoidNumber & a) const
213 ParanoidNumber result(*this);
218 std::string Str() const;
220 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)
222 if (fabs(Digit() - compare) > eps)
224 Error("Called via %s(%lf) (%s:%d)", func, arg, file, line);
225 Error("Failed: %s", Str().c_str());
226 Fatal("This: %.30lf vs Expected: %.30lf", Digit(), compare);
231 std::string PStr() const;
233 #ifdef PARANOID_USE_ARENA
234 void * operator new(size_t byes);
235 void operator delete(void * p);
236 #endif //PARANOID_USE_ARENA
241 void SimplifyTerms();
242 void SimplifyFactors();
245 #ifdef PARANOID_CACHE_RESULTS
246 digit_t m_cached_result;
248 std::vector<ParanoidNumber*> m_next[4];
249 #ifdef PARANOID_SIZE_LIMIT
251 #endif //PARANOID_SIZE_LIMIT
253 #ifdef PARANOID_USE_ARENA
257 Arena(int64_t block_size = 10000000);
260 void * allocate(size_t bytes);
261 void deallocate(void * p);
270 std::vector<Block> m_blocks;
271 int64_t m_block_size;
277 static Arena g_arena;
278 #endif //PARANOID_USE_ARENA
287 T ParanoidNumber::Convert() const
289 #ifdef PARANOID_CACHE_RESULTS
290 if (!isnan((float(m_cached_result))))
291 return (T)m_cached_result;
294 for (auto mul : m_next[MULTIPLY])
296 value *= mul->Convert<T>();
298 for (auto div : m_next[DIVIDE])
300 value /= div->Convert<T>();
302 for (auto add : m_next[ADD])
303 value += add->Convert<T>();
304 for (auto sub : m_next[SUBTRACT])
305 value -= sub->Convert<T>();
313 #endif //_PARANOIDNUMBER_H