Slightly better results
authorSam Moore <matches@ucc.asn.au>
Tue, 16 Sep 2014 10:43:39 +0000 (18:43 +0800)
committerSam Moore <matches@ucc.asn.au>
Tue, 16 Sep 2014 10:43:39 +0000 (18:43 +0800)
Assuming we can trust Wolfram's Giant Ego, err, I mean Wolfram Alpha, to give exact results,
it is generally giving a better result than doubles.

Try simplifying the "a/b + c/d" cases next?

Also at the moment "(a + b)*c" does not simplify to "a*c + b*c" even if
a*c is exact.

Have to be careful because sometimes making the representation more exact
ends up making the conversion back to double have a bigger error.

src/paranoidnumber.cpp
src/paranoidnumber.h
src/tests/paranoidtester.cpp

index 4769c46..b45c71e 100644 (file)
@@ -22,7 +22,7 @@ ParanoidNumber::~ParanoidNumber()
        }
 }
 
-ParanoidNumber::ParanoidNumber(const char * str) : m_value(0)
+ParanoidNumber::ParanoidNumber(const char * str) : m_value(0), m_cached_result(0)
 {
        Construct();
        int dp = 0;
@@ -55,6 +55,7 @@ ParanoidNumber::ParanoidNumber(const char * str) : m_value(0)
 ParanoidNumber & ParanoidNumber::operator=(const ParanoidNumber & a)
 {
        m_value = a.m_value;
+       m_cached_result = a.m_cached_result;
        for (int i = 0; i < NOP; ++i)
        {
                for (unsigned j = 0; j < m_next[i].size() && j < a.m_next[i].size(); ++j)
@@ -198,6 +199,8 @@ bool TrustingOp<int8_t>(int8_t & a, const int8_t & b, Optype op)
 ParanoidNumber & ParanoidNumber::operator+=(const ParanoidNumber & a)
 {
        delete Operation(new ParanoidNumber(a), ADD);
+       Simplify(ADD);
+       Simplify(SUBTRACT);
        return *this;
 }
 
@@ -205,6 +208,8 @@ ParanoidNumber & ParanoidNumber::operator+=(const ParanoidNumber & a)
 ParanoidNumber & ParanoidNumber::operator-=(const ParanoidNumber & a)
 {
        delete Operation(new ParanoidNumber(a), SUBTRACT);
+       //Simplify(SUBTRACT);
+       //Simplify(ADD);
        return *this;
 }
 
@@ -224,7 +229,7 @@ ParanoidNumber & ParanoidNumber::operator/=(const ParanoidNumber & a)
 // a + b
 ParanoidNumber * ParanoidNumber::OperationTerm(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point, Optype * merge_op)
 {
-                       
+       m_cached_result = nan("");
        if (Floating() && m_value == 0) // 0 + b = b
        {
                m_value = b->m_value;
@@ -246,7 +251,8 @@ ParanoidNumber * ParanoidNumber::OperationTerm(ParanoidNumber * b, Optype op, Pa
                
 
        
-       if (NoFactors() && b->NoFactors())
+       if ((NoFactors() && b->NoFactors())
+               || (GetFactors() == b->GetFactors()))
        {
                if (ParanoidOp<digit_t>(m_value, b->m_value, op))
                {
@@ -265,7 +271,6 @@ ParanoidNumber * ParanoidNumber::OperationTerm(ParanoidNumber * b, Optype op, Pa
                }
        }
 
-
        
        
        bool parent = (merge_point == NULL);
@@ -309,7 +314,8 @@ ParanoidNumber * ParanoidNumber::OperationTerm(ParanoidNumber * b, Optype op, Pa
        
        if (parent)
        {
-               merge->m_next[*merge_op].push_back(b);
+               //merge->m_next[*merge_op].push_back(b);
+               m_next[op].push_back(b);
        }
        else
        {
@@ -324,7 +330,7 @@ ParanoidNumber * ParanoidNumber::OperationTerm(ParanoidNumber * b, Optype op, Pa
 
 ParanoidNumber * ParanoidNumber::OperationFactor(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point, Optype * merge_op)
 {
-       
+       m_cached_result = nan("");
        if (Floating() && m_value == 0)
        {
                return b;
@@ -344,6 +350,8 @@ ParanoidNumber * ParanoidNumber::OperationFactor(ParanoidNumber * b, Optype op,
        }
        if (b->Floating() && b->m_value == 1)
                return b;
+       
+
                
        if (NoTerms() && b->NoTerms())
        {
@@ -360,6 +368,9 @@ ParanoidNumber * ParanoidNumber::OperationFactor(ParanoidNumber * b, Optype op,
                                
                        b->m_next[DIVIDE].clear();
                        b->m_next[MULTIPLY].clear();
+                       
+                       
+                       
                        return b;               
                }
        }
@@ -477,16 +488,63 @@ bool ParanoidNumber::Simplify(Optype op)
        swap(m_next[op], next);
        for (auto n : next)
        {
-               ParanoidNumber * result = Operation(n, op);
-               if (result != NULL)
-                       delete result;
-               else
-                       m_next[op].push_back(n);
+               delete Operation(n, op);
        }
        return (next.size() > m_next[op].size());
 }
 
+bool ParanoidNumber::FullSimplify()
+{
+       bool result = false;
+       result |= Simplify(MULTIPLY);
+       result |= Simplify(DIVIDE);
+       result |= Simplify(ADD);
+       result |= Simplify(SUBTRACT);
+       return result;
+}
+
+
+ParanoidNumber::digit_t ParanoidNumber::Digit()
+{
+       if (!isnan(m_cached_result))
+               return m_cached_result;
+       m_cached_result = m_value;
+       for (auto mul : m_next[MULTIPLY])
+       {
+               m_cached_result *= mul->Digit();
+       }
+       for (auto div : m_next[DIVIDE])
+       {
+               m_cached_result /= div->Digit();
+       }
+       for (auto add : m_next[ADD])
+               m_cached_result += add->Digit();
+       for (auto sub : m_next[SUBTRACT])
+               m_cached_result -= sub->Digit();
+       return m_cached_result;
+               
+}
+
+ParanoidNumber::digit_t ParanoidNumber::GetFactors()
+{
+       digit_t value = 1;
+       for (auto mul : m_next[MULTIPLY])
+               value *= mul->Digit();
+       for (auto div : m_next[DIVIDE])
+               value /= div->Digit();
+       return value;
+}
+
 
+ParanoidNumber::digit_t ParanoidNumber::GetTerms()
+{
+       digit_t value = 0;
+       for (auto add : m_next[ADD])
+               value += add->Digit();
+       for (auto sub : m_next[SUBTRACT])
+               value -= sub->Digit();
+       return value;
+}
 
 
 }
index e88cfe7..9e63a23 100644 (file)
@@ -71,12 +71,12 @@ namespace IPDF
                public:
                        typedef PARANOID_DIGIT_T digit_t;
 
-                       ParanoidNumber(digit_t value=0) : m_value(value)
+                       ParanoidNumber(digit_t value=0) : m_value(value), m_cached_result(value)
                        {
                                Construct();
                        }
                        
-                       ParanoidNumber(const ParanoidNumber & cpy) : m_value(cpy.m_value)
+                       ParanoidNumber(const ParanoidNumber & cpy) : m_value(cpy.m_value), m_cached_result(cpy.m_cached_result)
                        {
                                Construct();
                                for (int i = 0; i < NOP; ++i)
@@ -98,9 +98,12 @@ namespace IPDF
                        
                        
                        template <class T> T Convert() const;
+                       digit_t GetFactors();
+                       digit_t GetTerms();
+               
 
-                       double ToDouble() const {return Convert<double>();}
-                       digit_t Digit() const {return Convert<digit_t>();}
+                       double ToDouble() {return (double)Digit();}
+                       digit_t Digit();
                        
                        bool Floating() const 
                        {
@@ -122,14 +125,14 @@ namespace IPDF
                        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
                        {
@@ -176,7 +179,7 @@ namespace IPDF
                                return copy;
                        }
 
-               
+
                        static int64_t Paranoia() {return g_count;}
                        
                        std::string PStr() const;
@@ -191,29 +194,36 @@ namespace IPDF
                        digit_t m_value;
                        Optype m_op;
                        std::vector<ParanoidNumber*> m_next[4];
-                       
-                       int m_size;
+                       digit_t m_cached_result;
+                       bool m_cache_valid;
        };
+       
+
+
 
 template <class T>
 T ParanoidNumber::Convert() const
 {
+       if (!isnan(m_cached_result))
+               return (T)m_cached_result;
        T value(m_value);
        for (auto mul : m_next[MULTIPLY])
        {
-               value *= mul->Digit();
+               value *= mul->Convert<T>();
        }
        for (auto div : m_next[DIVIDE])
        {
-               value /= div->Digit();
+               value /= div->Convert<T>();
        }
        for (auto add : m_next[ADD])
-               value += add->Digit();
+               value += add->Convert<T>();
        for (auto sub : m_next[SUBTRACT])
-               value -= sub->Digit();
+               value -= sub->Convert<T>();
        return value;
 }
 
+
+
 }
 
 #endif //_PARANOIDNUMBER_H
index 1d4f26a..47969b9 100644 (file)
@@ -148,7 +148,7 @@ void TestMulDivIntegers(int max=50)
 void TestRandomisedOps(int test_cases = 1000, int ops_per_case = 1, int max_digits = 4)
 {
        Debug("Test %i*%i randomised ops (max digits = %i)", test_cases, ops_per_case, max_digits);
-       long double eps = 1e-6; //* (1e4*ops_per_case);
+       long double eps = 1e-2; //* (1e4*ops_per_case);
        for (int i = 0; i < test_cases; ++i)
        {
                string s = RandomNumberAsString(max_digits);

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