Add quadtree back to the Makefile
[ipdf/code.git] / src / arbint.cpp
index ac39942..8af84f9 100644 (file)
@@ -74,13 +74,36 @@ void Arbint::Zero()
 
 unsigned Arbint::Shrink()
 {
+       
        if (m_digits.size() <= 1)
                return 0;
-       unsigned i;
-       for (i = m_digits.size()-1; (i > 0 && m_digits[i] != 0L); --i);
-       unsigned result = m_digits.size() - i;
-       m_digits.resize(i);
-       return result;
+       
+       unsigned shrunk = 0;
+       while (m_digits.size() > 1 && m_digits[m_digits.size()-1] == 0L)
+       {
+               //Debug("Shrink 1");
+               m_digits.pop_back();
+               shrunk++;
+       }
+       return shrunk;
+}
+
+void Arbint::GrowDigit(digit_t new_msd)
+{
+       static unsigned total_grows = 0;
+       static unsigned biggest_arbint = 1;
+       m_digits.push_back(new_msd);
+       total_grows++;
+       if (m_digits.size() > biggest_arbint)
+       {
+               biggest_arbint = m_digits.size();
+               Warn("New biggest Arbint of size %u", m_digits.size());
+       }
+       //Warn("Arbint grows digit (%.16lx), this->m_digits.size() = %u, total grown = %u", new_msd, m_digits.size(), ++total_grows);
+       //if (total_grows++ > 10000)
+       //{
+       //      Fatal("Too many GrowDigit calls!");
+       //}
 }
 
 Arbint & Arbint::operator*=(const Arbint & mul)
@@ -101,12 +124,14 @@ Arbint & Arbint::operator*=(const Arbint & mul)
                digit_t carry = add_digits((digit_t*)new_digits.data(), step.data(), step.size());
                if (carry != 0L)
                {
-                       new_digits.push_back(carry);
+                       Debug("Add carry");
+                       GrowDigit(carry);
                }
        }
        
        m_digits.swap(new_digits);
        m_sign = !(m_sign == mul.m_sign);
+       Shrink();
        return *this;
 }
 
@@ -119,6 +144,15 @@ void Arbint::Division(const Arbint & div, Arbint & result, Arbint & remainder) c
                result = *this;
                return;
        }
+       /* may break things (even more that is)
+       else if (div.m_digits.size() == 1)
+       {
+               result.m_digits.resize(m_digits.size(), 0L);
+               remainder = Arbint(div_digits((digit_t*)&m_digits[0], div.m_digits[0], m_digits.size(), result.m_digits.data()));
+               result.m_sign = !(m_sign == div.m_sign);
+               return;
+       } */
+       
        for (int i = 8*sizeof(digit_t)*m_digits.size(); i >= 0; --i)
        {
                remainder <<= 1;
@@ -133,6 +167,7 @@ void Arbint::Division(const Arbint & div, Arbint & result, Arbint & remainder) c
                }
        }
        result.m_sign = !(m_sign == div.m_sign);
+       result.Shrink();
 }
 
 Arbint & Arbint::operator+=(const Arbint & add)
@@ -155,6 +190,7 @@ Arbint & Arbint::operator+=(const Arbint & add)
                // a + -b == a - b
                SubBasic(add);
        }
+       Shrink();
        return *this;
 }
 
@@ -167,37 +203,66 @@ Arbint & Arbint::operator-=(const Arbint & sub)
 
 Arbint & Arbint::AddBasic(const Arbint & add)
 {
-       if (add.m_digits.size() >= m_digits.size())
+       // Add any leading zeros to this number
+       while (m_digits.size() < add.m_digits.size())
        {
-               m_digits.resize(add.m_digits.size()+1,0L);
+               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)
-               m_digits[m_digits.size()-1] = carry;
-       else if (m_digits.back() == 0L)
-               m_digits.resize(m_digits.size()-1);
+       {
+               GrowDigit(carry);
+       }
+       Shrink();
        return *this;
 }
 
 Arbint & Arbint::SubBasic(const Arbint & sub)
 {
-       if (sub.m_digits.size() >= m_digits.size())
+       // Add leading zeros
+       while (sub.m_digits.size() > m_digits.size())
        {
-               m_digits.resize(sub.m_digits.size(),0L);
+               GrowDigit(0L);
        }
+       
+       // Do subtraction on digits
        digit_t borrow = sub_digits((digit_t*)m_digits.data(), 
                        (digit_t*)sub.m_digits.data(), sub.m_digits.size());
-               
-               
-       //TODO: Write ASM to do this bit?
+
+       // This number had more digits but there is a borrow left over  
+       if (borrow != 0L && m_digits.size() > sub.m_digits.size())
+       {
+               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());
+       }
+       
+       // borrow is still set => number is negative
        if (borrow != 0L)
        {
                m_sign = !m_sign;
                for (unsigned i = 0; i < m_digits.size(); ++i)
-                       m_digits[i] = -m_digits[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();
        return *this;
 }
 
@@ -206,7 +271,16 @@ string Arbint::Str(const string & base) const
 {
        string s("");
        Arbint cpy(*this);
-       
+       unsigned b = base.size();
+       while (cpy > Arbint(0L))
+       {
+               //Debug("cpy is %s", cpy.DigitStr().c_str());
+               unsigned c = (unsigned)(cpy % Arbint(b)).AsDigit();
+               s += base[c];
+               cpy /= Arbint(b);
+       }
+       if (m_sign)
+               s += '-';
        reverse(s.begin(), s.end());
        return s;
 }
@@ -293,6 +367,7 @@ Arbint & Arbint::operator>>=(unsigned amount)
                m_digits[i] |= underflow;
                underflow = next_underflow;
        }
+       Shrink();
        return *this;
 }
 
@@ -301,7 +376,11 @@ Arbint & Arbint::operator<<=(unsigned amount)
        // Shift by whole number of digits
        unsigned whole = amount/(8*sizeof(digit_t));
        unsigned old_size = m_digits.size();
-       m_digits.resize(m_digits.size() + whole);
+       for (unsigned i = 0; i < whole; ++i)
+       {
+               //Debug("i = %u, whole = %u", i, whole);
+               GrowDigit(0L);//m_digits.resize(m_digits.size() + whole);
+       }
        memmove(m_digits.data()+whole, m_digits.data(), sizeof(digit_t)*old_size);
        memset(m_digits.data(), 0L, whole*sizeof(digit_t));
        
@@ -328,7 +407,7 @@ Arbint & Arbint::operator<<=(unsigned amount)
        }
        if (overflow != 0L)
                m_digits.push_back(overflow);
-               
+       Shrink();
        return *this;
 }
 
@@ -356,10 +435,12 @@ void Arbint::BitClear(unsigned i)
 void Arbint::BitSet(unsigned i)
 {
        unsigned digit = i/(8*sizeof(digit_t));
-       if (digit >= m_digits.size())
+       while (m_digits.size() < digit+1)
        {
-               m_digits.resize(digit+1, 0L);
+               //Debug("Grow BitSet Size %u, digit %u", m_digits.size(), digit);
+               GrowDigit(0L);
        }
+               
        i = i % (8*sizeof(digit_t));
        m_digits[digit] |= (1L << i);           
 }

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