Arbint subtraction/addition deal with borrow/carry correctly, maybe
authorSam Moore <matches@ucc.asn.au>
Mon, 7 Jul 2014 01:49:20 +0000 (09:49 +0800)
committerSam Moore <matches@ucc.asn.au>
Mon, 7 Jul 2014 01:49:20 +0000 (09:49 +0800)
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<Arbint>, Rational<Arbint>) and the latter probably makes sense if you do the theory (considering how fast Rational<int64_t> overflowed).

src/arbint.cpp
src/main.cpp
src/tests/realops.cpp

index 12cf18d..df6da8d 100644 (file)
@@ -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<digit_t> 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<digit_t> 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<digit_t> 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<digit_t> 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;
 }
 
index 194ef04..91e362c 100644 (file)
@@ -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]);
index 4ac54ff..83a5241 100644 (file)
@@ -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);
                

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