#include <sstream>
#include <fenv.h>
#include "log.h"
+#include <cassert>
#include <iostream>
using namespace std;
{
int64_t ParanoidNumber::g_count = 0;
-ParanoidNumber::ParanoidNumber(const char * str) : m_value(0), m_op(ADD), m_next_term(NULL), m_next_factor(NULL)
+
+ParanoidNumber::~ParanoidNumber()
+{
+ g_count--;
+ for (int i = 0; i < NOP; ++i)
+ delete m_next[i];
+}
+
+ParanoidNumber::ParanoidNumber(const char * str) : m_value(0)
{
+ Construct();
int dp = 0;
int end = 0;
while (str[dp] != '\0' && str[dp] != '.')
}
while (str[end] != '\0')
++end;
-
ParanoidNumber m(1);
for (int i = dp-1; i >= 0; --i)
{
ParanoidNumber b(str[i]-'0');
b*=m;
- //Debug("m is %s", m.Str().c_str());
- //Debug("Add %s", b.Str().c_str());
this->operator+=(b);
- //Debug("Now at %s", Str().c_str());
m*=10;
}
ParanoidNumber n(1);
for (int i = dp+1; i < end; ++i)
{
+ Debug("{%s} /= 10", n.Str().c_str());
n/=10;
+ Debug("{%s}", n.Str().c_str());
ParanoidNumber b(str[i]-'0');
- //Debug("%s * %s", b.Str().c_str(), n.Str().c_str());
b*=n;
- //Debug("b -> %s", b.Str().c_str());
- //Debug("Add %s", b.Str().c_str());
+ Debug("{%s} += {%s}", Str().c_str(), b.Str().c_str());
this->operator+=(b);
- //Debug("Now at %s", Str().c_str());
-
}
- //Debug("Constructed {%s} from %s (%f)", Str().c_str(), str, ToDouble());
}
ParanoidNumber & ParanoidNumber::operator=(const ParanoidNumber & a)
{
- //TODO: Optimise
- delete m_next_term;
- delete m_next_factor;
- m_op = a.m_op;
- if (a.m_next_term != NULL)
- {
- m_next_term = new ParanoidNumber(*(a.m_next_term));
- }
- if (a.m_next_factor != NULL)
- {
- m_next_factor = new ParanoidNumber(*(a.m_next_factor));
- }
- return *this;
-}
-
-ParanoidNumber & ParanoidNumber::operator+=(const ParanoidNumber & a)
-{
- if (m_next_factor == NULL && a.Floating())
+ m_value = a.m_value;
+ for (int i = 0; i < NOP; ++i)
{
- if (ParanoidOp<digit_t>(m_value, a.m_value, ADD))
+ if (a.m_next[i] == NULL)
{
- Simplify();
- return *this;
+ if (m_next[i] != NULL)
+ delete m_next[i];
+ m_next[i] = NULL;
+ continue;
}
- }
- ParanoidNumber * nt = m_next_term;
- ParanoidNumber * nf = m_next_factor;
-
- ParanoidNumber ca(a);
- if (m_next_factor != NULL)
- {
- if (m_next_factor->m_op == MULTIPLY)
- ca /= (*m_next_factor);
- else
- ca *= (*m_next_factor);
- if (ca.Floating())
+ if (m_next[i] != NULL)
{
- m_next_factor = NULL;
- m_next_term = NULL;
- operator+=(ca);
- m_next_factor = nf;
- m_next_term = nt;
- Simplify();
- return *this;
+ m_next[i]->operator=(*(a.m_next[i]));
}
-
- }
-
- m_next_term = new ParanoidNumber(a, ADD);
- ParanoidNumber * t = m_next_term;
- while (t->m_next_term != NULL)
- t = t->m_next_term;
- t->m_next_term = nt;
- //Debug("Simplify {%s} after add", Str().c_str());
- Simplify();
- return *this;
-}
-
-ParanoidNumber & ParanoidNumber::operator-=(const ParanoidNumber & a)
-{
- // this = v + t + (a)
- // -> v + (a) + t
- if (m_next_factor == NULL && a.Floating())
- {
- if (ParanoidOp<digit_t>(m_value, a.m_value, ADD))
- {
- Simplify();
- return *this;
- }
- }
-
- ParanoidNumber * nt = m_next_term;
- ParanoidNumber * nf = m_next_factor;
-
- ParanoidNumber ca(a, SUBTRACT);
- if (m_next_factor != NULL)
- {
- if (m_next_factor->m_op == MULTIPLY)
- ca /= (*m_next_factor);
else
- ca *= (*m_next_factor);
-
- if (ca.Floating())
{
- m_next_factor = NULL;
- m_next_term = NULL;
- operator-=(ca);
- m_next_factor = nf;
- m_next_term = nt;
- Simplify();
- return *this;
+ m_next[i] = new ParanoidNumber(*(a.m_next[i]));
}
-
- }
-
- m_next_term = new ParanoidNumber(a,SUBTRACT);
- ParanoidNumber * t = m_next_term;
- while (t->m_next_term != NULL)
- {
- t->m_op = SUBTRACT;
- t = t->m_next_term;
- }
- t->m_op = SUBTRACT;
- //Debug("next term {%s}", m_next_term->Str().c_str());
- t->m_next_term = nt;
- //Debug("Simplify {%s} after sub", Str().c_str());
- Simplify();
+ }
return *this;
}
-ParanoidNumber & ParanoidNumber::operator*=(const ParanoidNumber & a)
-{
-
- //if (m_value == 0)
- // return *this;
- //Debug("{%s} *= {%s}", Str().c_str(), a.Str().c_str());
- // this = (vf + t) * (a)
- if (a.Floating() && ParanoidOp<digit_t>(m_value, a.m_value, MULTIPLY))
- {
- if (m_next_term != NULL)
- m_next_term->operator*=(a);
- Simplify();
- return *this;
- }
-
- ParanoidNumber * t = this;
- while (t->m_next_factor != NULL)
- t = t->m_next_factor;
- t->m_next_factor = new ParanoidNumber(a, MULTIPLY);
-
- if (m_next_term != NULL)
- m_next_term->operator*=(a);
-
- //Debug("Simplify {%s}", Str().c_str());
- Simplify();
- //Debug("Simplified to {%s}", Str().c_str());
- return *this;
-}
-
-
-ParanoidNumber & ParanoidNumber::operator/=(const ParanoidNumber & a)
-{
-
-
-
- if (a.Floating() && ParanoidOp<digit_t>(m_value, a.m_value, DIVIDE))
- {
- if (m_next_term != NULL)
- m_next_term->operator/=(a);
- Simplify();
- return *this;
- }
-
- //Debug("Called %s /= %s", Str().c_str(), a.Str().c_str());
- // this = (vf + t) * (a)
- ParanoidNumber * t = this;
- while (t->m_next_factor != NULL)
- {
- t = t->m_next_factor;
- }
- t->m_next_factor = new ParanoidNumber(a, DIVIDE);
-
- if (m_next_term != NULL)
- m_next_term->operator/=(a);
-
- Simplify();
- return *this;
-}
-
-
-
-void ParanoidNumber::SimplifyTerms()
-{
-
- //Debug("Simplify {%s}", Str().c_str());
- if (m_next_term == NULL)
- {
- //Debug("No terms!");
- return;
- }
-
- for (ParanoidNumber * a = this; a != NULL; a = a->m_next_term)
- {
- ParanoidNumber * b = a->m_next_term;
- if (a->m_next_factor != NULL && !a->m_next_factor->Floating())
- {
- continue;
- }
-
- ParanoidNumber * bprev = a;
- while (b != NULL)
- {
- //Debug("Simplify factors of %s", b->Str().c_str());
- b->SimplifyFactors();
- if (b->m_next_factor != NULL && !b->m_next_factor->Floating())
- {
- bprev = b;
- b = b->m_next_term;
- continue;
- }
-
- bool simplify = false;
- if (a->m_next_factor != NULL || b->m_next_factor != NULL)
- {
- digit_t aa(a->Head<digit_t>());
- digit_t ab = (a->m_next_factor != NULL) ? a->m_next_factor->Head<digit_t>() : 1;
- digit_t bc(b->Head<digit_t>());
- digit_t bd = (b->m_next_factor != NULL) ? b->m_next_factor->Head<digit_t>() : 1;
- Optype aop = (a->m_next_factor != NULL) ? a->m_next_factor->m_op : DIVIDE;
- Optype cop = (b->m_next_factor != NULL) ? b->m_next_factor->m_op : DIVIDE;
- simplify = CombineTerms<digit_t>(aa, aop, ab, bc, cop, bd);
- if (simplify)
- {
- a->m_value = aa;
- if (a->m_next_factor != NULL)
- a->m_next_factor->m_value = ab;
- else if (ab != 1)
- {
- a->m_next_factor = b->m_next_factor;
- b->m_next_factor = NULL;
- a->m_next_factor->m_value = ab;
- }
- }
- }
- else
- {
- simplify = ParanoidOp<digit_t>(a->m_value, b->Head<digit_t>(), ADD);
- }
- if (simplify)
- {
- bprev->m_next_term = b->m_next_term;
- b->m_next_term = NULL;
- delete b;
- b = bprev;
- }
-
- bprev = b;
- b = b->m_next_term;
- }
- }
-}
-
-void ParanoidNumber::SimplifyFactors()
-{
-
- //Debug("Simplify {%s}", Str().c_str());
- if (m_next_factor == NULL)
- {
- //Debug("No factors!");
- return;
- }
-
- for (ParanoidNumber * a = this; a != NULL; a = a->m_next_factor)
- {
- if ((a->m_op != ADD || a->m_op != SUBTRACT) && a->m_next_term != NULL)
- continue;
-
- ParanoidNumber * bprev = a;
- ParanoidNumber * b = a->m_next_factor;
- while (b != NULL)
- {
- b->SimplifyTerms();
- if (b->m_next_term != NULL)
- {
- bprev = b;
- b = b->m_next_factor;
- continue;
- }
-
- Optype op = b->m_op;
- if (a->m_op == DIVIDE)
- {
- op = (b->m_op == DIVIDE) ? MULTIPLY : DIVIDE;
- }
-
- if (ParanoidOp<digit_t>(a->m_value, b->m_value, op))
- {
-
- bprev->m_next_factor = b->m_next_factor;
- b->m_next_factor = NULL;
- delete b;
- b = bprev;
- }
- bprev = b;
- b = b->m_next_factor;
- }
- }
-}
-
-void ParanoidNumber::Simplify()
-{
- SimplifyFactors();
- SimplifyTerms();
-}
string ParanoidNumber::Str() const
{
string result("");
stringstream s;
s << (double)m_value;
-
- if (m_next_factor != NULL)
+ result += s.str();
+ if (m_next[MULTIPLY] != NULL)
{
- result += s.str();
- result += OpChar(m_next_factor->m_op);
- if (m_next_factor->m_next_term != NULL)
- result += "(" + m_next_factor->Str() + ")";
+ result += "*";
+ if (m_next[MULTIPLY]->m_next[ADD] != NULL || m_next[MULTIPLY]->m_next[SUBTRACT] != NULL)
+ result += "(" + m_next[MULTIPLY]->Str() + ")";
else
- result += m_next_factor->Str();
+ result += m_next[MULTIPLY]->Str();
}
- else
+ if (m_next[DIVIDE] != NULL)
+ {
+ result += "/";
+ if (m_next[DIVIDE]->m_next[ADD] != NULL || m_next[DIVIDE]->m_next[SUBTRACT] != NULL)
+ result += "(" + m_next[DIVIDE]->Str() + ")";
+ else
+ result += m_next[DIVIDE]->Str();
+ }
+
+ if (m_next[ADD] != NULL)
{
- result += s.str();
+ result += "+";
+ if (m_next[ADD]->m_next[MULTIPLY] != NULL || m_next[ADD]->m_next[DIVIDE] != NULL)
+ result += "(" + m_next[ADD]->Str() + ")";
+ else
+ result += m_next[ADD]->Str();
}
-
- if (m_next_term != NULL)
+ if (m_next[SUBTRACT] != NULL)
{
- result += " ";
- result += OpChar(m_next_term->m_op);
- result += m_next_term->Str();
+ result += "-";
+ if (m_next[SUBTRACT]->m_next[MULTIPLY] != NULL || m_next[SUBTRACT]->m_next[DIVIDE] != NULL)
+ result += "(" + m_next[SUBTRACT]->Str() + ")";
+ else
+ result += m_next[SUBTRACT]->Str();
}
+
+
return result;
}
case DIVIDE:
a /= b;
break;
+ case NOP:
+ break;
}
return !fetestexcept(FE_ALL_EXCEPT);
}
case DIVIDE:
a /= b;
break;
+ case NOP:
+ break;
}
return !fetestexcept(FE_ALL_EXCEPT);
}
exact = (b != 0 && sa > b && sa % b == 0);
sa /= b;
break;
+ case NOP:
+ break;
}
a = (int8_t)(sa);
return exact;
}
+
+ParanoidNumber & ParanoidNumber::operator+=(const ParanoidNumber & a)
+{
+ delete Operation(new ParanoidNumber(a), ADD);
+ return *this;
+}
+
+
+ParanoidNumber & ParanoidNumber::operator-=(const ParanoidNumber & a)
+{
+ delete Operation(new ParanoidNumber(a), SUBTRACT);
+ return *this;
+}
+
+ParanoidNumber & ParanoidNumber::operator*=(const ParanoidNumber & a)
+{
+ delete Operation(new ParanoidNumber(a), MULTIPLY);
+ return *this;
+}
+
+
+ParanoidNumber & ParanoidNumber::operator/=(const ParanoidNumber & a)
+{
+ delete Operation(new ParanoidNumber(a), DIVIDE);
+ return *this;
+}
+
+/**
+ * Performs the operation on a with argument b (a += b, a -= b, a *= b, a /= b)
+ * @returns b if b can safely be deleted
+ * @returns NULL if b has been merged with a
+ * append indicates that b should be merged
+ */
+ParanoidNumber * ParanoidNumber::Operation(ParanoidNumber * b, Optype op, ParanoidNumber ** parent)
+{
+ if (b == NULL)
+ return NULL;
+
+ Optype invop = InverseOp(op); // inverse of p
+ ParanoidNumber * append_at = this;
+
+ if (Floating())
+ {
+ if ((op == ADD || op == SUBTRACT) && (m_value == 0))
+ {
+ m_value = b->m_value;
+ for (int i = 0; i < NOP; ++i)
+ {
+ m_next[i] = b->m_next[i];
+ b->m_next[i] = NULL;
+ }
+ return b;
+ }
+ if ((op == MULTIPLY) && (m_value == 1))
+ {
+ m_value = b->m_value;
+ for (int i = 0; i < NOP; ++i)
+ {
+ m_next[i] = b->m_next[i];
+ b->m_next[i] = NULL;
+ }
+ return b;
+ return b;
+ }
+
+ }
+
+ if (b->Floating())
+ {
+ if ((op == ADD || op == SUBTRACT) && (b->m_value == 0))
+ return b;
+ if ((op == MULTIPLY || op == DIVIDE) && (b->m_value == 1))
+ return b;
+ }
+
+ // Operation can be applied directly to the m_value of this and b
+ // ie: op is + or - and this and b have no * or / children
+ // or: op is * or / and this and b have no + or - children
+ if (Pure(op) && (b->Pure(op)))
+ {
+ if (ParanoidOp<digit_t>(m_value, b->m_value, op)) // op applied successfully...
+ {
+ Simplify(op);
+ Simplify(invop);
+ for (int i = 0; i < NOP; ++i) // Try applying b's children to this
+ {
+ delete Operation(b->m_next[i], Optype(i));
+ b->m_next[i] = NULL;
+ }
+ return b; // can delete b
+ }
+ }
+
+ // Try to simplify the cases:
+ // a + b*c == (a/c + b)*c
+ // a + b/c == (a*c + b)/c
+ else if ((op == ADD || op == SUBTRACT) &&
+ (Pure(op) || b->Pure(op)))
+ {
+
+ Debug("Simplify: {%s} %c {%s}", Str().c_str(), OpChar(op), b->Str().c_str());
+ Optype adj[] = {MULTIPLY, DIVIDE};
+ for (int i = 0; i < 2; ++i)
+ {
+
+ Optype f = adj[i];
+ Optype invf = InverseOp(f);
+
+ Debug("Try %c", OpChar(f));
+
+ if (m_next[f] == NULL && b->m_next[f] == NULL)
+ continue;
+
+ ParanoidNumber * tmp_a = new ParanoidNumber(*this);
+ ParanoidNumber * tmp_b = new ParanoidNumber(*b);
+
+
+ ParanoidNumber * af = (tmp_a->m_next[f] != NULL) ? new ParanoidNumber(*(tmp_a->m_next[f])) : NULL;
+ ParanoidNumber * bf = (tmp_b->m_next[f] != NULL) ? new ParanoidNumber(*(tmp_b->m_next[f])) : NULL;
+
+ Debug("{%s} %c {%s}", tmp_a->Str().c_str(), OpChar(op), tmp_b->Str().c_str());
+ Debug("{%s} %c {%s}", tmp_a->Str().c_str(), OpChar(op), tmp_b->Str().c_str());
+ if (tmp_a->Operation(af, invf) != af || tmp_b->Operation(bf, invf) != bf)
+ {
+ delete af;
+ delete bf;
+ delete tmp_a;
+ delete tmp_b;
+ continue;
+ }
+ Debug("{%s} %c {%s}", tmp_a->Str().c_str(), OpChar(op), tmp_b->Str().c_str());
+
+ if (tmp_a->Operation(bf, invf) == bf && tmp_b->Operation(af, invf) == af) // a / c simplifies
+ {
+ if (tmp_a->Operation(tmp_b, op) != NULL) // (a/c) + b simplifies
+ {
+ this->operator=(*tmp_a);
+ if (bf != NULL)
+ delete Operation(bf, f);
+ if (af != NULL)
+ delete Operation(af, f);
+ delete tmp_a;
+ delete tmp_b;
+ return b; // It simplified after all!
+ }
+ else
+ {
+ tmp_b = NULL;
+ delete af;
+ delete bf;
+ }
+ }
+ //Debug("tmp_a : %s", tmp_a->PStr().c_str());
+ //Debug("tmp_b : %s", tmp_b->PStr().c_str());
+ delete tmp_a;
+ delete tmp_b;
+ }
+ }
+
+ // See if operation can be applied to children of this in the same dimension
+ {
+ // (a / b) / c = a / (b*c)
+ // (a * b) / c = a * (b/c)
+ // (a / b) * c = a / (b/c)
+ // (a * b) * c = a * (b*c)
+ // (a + b) + c = a + (b+c)
+ // (a - b) + c = a - (b-c)
+ // (a + b) - c = a + (b-c)
+ // (a - b) - c = a - (b+c)
+ Optype fwd(op);
+ Optype rev(invop);
+ if (op == DIVIDE || op == SUBTRACT)
+ {
+ fwd = invop;
+ rev = op;
+ }
+ // opposite direction first (because ideally things will cancel each other out...)
+ if (m_next[invop] != NULL && m_next[invop]->Operation(b, rev, &append_at) != NULL)
+ return b;
+ // forward direction
+ if (m_next[op] != NULL && m_next[op]->Operation(b, fwd, &append_at) != NULL)
+ return b;
+ }
+
+ // At this point, we have no choice but to merge 'b' with this ParanoidNumber
+
+ // we are a child; the merge operation needs to be applied by the root, so leave
+ if (parent != NULL)
+ {
+ if (m_next[op] == NULL)
+ *parent = this; // last element in list
+ return NULL;
+ }
+
+ append_at->m_next[op] = b; // Merge with b
+
+ // MULTIPLY and DIVIDE operations need to be performed on each term in the ADD/SUBTRACT dimension
+ if (op == DIVIDE || op == MULTIPLY)
+ {
+ // apply the operation to each term
+ if (m_next[ADD] != NULL) delete m_next[ADD]->Operation(new ParanoidNumber(*b), op);
+ if (m_next[SUBTRACT] != NULL) delete m_next[SUBTRACT]->Operation(new ParanoidNumber(*b), op);
+
+ // try and simplify this by adding the terms (you never know...)
+ Simplify(ADD);
+ Simplify(SUBTRACT);
+ }
+ // failed to simplify
+ return NULL;
+}
+
+bool ParanoidNumber::Simplify(Optype op)
+{
+ ParanoidNumber * n = m_next[op];
+ m_next[op] = NULL;
+ if (Operation(n, Optype(op)))
+ {
+ delete n;
+ return true;
+ }
+ else
+ {
+ m_next[op] = n;
+ return false;
+ }
+}
+
+string ParanoidNumber::PStr() const
+{
+ stringstream s;
+ for (int i = 0; i < NOP; ++i)
+ {
+ Optype f = Optype(i);
+ s << this << OpChar(f) << m_next[f] << "\n";
+ }
+ return s.str();
+}
+
+
+
+
+
}
namespace IPDF
{
- typedef enum {ADD, SUBTRACT, MULTIPLY, DIVIDE} Optype;
+ typedef enum {ADD, SUBTRACT, MULTIPLY, DIVIDE, NOP} Optype;
+ inline Optype InverseOp(Optype op)
+ {
+ return ((op == ADD) ? SUBTRACT :
+ (op == SUBTRACT) ? ADD :
+ (op == MULTIPLY) ? DIVIDE :
+ (op == DIVIDE) ? MULTIPLY :
+ (op == NOP) ? NOP : NOP);
+ }
+ inline Optype AdjacentOp(Optype op)
+ {
+ return ((op == ADD) ? MULTIPLY :
+ (op == SUBTRACT) ? DIVIDE :
+ (op == MULTIPLY) ? ADD :
+ (op == DIVIDE) ? SUBTRACT :
+ (op == NOP) ? NOP : NOP);
+ }
+
+ inline char OpChar(int op)
+ {
+ static char opch[] = {'+','-','*','/'};
+ return (op < NOP && op >= 0) ? opch[op] : '?';
+ }
+
/** Performs an operation, returning if the result was exact **/
// NOTE: DIFFERENT to ParanoidOp (although that wraps to this...)
}
return false;
}
-
-
template <> bool TrustingOp<float>(float & a, const float & b, Optype op);
template <> bool TrustingOp<double>(double & a, const double & b, Optype op);
template <> bool TrustingOp<int8_t>(int8_t & a, const int8_t & b, Optype op);
- // Attempt to comine two terms: a*b + c*d or a/b + c/d
- template <class T> bool CombineTerms(T & aa, Optype aop, T & bb, T & cc, Optype cop, T & dd)
- {
- T a(aa); T b(bb); T c(cc); T d(dd);
- if (aop == MULTIPLY && cop == MULTIPLY) // a*b + c*d
- {
-
- if ((ParanoidOp<T>(c, b, DIVIDE) || ParanoidOp(d, b, DIVIDE))
- && TrustingOp<T>(c, d, MULTIPLY) && TrustingOp<T>(a,c,ADD)
- && TrustingOp<T>(a, b, MULTIPLY)) // (a + (cd)/b) * b
- {
- aa = a;
- bb = 1;
- cc = 1;
- dd = 1;
- return true;
- }
- if ((ParanoidOp<T>(a, d, DIVIDE) || ParanoidOp(b, d, DIVIDE))
- && TrustingOp<T>(a, b, MULTIPLY) && TrustingOp<T>(a,c,ADD)
- && TrustingOp<T>(a, d, MULTIPLY)) // ((ab)/d + c)*d
- {
- aa = a;
- bb = 1;
- cc = 1;
- dd = 1;
- return true;
- }
- return false;
- }
- else if (aop == DIVIDE && cop == DIVIDE)
- {
-
-
- if (TrustingOp<T>(a, d, MULTIPLY) && TrustingOp<T>(c, b, MULTIPLY)
- && TrustingOp<T>(a, c, ADD) && TrustingOp<T>(b, d, MULTIPLY))
- {
- cc = 1;
- dd = 1;
- if (ParanoidOp<T>(a, b, DIVIDE))
- {
- aa = a;
- bb = 1;
- return true;
- }
- aa = a;
- bb = b;
- return true;
- }
- return false;
- }
- return false;
- }
-
+ /**
+ * A ParanoidNumber
+ * Idea: Perform regular floating point arithmetic but rearrange operations to only ever use exact results
+ * Memory Usage: O(all of it)
+ * CPU Usage: O(all of it)
+ * Accuracy: O(gives better result for 0.3+0.3+0.3, gives same result for everything else, or worse result)
+ *
+ * The ParanoidNumber basically stores 4 linked lists which can be split into two "dimensions"
+ * 1. Terms to ADD and terms to SUBTRACT
+ * 2. Factors to MULTIPLY and DIVIDE
+ * Because ADD and SUBTRACT are inverse operations and MULTIPLY and DIVIDE are inverse operations
+ * See paranoidnumber.cpp and the ParanoidNumber::Operation function
+ */
class ParanoidNumber
{
public:
typedef PARANOID_DIGIT_T digit_t;
- ParanoidNumber(digit_t value=0, Optype type = ADD) : m_value(value), m_op(type), m_next_term(NULL), m_next_factor(NULL)
+ ParanoidNumber(digit_t value=0) : m_value(value)
{
Construct();
}
- ParanoidNumber(const ParanoidNumber & cpy) : m_value(cpy.m_value), m_op(cpy.m_op), m_next_term(NULL), m_next_factor(NULL)
+ ParanoidNumber(const ParanoidNumber & cpy) : m_value(cpy.m_value)
{
- if (cpy.m_next_term != NULL)
- {
- m_next_term = new ParanoidNumber(*(cpy.m_next_term));
- }
- if (cpy.m_next_factor != NULL)
+ Construct();
+ for (int i = 0; i < NOP; ++i)
{
- m_next_factor = new ParanoidNumber(*(cpy.m_next_factor));
+ if (cpy.m_next[i] != NULL)
+ m_next[i] = new ParanoidNumber(*(cpy.m_next[i]));
}
- Construct();
- }
-
- ParanoidNumber(const ParanoidNumber & cpy, Optype type) : ParanoidNumber(cpy)
- {
- m_op = type;
}
ParanoidNumber(const char * str);
ParanoidNumber(const std::string & str) : ParanoidNumber(str.c_str()) {Construct();}
- virtual ~ParanoidNumber()
+ virtual ~ParanoidNumber();
+
+ inline void Construct()
{
- if (m_next_term != NULL)
- delete m_next_term;
- if (m_next_factor != NULL)
- delete m_next_factor;
- g_count--;
+ for (int i = 0; i < NOP; ++i)
+ m_next[i] = NULL;
+ g_count++;
}
- inline void Construct() {g_count++;}
-
template <class T> T Convert() const;
- template <class T> T AddTerms() const;
- template <class T> T MultiplyFactors() const;
+ template <class T> T AddTerms(T value = T(0)) const;
+ template <class T> T MultiplyFactors(T value = T(1)) const;
template <class T> T Head() const {return (m_op == SUBTRACT) ? T(-m_value) : T(m_value);}
float ToFloat() const {return Convert<float>();}
digit_t Digit() const {return Convert<digit_t>();}
- bool Floating() const {return (m_next_term == NULL && m_next_factor == NULL);}
+ bool Floating() const
+ {
+ for (int i = 0; i < NOP; ++i)
+ {
+ if (m_next[i] != NULL)
+ return false;
+ }
+ return true;
+ }
bool Sunken() const {return !Floating();} // I could not resist...
+ bool Pure(Optype op) const
+ {
+ if (op == ADD || op == SUBTRACT)
+ return (m_next[MULTIPLY] == NULL && m_next[DIVIDE] == NULL);
+ return (m_next[ADD] == NULL && m_next[SUBTRACT] == NULL);
+ }
+
ParanoidNumber & operator+=(const ParanoidNumber & a);
ParanoidNumber & operator-=(const ParanoidNumber & a);
ParanoidNumber & operator*=(const ParanoidNumber & a);
ParanoidNumber & operator=(const ParanoidNumber & a);
+ ParanoidNumber * Operation(ParanoidNumber * b, Optype op, ParanoidNumber ** parent = NULL);
+ bool Simplify(Optype op);
+
+
bool operator<(const ParanoidNumber & a) const {return ToDouble() < a.ToDouble();}
bool operator<=(const ParanoidNumber & a) const {return this->operator<(a) || this->operator==(a);}
bool operator>(const ParanoidNumber & a) const {return !(this->operator<=(a));}
}
std::string Str() const;
- static char OpChar(Optype op)
- {
- static char opch[] = {'+','-','*','/'};
- return opch[(int)op];
- }
+
static int64_t Paranoia() {return g_count;}
+
+ std::string PStr() const;
private:
static int64_t g_count;
digit_t m_value;
Optype m_op;
- ParanoidNumber * m_next_term;
- ParanoidNumber * m_next_factor;
+ ParanoidNumber * m_next[4]; // Next by Operation
};
template <class T>
-T ParanoidNumber::AddTerms() const
+T ParanoidNumber::AddTerms(T value) const
{
- T value(0);
- for (ParanoidNumber * a = m_next_term; a != NULL; a = a->m_next_term)
+ ParanoidNumber * add = m_next[ADD];
+ ParanoidNumber * sub = m_next[SUBTRACT];
+ while (add != NULL && sub != NULL)
{
- value += a->Head<T>() * a->MultiplyFactors<T>();
+ value += add->m_value * add->MultiplyFactors<T>();
+ value -= sub->m_value * sub->MultiplyFactors<T>();
+ add = add->m_next[ADD];
+ sub = sub->m_next[SUBTRACT];
+ }
+ while (add != NULL)
+ {
+ value += add->m_value * add->MultiplyFactors<T>();
+ add = add->m_next[ADD];
+ }
+ while (sub != NULL)
+ {
+ value -= sub->m_value * sub->MultiplyFactors<T>();
+ sub = sub->m_next[SUBTRACT];;
}
return value;
}
template <class T>
-T ParanoidNumber::MultiplyFactors() const
+T ParanoidNumber::MultiplyFactors(T value) const
{
- T value(1);
- for (ParanoidNumber * a = m_next_factor; a != NULL; a = a->m_next_factor)
+ ParanoidNumber * mul = m_next[MULTIPLY];
+ ParanoidNumber * div = m_next[DIVIDE];
+ while (mul != NULL && div != NULL)
+ {
+ value *= (mul->m_value + mul->AddTerms<T>());
+ value /= (div->m_value + div->AddTerms<T>());
+ mul = mul->m_next[MULTIPLY];
+ div = div->m_next[DIVIDE];
+ }
+ while (mul != NULL)
+ {
+ value *= (mul->m_value + mul->AddTerms<T>());
+ mul = mul->m_next[MULTIPLY];
+ }
+ while (div != NULL)
{
- if (a->m_op == DIVIDE)
- value /= (a->Head<T>() + a->AddTerms<T>());
- else
- value *= (a->Head<T>() + a->AddTerms<T>());
+ value /= (div->m_value + div->AddTerms<T>());
+ div = div->m_next[DIVIDE];
}
return value;
}
template <class T>
T ParanoidNumber::Convert() const
{
- return Head<T>() * MultiplyFactors<T>() + AddTerms<T>();
+ return MultiplyFactors<T>(m_value) + AddTerms<T>(0);
}
git.ucc.asn.au / ipdf / code.git / commitdiff
UCC git Repository :: git.ucc.asn.au