#include <cassert>
#include <iostream>
+// here be many copy paste bugs
+
using namespace std;
namespace IPDF
{
-int64_t ParanoidNumber::g_count = 0;
+#ifdef PARANOID_USE_ARENA
+ParanoidNumber::Arena ParanoidNumber::g_arena;
+#endif //PARANOID_USE_ARENA
+
ParanoidNumber::~ParanoidNumber()
{
- g_count--;
for (int i = 0; i < NOP; ++i)
{
for (auto n : m_next[i])
}
}
-ParanoidNumber::ParanoidNumber(const string & str) : m_value(0), m_cached_result(0), m_cache_valid(false), m_next()
+ParanoidNumber::ParanoidNumber(const string & str) : m_value(0), m_next()
{
- Construct();
+ #ifdef PARANOID_SIZE_LIMIT
+ m_size = 1;
+ #endif
+ #ifdef PARANOID_CACHE_RESULTS
+ m_cache_valid = false;
+ #endif
+
int dp = 0;
int end = 0;
+ bool negate = str[0] == '-';
+ if (negate)
+ {
+ dp++;
+ end++;
+ }
while (str[dp] != '\0' && str[dp] != '.')
{
++dp;
while (str[end] != '\0')
++end;
ParanoidNumber m(1);
- for (int i = dp-1; i >= 0; --i)
+ for (int i = dp-1; i >= negate; --i)
{
ParanoidNumber b(str[i]-'0');
b*=m;
b*=n;
this->operator+=(b);
}
+
+ if (negate)
+ Negate();
+
+ #ifdef PARANOID_COMPARE_EPSILON
+ double d = strtod(str.c_str(), NULL);
+ CompareForSanity(d, d);
+ #endif
}
ParanoidNumber & ParanoidNumber::operator=(const ParanoidNumber & a)
{
- assert(this != NULL);
+ //assert(this != NULL);
+
+ #ifdef PARANOID_SIZE_LIMIT
+ m_size = a.m_size;
+ #endif
+
m_value = a.m_value;
+ #ifdef PARANOID_CACHE_RESULTS
m_cached_result = a.m_cached_result;
+ m_cache_valid = a.m_cache_valid;
+ #endif
for (int i = 0; i < NOP; ++i)
{
for (auto n : m_next[i])
for (auto n : a.m_next[i])
m_next[i].push_back(new ParanoidNumber(*n));
}
- /*
- for (unsigned j = 0; j < m_next[i].size() && j < a.m_next[i].size(); ++j)
- {
- if (a.m_next[i][j] != NULL)
- m_next[i][j]->operator=(*(a.m_next[i][j]));
- }
-
- for (unsigned j = a.m_next[i].size(); j < m_next[i].size(); ++j)
- {
- delete m_next[i][j];
- }
- m_next[i].resize(a.m_next[i].size());
- */
- //}
+ #ifdef PARANOID_COMPARE_EPSILON
+ CompareForSanity(a.Digit(),a.Digit());
+ #endif
return *this;
}
string ParanoidNumber::Str() const
{
- assert(this != NULL);
+ //assert(this != NULL);
string result("");
stringstream s;
s << (double)m_value;
template <>
bool TrustingOp<float>(float & a, const float & b, Optype op)
{
+
feclearexcept(FE_ALL_EXCEPT);
switch (op)
return !fetestexcept(FE_ALL_EXCEPT);
}
+
+
+template <>
+bool TrustingOp<long double>(long double & a, const long double & b, Optype op)
+{
+
+
+ feclearexcept(FE_ALL_EXCEPT);
+ switch (op)
+ {
+ case ADD:
+ a += b;
+ break;
+ case SUBTRACT:
+ a -= b;
+ break;
+ case MULTIPLY:
+ a *= b;
+ break;
+ case DIVIDE:
+ if (b == 0)
+ {
+ a = (a >= 0) ? INFINITY : -INFINITY;
+ return false;
+ }
+
+ a /= b;
+ break;
+ case NOP:
+ break;
+ }
+ return !fetestexcept(FE_ALL_EXCEPT);
+}
+
+
template <>
bool TrustingOp<int8_t>(int8_t & a, const int8_t & b, Optype op)
{
}
-ParanoidNumber & ParanoidNumber::operator+=(const ParanoidNumber & a)
+ParanoidNumber & ParanoidNumber::operator+=(const digit_t & a)
{
-
- assert(this != NULL);
- delete Operation(SafeConstruct(a), ADD);
+ #ifdef PARANOID_COMPARE_EPSILON
+ digit_t compare = Digit();
+ compare += a;
+ #endif
+ delete Operation(new ParanoidNumber(a), ADD);
+ Simplify(SUBTRACT);
+ Simplify(ADD);
+ #ifdef PARANOID_COMPARE_EPSILON
+ CompareForSanity(compare, a);
+ #endif
+ return *this;
+}
+
+
+ParanoidNumber & ParanoidNumber::operator-=(const digit_t & a)
+{
+ #ifdef PARANOID_COMPARE_EPSILON
+ digit_t compare = Digit();
+ compare -= a;
+ #endif
+ delete Operation(new ParanoidNumber(a), SUBTRACT);
Simplify(ADD);
Simplify(SUBTRACT);
+ #ifdef PARANOID_COMPARE_EPSILON
+ CompareForSanity(compare, a);
+ #endif
return *this;
}
+ParanoidNumber & ParanoidNumber::operator*=(const digit_t & a)
+{
+ #ifdef PARANOID_COMPARE_EPSILON
+ digit_t compare = Digit();
+ compare *= a;
+ #endif
+ delete Operation(new ParanoidNumber(a), MULTIPLY);
+ Simplify(DIVIDE);
+ Simplify(MULTIPLY);
+ #ifdef PARANOID_COMPARE_EPSILON
+ CompareForSanity(compare, a);
+ #endif
+ return *this;
+}
-ParanoidNumber & ParanoidNumber::operator-=(const ParanoidNumber & a)
+
+ParanoidNumber & ParanoidNumber::operator/=(const digit_t & a)
+{
+ #ifdef PARANOID_COMPARE_EPSILON
+ digit_t compare = Digit();
+ compare /= a;
+ #endif
+ delete Operation(new ParanoidNumber(a), DIVIDE);
+ Simplify(MULTIPLY);
+ Simplify(DIVIDE);
+ #ifdef PARANOID_COMPARE_EPSILON
+ CompareForSanity(compare, a);
+ #endif
+ return *this;
+}
+
+
+ParanoidNumber & ParanoidNumber::operator+=(const ParanoidNumber & a)
{
- delete Operation(SafeConstruct(a), SUBTRACT);
+ #ifdef PARANOID_COMPARE_EPSILON
+ digit_t compare = Digit();
+ compare += a.Digit();
+ #endif
+ delete Operation(new ParanoidNumber(a), ADD);
Simplify(SUBTRACT);
Simplify(ADD);
+ #ifdef PARANOID_COMPARE_EPSILON
+ CompareForSanity(compare, a.Digit());
+ #endif
+ return *this;
+}
+
+
+ParanoidNumber & ParanoidNumber::operator-=(const ParanoidNumber & a)
+{
+ #ifdef PARANOID_COMPARE_EPSILON
+ digit_t compare = Digit();
+ compare -= a.Digit();
+ #endif
+ delete Operation(new ParanoidNumber(a), SUBTRACT);
+ Simplify(ADD);
+ Simplify(SUBTRACT);
+ #ifdef PARANOID_COMPARE_EPSILON
+ CompareForSanity(compare, a.Digit());
+ #endif
return *this;
}
ParanoidNumber & ParanoidNumber::operator*=(const ParanoidNumber & a)
{
- delete Operation(SafeConstruct(a), MULTIPLY);
+ #ifdef PARANOID_COMPARE_EPSILON
+ digit_t compare = Digit();
+ compare *= a.Digit();
+ #endif
+ delete Operation(new ParanoidNumber(a), MULTIPLY);
+ Simplify(DIVIDE);
Simplify(MULTIPLY);
- Simplify(DIVIDE);
+ #ifdef PARANOID_COMPARE_EPSILON
+ CompareForSanity(compare, a.Digit());
+ #endif
return *this;
}
ParanoidNumber & ParanoidNumber::operator/=(const ParanoidNumber & a)
{
- delete Operation(SafeConstruct(a), DIVIDE);
+ #ifdef PARANOID_COMPARE_EPSILON
+ digit_t compare = Digit();
+ compare /= a.Digit();
+ #endif
+ delete Operation(new ParanoidNumber(a), DIVIDE);
Simplify(MULTIPLY);
Simplify(DIVIDE);
+ #ifdef PARANOID_COMPARE_EPSILON
+ CompareForSanity(compare, a.Digit());
+ #endif
return *this;
}
-// a + b
-ParanoidNumber * ParanoidNumber::OperationTerm(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point, Optype * merge_op)
+ParanoidNumber & ParanoidNumber::operator=(const digit_t & a)
{
- if (!SanityCheck())
+
+ for (int i = 0; i < NOP; ++i)
{
- Fatal("What...");
+ for (auto n : m_next[i])
+ delete n;
+ m_next[i].clear();
}
- assert(b->SanityCheck());
+ m_value = a;
+ #ifdef PARANOID_CACHE_RESULTS
+ m_cached_result = a;
+ m_cache_valid = true;
+ #endif
+
+ #ifdef PARANOID_COMPARE_EPSILON
+ CompareForSanity(a,a);
+ #endif
+
+ return *this;
+}
+
+// a + b
+ParanoidNumber * ParanoidNumber::OperationTerm(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point, Optype * merge_op)
+{
+ ////assert(b->SanityCheck());
+ #ifdef PARANOID_CACHE_RESULTS
+ m_cache_valid = false;
+ #endif
+ #ifdef PARANOID_SIZE_LIMIT
+ if (m_size + b->m_size >= PARANOID_SIZE_LIMIT)
+ {
+ this->operator=(this->Digit());
+ if (op == ADD)
+ m_value += b->Digit();
+ else
+ m_value -= b->Digit();
+ m_size = 1;
+ #ifdef PARANOID_CACHE_RESULTS
+ m_cached_result = m_value;
+ m_cache_valid = true;
+ #endif
+ return b;
+ }
+ //Debug("At size limit %d", m_size);
+ #endif
- m_cached_result = nan("");
+
if (Floating() && m_value == 0) // 0 + b = b
{
m_value = b->m_value;
b->m_next[i].clear();
}
- assert(SanityCheck());
+ //assert(SanityCheck());
return b;
}
if (b->Floating() && b->m_value == 0) // a + 0 = a
Optype addop = (op == ADD) ? ADD : SUBTRACT;
for (auto add : b->m_next[ADD])
{
- delete OperationTerm(add, addop);
+ delete (OperationTerm(add, addop));
}
Optype subop = (op == ADD) ? SUBTRACT : ADD;
for (auto sub : b->m_next[SUBTRACT])
- delete OperationTerm(sub, subop);
+ delete (OperationTerm(sub, subop));
b->m_next[ADD].clear();
b->m_next[SUBTRACT].clear();
- assert(SanityCheck());
+ //assert(SanityCheck());
return b;
}
}
bool parent = (merge_point == NULL);
ParanoidNumber * merge = this;
Optype mop = op;
- assert(mop != NOP); // silence compiler warning
+ //assert(mop != NOP); // silence compiler warning
if (parent)
{
merge_point = &merge;
{
if (prev->OperationTerm(b, rev, merge_point, merge_op) == b)
{
- assert(SanityCheck());
+ //assert(SanityCheck());
return b;
}
{
if (next->OperationTerm(b, fwd, merge_point, merge_op) == b)
{
- assert(SanityCheck());
+ //assert(SanityCheck());
return b;
}
}
{
//merge->m_next[*merge_op].push_back(b);
m_next[op].push_back(b);
+ #ifdef PARANOID_SIZE_LIMIT
+ m_size += b->m_size;
+ #endif
}
else
{
}
}
- assert(SanityCheck());
+ //assert(SanityCheck());
+
return NULL;
}
ParanoidNumber * ParanoidNumber::OperationFactor(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point, Optype * merge_op)
{
- assert(SanityCheck());
- assert(b->SanityCheck());
- m_cached_result = nan("");
+ #ifdef PARANOID_CACHE_RESULTS
+ m_cache_valid = false;
+ #endif
+ #ifdef PARANOID_SIZE_LIMIT
+ if (m_size + b->m_size >= PARANOID_SIZE_LIMIT)
+ {
+ this->operator=(this->Digit());
+ if (op == MULTIPLY)
+ m_value *= b->Digit();
+ else
+ m_value /= b->Digit();
+ m_size = 1;
+ #ifdef PARANOID_CACHE_RESULTS
+ m_cached_result = m_value;
+ m_cache_valid = true;
+ #endif
+ //Debug("Cut off %p", this);
+ return b;
+
+ }
+ #endif
+
if (Floating() && m_value == 0)
{
return b;
for (int i = 0; i < NOP; ++i)
{
for (auto n : m_next[i])
- delete n;
+ delete (n);
m_next[i].clear();
swap(m_next[i], b->m_next[i]);
}
- assert(SanityCheck());
+ //assert(SanityCheck());
return b;
}
if (b->Floating() && b->m_value == 1)
return b;
-
+ if (b->Floating() && b->m_value == 0 && op == MULTIPLY)
+ {
+ operator=(*b);
+ return b;
+ }
if (NoTerms() && b->NoTerms())
Optype mulop = (op == MULTIPLY) ? MULTIPLY : DIVIDE;
for (auto mul : b->m_next[MULTIPLY])
{
- delete OperationFactor(mul, mulop);
+ delete(OperationFactor(mul, mulop));
}
Optype divop = (op == MULTIPLY) ? DIVIDE : MULTIPLY;
for (auto div : b->m_next[DIVIDE])
- delete OperationFactor(div, divop);
+ delete(OperationFactor(div, divop));
b->m_next[DIVIDE].clear();
b->m_next[MULTIPLY].clear();
-
-
- assert(SanityCheck());
return b;
}
}
rev = DIVIDE;
}
- ParanoidNumber * cpy_b = NULL;
-
- if (m_next[ADD].size() > 0 || m_next[SUBTRACT].size() > 0)
- {
- cpy_b = SafeConstruct(*b);
- }
-
+ ParanoidNumber * cpy_b = new ParanoidNumber(*b);
for (auto prev : m_next[invop])
{
if (prev->OperationFactor(b, rev, merge_point, merge_op) == b)
{
for (auto add : m_next[ADD])
- delete add->OperationFactor(SafeConstruct(*cpy_b), op);
+ delete(add->OperationFactor(new ParanoidNumber(*cpy_b), op));
for (auto sub : m_next[SUBTRACT])
- delete sub->OperationFactor(SafeConstruct(*cpy_b), op);
+ delete(sub->OperationFactor(new ParanoidNumber(*cpy_b), op));
- delete cpy_b;
- assert(SanityCheck());
+ delete(cpy_b);
return b;
}
}
{
for (auto add : m_next[ADD])
{
- delete add->OperationFactor(SafeConstruct(*cpy_b), op);
+ delete(add->OperationFactor(new ParanoidNumber(*cpy_b), op));
}
for (auto sub : m_next[SUBTRACT])
{
- delete sub->OperationFactor(SafeConstruct(*cpy_b), op);
+ delete(sub->OperationFactor(new ParanoidNumber(*cpy_b), op));
}
- delete cpy_b;
- assert(SanityCheck());
+ delete(cpy_b);
return b;
}
}
if (parent)
{
- assert(b != NULL);
+ //assert(b != NULL);
m_next[op].push_back(b);
for (auto add : m_next[ADD])
- delete add->OperationFactor(SafeConstruct(*cpy_b), op);
+ delete(add->OperationFactor(new ParanoidNumber(*cpy_b), op));
for (auto sub : m_next[SUBTRACT])
- delete sub->OperationFactor(SafeConstruct(*cpy_b), op);
+ delete(sub->OperationFactor(new ParanoidNumber(*cpy_b), op));
+
+ #ifdef PARANOID_SIZE_LIMIT
+ m_size += b->m_size;
+ #endif
}
- assert(SanityCheck());
+ //assert(SanityCheck());
+
+
+
return NULL;
}
bool ParanoidNumber::Simplify(Optype op)
{
+
if (Floating())
return false;
- assert(SanityCheck());
+ //assert(SanityCheck());
vector<ParanoidNumber*> next;
next.clear();
swap(m_next[op], next);
m_next[op].clear();
- assert(m_next[op].size() == 0);
- assert(SanityCheck());
+ //assert(m_next[op].size() == 0);
+ //assert(SanityCheck());
Optype fwd = op;
if (op == DIVIDE)
fwd = MULTIPLY;
else if (op == SUBTRACT)
fwd = ADD;
+
+ vector<ParanoidNumber*> hold[2];
+ if (op == MULTIPLY || op == DIVIDE)
+ {
+ swap(m_next[ADD], hold[0]);
+ swap(m_next[SUBTRACT], hold[1]);
+ }
for (vector<ParanoidNumber*>::iterator n = next.begin(); n != next.end(); ++n)
{
ParanoidNumber * result = (*n)->Operation(*m, fwd, &parent, &mop);
if (result != NULL)
{
+ #ifdef PARANOID_SIZE_LIMIT
+ m_size -= result->m_size;
+ #endif
*m = NULL;
- delete result;
+ delete(result);
}
}
- if (*n != NULL)
- delete Operation(*n, op);
}
- set<ParanoidNumber*> s;
- if (!SanityCheck(s))
+
+
+
+ for (auto n : next)
+ {
+ if (n != NULL)
+ {
+ #ifdef PARANOID_SIZE_LIMIT
+ if (Operation(n, op) == n)
+ {
+ m_size -= n->m_size;
+ delete n;
+ }
+ #else
+ delete(Operation(n, op));
+ #endif
+ }
+ }
+
+ if (op == MULTIPLY || op == DIVIDE)
{
- Error("Simplify broke Sanity");
+ swap(m_next[ADD], hold[0]);
+ swap(m_next[SUBTRACT], hold[1]);
}
+
+ set<ParanoidNumber*> s;
+ //if (!SanityCheck(s))
+ //{
+ // Error("Simplify broke Sanity");
+ //}
return (next.size() > m_next[op].size());
}
ParanoidNumber::digit_t ParanoidNumber::Digit() const
{
- if (!SanityCheck())
- {
- Fatal("Blargh");
- }
- //if (!isnan(m_cached_result))
- // return m_cached_result;
-
+
// Get around the absurd requirement that const correctness be observed.
- digit_t result;// = ((ParanoidNumber*)(this))->m_cached_result;
+ #ifdef PARANOID_CACHE_RESULTS
+ if (m_cache_valid) // le sigh ambiguous function compiler warnings
+ return m_cached_result;
+
+ digit_t & result = ((ParanoidNumber*)(this))->m_cached_result;
+
+ #else
+ digit_t result;
+ #endif
result = m_value;
for (auto mul : m_next[MULTIPLY])
{
result += add->Digit();
for (auto sub : m_next[SUBTRACT])
result -= sub->Digit();
+
+ #ifdef PARANOID_CACHE_RESULTS
+ ((ParanoidNumber*)(this))->m_cache_valid = true;
+ #endif
return result;
}
{
if (!div->SanityCheck(visited))
return false;
+ if (div->Digit() == 0)
+ {
+ Error("Divide by zero");
+ return false;
+ }
}
return true;
}
+void ParanoidNumber::Negate()
+{
+ swap(m_next[ADD], m_next[SUBTRACT]);
+ m_value = -m_value;
+ #ifdef PARANOID_CACHE_RESULTS
+ m_cached_result = -m_cached_result;
+ #endif
+}
+
+#ifdef PARANOID_USE_ARENA
+
+void * ParanoidNumber::operator new(size_t s)
+{
+ return g_arena.allocate(s);
+}
+
+void ParanoidNumber::operator delete(void * p)
+{
+ g_arena.deallocate(p);
+}
+
+ParanoidNumber::Arena::Arena(int64_t block_size) : m_block_size(block_size), m_spare(NULL)
+{
+ m_blocks.push_back({malloc(block_size*sizeof(ParanoidNumber)),0});
+}
+
+ParanoidNumber::Arena::~Arena()
+{
+ for (auto block : m_blocks)
+ {
+ free(block.memory);
+ }
+ m_blocks.clear();
+}
+
+void * ParanoidNumber::Arena::allocate(size_t s)
+{
+ if (m_spare != NULL)
+ {
+ void * result = m_spare;
+ m_spare = NULL;
+ return result;
+ }
+
+ Block & b = m_blocks.back();
+ void * result = (ParanoidNumber*)(b.memory) + (b.used++);
+ if (b.used >= m_block_size)
+ {
+ m_block_size *= 2;
+ Debug("Add block of size %d", m_block_size);
+ m_blocks.push_back({malloc(m_block_size*sizeof(ParanoidNumber)), 0});
+ }
+ return result;
+}
+
+void ParanoidNumber::Arena::deallocate(void * p)
+{
+ m_spare = p;
+}
+#endif //PARANOID_USE_ARENA
+
}