From d2a8386f675fc01216c29e96d35518789b25965b Mon Sep 17 00:00:00 2001 From: Sam Moore Date: Mon, 7 Jul 2014 09:49:20 +0800 Subject: [PATCH] Arbint subtraction/addition deal with borrow/carry correctly, maybe Eventually they will be right. This still doesn't fix the wierd bezier bug or the growing digits really fast (exponential?). I suspect the former is related to pow(Rational, Rational) and the latter probably makes sense if you do the theory (considering how fast Rational overflowed). --- src/arbint.cpp | 64 ++++++++++++++++++++----------------------- src/main.cpp | 5 +--- src/tests/realops.cpp | 2 +- 3 files changed, 31 insertions(+), 40 deletions(-) diff --git a/src/arbint.cpp b/src/arbint.cpp index 12cf18d..df6da8d 100644 --- a/src/arbint.cpp +++ b/src/arbint.cpp @@ -203,19 +203,28 @@ Arbint & Arbint::operator-=(const Arbint & sub) Arbint & Arbint::AddBasic(const Arbint & add) { + // Add any leading zeros to this number while (m_digits.size() < add.m_digits.size()) { - - Debug("Size is %u, add's size is %u", m_digits.size(), add.m_digits.size()); GrowDigit(0L); } //m_digits.resize(add.m_digits.size()+1,0L); digit_t carry = add_digits((digit_t*)m_digits.data(), (digit_t*)add.m_digits.data(), add.m_digits.size()); + + // This number had more digits but there is a carry left over + if (carry != 0L && m_digits.size() > add.m_digits.size()) + { + vector carry_digits(m_digits.size() - add.m_digits.size(), 0L); + carry_digits[0] = carry; + carry = add_digits((digit_t*)m_digits.data()+add.m_digits.size(), + (digit_t*)carry_digits.data(), m_digits.size()-add.m_digits.size()); + } + + // There is still a carry left over if (carry != 0L) { - Debug("Grow carry %lu", carry); GrowDigit(carry); } Shrink(); @@ -224,51 +233,36 @@ Arbint & Arbint::AddBasic(const Arbint & add) Arbint & Arbint::SubBasic(const Arbint & sub) { - bool fith = false; + // Add leading zeros while (sub.m_digits.size() > m_digits.size()) { - fith = false; GrowDigit(0L); } - if (fith) - { - Debug("START sub was %c%s, I am %c%s", SignChar(), sub.DigitStr().c_str(), SignChar(), DigitStr().c_str()); - } + // Do subtraction on digits digit_t borrow = sub_digits((digit_t*)m_digits.data(), (digit_t*)sub.m_digits.data(), sub.m_digits.size()); - - if (fith) + + // This number had more digits but there is a borrow left over + if (borrow != 0L && m_digits.size() > sub.m_digits.size()) { - Debug("SUB_DIGITS -> sub was %c%s, I am %c%s, borrow is %lu", SignChar(), sub.DigitStr().c_str(), SignChar(), DigitStr().c_str(), borrow); + vector borrow_digits(m_digits.size()-sub.m_digits.size(), 0L); + borrow_digits[0] = borrow; + borrow = sub_digits((digit_t*)m_digits.data()+sub.m_digits.size(), + (digit_t*)borrow_digits.data(), m_digits.size()-sub.m_digits.size()); } - - //TODO: Write ASM to do this bit? + + // borrow is still set => number is negative if (borrow != 0L) { - if (sub.m_digits.size() < m_digits.size()) - { - m_digits[m_digits.size()-1] -= borrow; - } - else - { - m_sign = !m_sign; - for (unsigned i = 0; i < m_digits.size(); ++i) - m_digits[i] = (~m_digits[i]); - vector one_digits(m_digits.size(), 0L); - one_digits[0] = 1L; - add_digits((digit_t*)m_digits.data(), (digit_t*)one_digits.data(), m_digits.size()); - } - } - if (fith) - { - Debug("END -> sub was %c%s, I am %c%s", sub.SignChar(), sub.DigitStr().c_str(), SignChar(), DigitStr().c_str()); + m_sign = !m_sign; + for (unsigned i = 0; i < m_digits.size(); ++i) + m_digits[i] = (~m_digits[i]); + vector one_digits(m_digits.size(), 0L); + one_digits[0] = 1L; + add_digits((digit_t*)m_digits.data(), (digit_t*)one_digits.data(), m_digits.size()); } Shrink(); - if (fith) - { - Debug("SHRUNK -> sub was %c%s, I am %c%s", sub.SignChar(), sub.DigitStr().c_str(), SignChar(), DigitStr().c_str()); - } return *this; } diff --git a/src/main.cpp b/src/main.cpp index 194ef04..91e362c 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -97,10 +97,7 @@ int main(int argc, char ** argv) //doc.Add(BEZIER, Rect(0.2+x-4.0, 0.2+y-4.0, 0.6,0.6), (x^y)%3); } } - Debug("Make rect"); - doc.Add(RECT_OUTLINE, Rect(0.1,0.1,0.8,0.8), 0); - Debug("Made rect"); - + doc.Add(BEZIER, Rect(0.1,0.1,0.8,0.8), 0); } Debug("Start!"); Rect bounds(b[0],b[1],b[2],b[3]); diff --git a/src/tests/realops.cpp b/src/tests/realops.cpp index 4ac54ff..83a5241 100644 --- a/src/tests/realops.cpp +++ b/src/tests/realops.cpp @@ -22,7 +22,7 @@ int main(int argc, char ** argv) unsigned failures = 0; for (unsigned i = 0; i < TEST_CASES; ++i) { - Debug("Test %u of %u", i, TEST_CASES); + //Debug("Test %u of %u", i, TEST_CASES); double da = (double)(rand() + 1) / (double)(rand() + 1); double db = (double)(rand() + 1) / (double)(rand() + 1); -- 2.20.1