From 0f3a7a9d2c6cc19852fae8ed048dcd1089d33250 Mon Sep 17 00:00:00 2001 From: Sam Moore Date: Tue, 16 Sep 2014 18:43:39 +0800 Subject: [PATCH] Slightly better results 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 | 80 +++++++++++++++++++++++++++++++----- src/paranoidnumber.h | 46 +++++++++++++-------- src/tests/paranoidtester.cpp | 2 +- 3 files changed, 98 insertions(+), 30 deletions(-) diff --git a/src/paranoidnumber.cpp b/src/paranoidnumber.cpp index 4769c46..b45c71e 100644 --- a/src/paranoidnumber.cpp +++ b/src/paranoidnumber.cpp @@ -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 & 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(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; +} } diff --git a/src/paranoidnumber.h b/src/paranoidnumber.h index e88cfe7..9e63a23 100644 --- a/src/paranoidnumber.h +++ b/src/paranoidnumber.h @@ -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 T Convert() const; + digit_t GetFactors(); + digit_t GetTerms(); + - double ToDouble() const {return Convert();} - digit_t Digit() const {return Convert();} + 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 m_next[4]; - - int m_size; + digit_t m_cached_result; + bool m_cache_valid; }; + + + template 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(); } for (auto div : m_next[DIVIDE]) { - value /= div->Digit(); + value /= div->Convert(); } for (auto add : m_next[ADD]) - value += add->Digit(); + value += add->Convert(); for (auto sub : m_next[SUBTRACT]) - value -= sub->Digit(); + value -= sub->Convert(); return value; } + + } #endif //_PARANOIDNUMBER_H diff --git a/src/tests/paranoidtester.cpp b/src/tests/paranoidtester.cpp index 1d4f26a..47969b9 100644 --- a/src/tests/paranoidtester.cpp +++ b/src/tests/paranoidtester.cpp @@ -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); -- 2.20.1