X-Git-Url: https://git.ucc.asn.au/?a=blobdiff_plain;f=src%2Fparanoidnumber.h;h=9e63a23371b853291d278164b88e922957bf59cb;hb=0f3a7a9d2c6cc19852fae8ed048dcd1089d33250;hp=f767ffa2a65315788be14b6d4a1baf4ba6527b95;hpb=20788af97c06b76040ea2de5ab3ddc683a261365;p=ipdf%2Fcode.git

diff --git a/src/paranoidnumber.h b/src/paranoidnumber.h
index f767ffa..9e63a23 100644
--- a/src/paranoidnumber.h
+++ b/src/paranoidnumber.h
@@ -7,13 +7,31 @@
 #include <string>
 #include "log.h"
 #include <fenv.h>
+#include <vector>
+#include <cmath>
 
-#define PARANOID_DIGIT_T int8_t // we could theoretically replace this with a template
+#define PARANOID_DIGIT_T float // we could theoretically replace this with a template
 								// but let's not do that...
 
 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 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,134 +48,91 @@ 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), m_cached_result(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), m_cached_result(cpy.m_cached_result)
 			{
-				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));
+					for (auto next : cpy.m_next[i])
+						m_next[i].push_back(new ParanoidNumber(*next));
 				}
-				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();}
+			ParanoidNumber(const std::string & str) : ParanoidNumber(str.c_str()) {}
+			
+			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--;
+				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 Head() const {return (m_op == SUBTRACT) ? T(-m_value) : T(m_value);}
-			
+			digit_t GetFactors();
+			digit_t GetTerms();
+		
 
+			double ToDouble() {return (double)Digit();}
+			digit_t Digit();
 			
-			
-			double ToDouble() const {return Convert<double>();}
-			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 
+			{
+				return NoFactors() && NoTerms();
+			}
 			bool Sunken() const {return !Floating();} // I could not resist...
 			
+			bool NoFactors() const {return (m_next[MULTIPLY].size() == 0 && m_next[DIVIDE].size() == 0);}
+			bool NoTerms() const {return (m_next[ADD].size() == 0 && m_next[SUBTRACT].size() == 0);}
+			
 			ParanoidNumber & operator+=(const ParanoidNumber & a);
 			ParanoidNumber & operator-=(const ParanoidNumber & a);
 			ParanoidNumber & operator*=(const ParanoidNumber & a);
 			ParanoidNumber & operator/=(const ParanoidNumber & a);
 			ParanoidNumber & operator=(const ParanoidNumber & a);
 			
+			ParanoidNumber * OperationTerm(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point = NULL, Optype * mop = NULL);
+			ParanoidNumber * OperationFactor(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point = NULL, Optype * mop = NULL);
+			ParanoidNumber * TrivialOp(ParanoidNumber * b, Optype op);
+			ParanoidNumber * Operation(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point = NULL, Optype * mop = NULL);
+			bool Simplify(Optype op);
+			bool FullSimplify();
 			
-			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));}
-			bool operator>=(const ParanoidNumber & a) const {return !(this->operator<(a));}
-			bool operator==(const ParanoidNumber & a) const {return ToDouble() == a.ToDouble();}
-			bool operator!=(const ParanoidNumber & a) const {return !(this->operator==(a));}
+			bool operator<(ParanoidNumber & a) {return ToDouble() < a.ToDouble();}
+			bool operator<=(ParanoidNumber & a) {return this->operator<(a) || this->operator==(a);}
+			bool operator>(ParanoidNumber & a) {return !(this->operator<=(a));}
+			bool operator>=(ParanoidNumber & a) {return !(this->operator<(a));}
+			bool operator==(ParanoidNumber & a) {return ToDouble() == a.ToDouble();}
+			bool operator!=(ParanoidNumber & a) {return !(this->operator==(a));}
 			
 			ParanoidNumber operator+(const ParanoidNumber & a) const
 			{
@@ -185,13 +160,29 @@ namespace IPDF
 			}
 			
 			std::string Str() const;
-			static char OpChar(Optype op) 
+
+			ParanoidNumber * CopyTerms()
 			{
-				static char opch[] = {'+','-','*','/'};
-				return opch[(int)op];
+				ParanoidNumber * copy = new ParanoidNumber(*this);
+				copy->m_value = 0;
+				copy->Simplify(ADD);
+				copy->Simplify(SUBTRACT);
+				return copy;
 			}
-		
+			
+			ParanoidNumber * CopyFactors()
+			{
+				ParanoidNumber * copy = new ParanoidNumber(*this);
+				copy->m_value = 1;
+				copy->Simplify(MULTIPLY);
+				copy->Simplify(DIVIDE);
+				return copy;
+			}
+
+
 			static int64_t Paranoia() {return g_count;}
+			
+			std::string PStr() const;
 		
 		private:
 			static int64_t g_count;
@@ -202,45 +193,37 @@ namespace IPDF
 			
 			digit_t m_value;
 			Optype m_op;
-			ParanoidNumber * m_next_term;
-			ParanoidNumber * m_next_factor;
+			std::vector<ParanoidNumber*> m_next[4];
+			digit_t m_cached_result;
+			bool m_cache_valid;
 	};
+	
+
+
 
 template <class T>
-T ParanoidNumber::AddTerms() const
+T ParanoidNumber::Convert() const
 {
-	T value(0);
-	for (ParanoidNumber * a = m_next_term; a != NULL; a = a->m_next_term)
+	if (!isnan(m_cached_result))
+		return (T)m_cached_result;
+	T value(m_value);
+	for (auto mul : m_next[MULTIPLY])
 	{
-		value += a->Head<T>() * a->MultiplyFactors<T>();
+		value *= mul->Convert<T>();
 	}
-	return value;
-}
-
-template <class T>
-T ParanoidNumber::MultiplyFactors() const
-{
-	T value(1);
-	for (ParanoidNumber * a = m_next_factor; a != NULL; a = a->m_next_factor)
+	for (auto div : m_next[DIVIDE])
 	{
-		if (a->m_op == DIVIDE)
-			value /= (a->Head<T>() + a->AddTerms<T>());	
-		else
-			value *= (a->Head<T>() + a->AddTerms<T>());	
+		value /= div->Convert<T>();
 	}
+	for (auto add : m_next[ADD])
+		value += add->Convert<T>();
+	for (auto sub : m_next[SUBTRACT])
+		value -= sub->Convert<T>();
 	return value;
 }
 
 
 
-template <class T>
-T ParanoidNumber::Convert() const
-{
-	return Head<T>() * MultiplyFactors<T>() + AddTerms<T>();
-}
-
-
-
 }
 
 #endif //_PARANOIDNUMBER_H