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 / blobdiff
UCC git Repository :: git.ucc.asn.au