Nope.avi
authorSam Moore <matches@ucc.asn.au>
Sat, 13 Sep 2014 18:36:12 +0000 (02:36 +0800)
committerSam Moore <matches@ucc.asn.au>
Sat, 13 Sep 2014 18:36:12 +0000 (02:36 +0800)
src/paranoidnumber.cpp
src/paranoidnumber.h
src/tests/paranoidcalculator.cpp

index 53729a3..49cceaf 100644 (file)
@@ -3,6 +3,7 @@
 #include <sstream>
 #include <fenv.h>
 #include "log.h"
+#include <cassert>
 #include <iostream>
 
 using namespace std;
@@ -10,8 +11,17 @@ namespace IPDF
 {
 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] != '.')
@@ -21,358 +31,94 @@ ParanoidNumber::ParanoidNumber(const char * str) : m_value(0), m_op(ADD), m_next
        }
        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;
 }
 
@@ -394,6 +140,8 @@ bool TrustingOp<float>(float & a, const float & b, Optype op)
                case DIVIDE:
                        a /= b;
                        break;
+               case NOP:
+                       break;
        }
        return !fetestexcept(FE_ALL_EXCEPT);
 }
@@ -416,6 +164,8 @@ bool TrustingOp<double>(double & a, const double & b, Optype op)
                case DIVIDE:
                        a /= b;
                        break;
+               case NOP:
+                       break;
        }
        return !fetestexcept(FE_ALL_EXCEPT);
 }
@@ -443,9 +193,253 @@ bool TrustingOp<int8_t>(int8_t & a, const int8_t & b, Optype op)
                        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();
+}
+
+
+
+
+
 }
index 9005a15..77a8d44 100644 (file)
 
 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...)
@@ -30,112 +53,60 @@ namespace IPDF
                }
                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);}
                        
 
@@ -145,9 +116,24 @@ namespace IPDF
                        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);
@@ -155,6 +141,10 @@ namespace IPDF
                        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));}
@@ -188,13 +178,11 @@ namespace IPDF
                        }
                        
                        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;
@@ -205,31 +193,55 @@ namespace IPDF
                        
                        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;
 }
@@ -239,7 +251,7 @@ T ParanoidNumber::MultiplyFactors() const
 template <class T>
 T ParanoidNumber::Convert() const
 {
-       return Head<T>() * MultiplyFactors<T>() + AddTerms<T>();
+       return MultiplyFactors<T>(m_value) + AddTerms<T>(0);
 }
 
 
index eb30860..b9bd13a 100644 (file)
@@ -41,11 +41,13 @@ int main(int argc, char ** argv)
                        token += c;
                        c = cin.get();
                }
-               Debug("String is %s", token.c_str());
+               //Debug("String is \"%s\"", token.c_str());
                float fb = strtof(token.c_str(), NULL);
                double db = strtod(token.c_str(), NULL);
                ParanoidNumber b(token.c_str());
-               Debug("b is {%s} %lf", b.Str().c_str(), b.ToDouble());
+               Debug("a is {%s} \"%lf\"", a.Str().c_str(), a.ToDouble());
+               Debug("b is {%s} \"%lf\"", b.Str().c_str(), b.ToDouble());
+               Debug("db is %lf", db);
                switch (op)
                {
                        case '+':
@@ -70,12 +72,12 @@ int main(int argc, char ** argv)
                                break;
                }
                        
-               Debug("a is: %s", a.Str().c_str());
-               Debug("a as double: %.40f\n", a.ToDouble());
-               Debug("a as float: %.40f\n", a.ToFloat());
-               Debug("a as int64_t: %ld\n", a.Convert<int64_t>());
-               Debug("floats give: %.40f\n", fa);
-               Debug("double gives: %.40f\n", da);
+               Debug("a is: {%s}", a.Str().c_str());
+               Debug("a as double: %.40lf", a.ToDouble());
+               Debug("a as float: %.40f", a.ToFloat());
+               Debug("a as int64_t: %ld", a.Convert<int64_t>());
+               Debug("floats give: %.40f", fa);
+               Debug("double gives: %.40lf", da);
                
                
        }

UCC git Repository :: git.ucc.asn.au