Arbint class implemented

Seems to not explode, at least, when it only has one digit...

diff --git a/src/arbint.cpp b/src/arbint.cpp
index 4f8aff2..3a1757b 100644 (file)
--- a/src/arbint.cpp
+++ b/src/arbint.cpp
@@ -1,3 +1,12 @@
+/**
+ * @file arbint.cpp
+ * @brief Arbitrary sized integer definitions
+ * @see arbint.h
+ * @see add_digits_asm.s
+ * @see sub_digits_asm.s
+ * @see mul_digits_asm.s
+ */
+
 #include "arbint.h"
 #include <algorithm>
 #include <cstring>
@@ -15,7 +24,7 @@ namespace IPDF
 
 Arbint::Arbint(digit_t i) : m_digits(1), m_sign(i < 0)
 {
-       m_digits[0] = i;
+       m_digits[0] = llabs(i);
 }
 
 Arbint::Arbint(unsigned n, digit_t d0, ...) : m_digits(n), m_sign(false)
@@ -31,10 +40,14 @@ Arbint::Arbint(unsigned n, digit_t d0, ...) : m_digits(n), m_sign(false)
        va_end(ap);
 }
 
-Arbint::Arbint(const Arbint & cpy) : m_digits(cpy.m_digits.size()), m_sign(cpy.m_sign)
+Arbint::Arbint(const Arbint & cpy) : m_digits(cpy.m_digits), m_sign(cpy.m_sign)
+{
+       
+}
+
+Arbint::Arbint(const vector<digit_t> & digits) : m_digits(digits), m_sign(false)
 {
-       memcpy(m_digits.data(), cpy.m_digits.data(), 
-               sizeof(digit_t)*m_digits.size());
+       
 }
 
 Arbint & Arbint::operator=(const Arbint & cpy)
@@ -66,6 +79,47 @@ unsigned Arbint::Shrink()
        return result;
 }
 
+Arbint & Arbint::operator*=(const Arbint & mul)
+{
+       vector<digit_t> new_digits(m_digits.size(), 0L);
+       new_digits.reserve(new_digits.size()+mul.m_digits.size());
+       for (unsigned i = 0; i < mul.m_digits.size(); ++i)
+       {
+               vector<digit_t> step(m_digits.size()+i, 0L);
+               memcpy(step.data()+i, m_digits.data(), sizeof(digit_t)*m_digits.size());
+               
+               digit_t overflow = mul_digits((digit_t*)step.data()+i, mul.m_digits[i], m_digits.size());
+               if (overflow != 0L)
+               {
+                       step.push_back(overflow);
+               }
+               new_digits.resize(max(new_digits.size(), step.size()), 0L);
+               digit_t carry = add_digits((digit_t*)new_digits.data(), step.data(), step.size());
+               if (carry != 0L)
+               {
+                       new_digits.push_back(carry);
+               }
+       }
+       
+       m_digits.swap(new_digits);
+       m_sign = !(m_sign == mul.m_sign);
+       return *this;
+}
+
+void Arbint::Division(const Arbint & div, Arbint & result, Arbint & remainder) const
+{
+       //TODO: Optimise?
+       remainder = *this;
+       result = 0L;
+       while ((remainder -= div) > 0L)
+       {
+               //Debug("Remainder %c%s", remainder.SignChar(), remainder.DigitStr().c_str());
+               //Debug("Result %c%s + 1", result.SignChar(), result.DigitStr().c_str());
+               result += 1;
+       }
+       remainder += div;
+}
+
 Arbint & Arbint::operator+=(const Arbint & add)
 {
        if (m_sign == add.m_sign)
@@ -130,7 +184,6 @@ Arbint & Arbint::SubBasic(const Arbint & sub)
                        m_digits[i] = -m_digits[i];
        }
        return *this;
-       return *this;
 }
 
 
@@ -153,6 +206,15 @@ string Arbint::Str(const string & base) const
        return s;
 }
 
+bool Arbint::IsZero() const
+{
+       for (unsigned i = m_digits.size()-1; i > 0; --i)
+       {
+               if (m_digits[i] != 0L) return false;
+       }
+       return (m_digits[0] == 0L);
+}
+
 bool Arbint::operator==(const Arbint & equ) const
 {
        if (m_sign != equ.m_sign) return false;
@@ -164,7 +226,7 @@ bool Arbint::operator==(const Arbint & equ) const
                larger = this;
        }
        
-       if (memcmp(m_digits.data(), equ.m_digits.data(), min_size) != 0)
+       if (memcmp(m_digits.data(), equ.m_digits.data(), sizeof(digit_t)*min_size) != 0)
                return false;
        
        for (unsigned i = min_size; i < larger->m_digits.size(); ++i)
@@ -175,10 +237,17 @@ bool Arbint::operator==(const Arbint & equ) const
        return true;
 }
 
+bool Arbint::operator<(const Arbint & less) const
+{
+       Arbint cpy(*this);
+       cpy -= less;
+       return (cpy.m_sign && !cpy.IsZero());
+}
+
 string Arbint::DigitStr() const
 {
        stringstream ss("");
-       //ss << std::hex << std::setfill('0');
+       ss << std::hex << std::setfill('0');
        for (unsigned i = 0; i < m_digits.size(); ++i)
        {
                if (i != 0) ss << ',';

diff --git a/src/arbint.h b/src/arbint.h
index 1507ba7..f137796 100644 (file)
--- a/src/arbint.h
+++ b/src/arbint.h
@@ -1,3 +1,9 @@
+/**
+ * @file arbint.h
+ * @brief Arbitrary sized integer declarations
+ * @see arbint.cpp
+ */
+ 
 #ifndef _ARBINT_H
 #define _ARBINT_H
 
@@ -11,11 +17,16 @@ namespace IPDF
                        typedef int64_t digit_t;
                
                        Arbint(digit_t i);
+                       Arbint(const std::vector<digit_t> & digits);
                        Arbint(unsigned n, digit_t d0, ...);
                        Arbint(const std::string & str, const std::string & base="0123456789");
                        ~Arbint() {}
                        Arbint(const Arbint & cpy);
                        
+                       digit_t AsDigit() const 
+                       {
+                               return (m_sign) ? -m_digits[0] : m_digits[0];
+                       }
                        
                        inline bool Sign() const {return m_sign;}
                        inline char SignChar() const {return (m_sign) ? '-' : '+';}
@@ -30,10 +41,8 @@ namespace IPDF
                        Arbint & operator=(const Arbint & equ);
                        Arbint & operator+=(const Arbint & add);
                        Arbint & operator-=(const Arbint & sub);
-       
-                       
-                       bool operator==(const Arbint & equ) const;
-                       
+                       Arbint & operator*=(const Arbint & mul);
+                       void Division(const Arbint & div, Arbint & result, Arbint & modulo) const;
                        
                        inline Arbint operator+(const Arbint & add) const 
                        {
@@ -46,12 +55,60 @@ namespace IPDF
                                Arbint a(*this);
                                a -= add;
                                return a;
-                       }       
+                       }
+                       
+                       inline Arbint operator*(const Arbint & mul) const
+                       {
+                               Arbint a(*this);
+                               a *= mul;
+                               return a;
+                       }
+                       
+                       inline Arbint & operator/=(const Arbint & div)
+                       {
+                               Arbint result(0L);
+                               Arbint remainder(0L);
+                               this->Division(div, result, remainder);
+                               this->operator=(result);
+                               return *this;
+                       }
+                       inline Arbint operator/(const Arbint & div)
+                       {
+                               Arbint cpy(*this);
+                               cpy /= div;
+                               return cpy;
+                       }
+                       inline Arbint operator%(const Arbint & div)
+                       {
+                               Arbint result(0L);
+                               Arbint remainder(0L);
+                               this->Division(div, result, remainder);
+                               return remainder;
+                       }
+                       
+                       bool operator==(const Arbint & equ) const;
+                       bool operator<(const Arbint & less) const;
+
                        inline bool operator!=(const Arbint & equ) const 
                        {
-                               return !this->operator==(equ);
+                               return !(this->operator==(equ));
+                       }
+                       inline bool operator<=(const Arbint & leq) const 
+                       {
+                               return (this->operator==(leq) || this->operator<(leq));
+                       }
+                       
+                       inline bool operator>=(const Arbint & leq) const 
+                       {
+                               return (this->operator==(leq) || this->operator<(leq));
+                       }
+                       inline bool operator>(const Arbint & grea) const
+                       {
+                               return !(this->operator<=(grea));
                        }
                        
+                       bool IsZero() const;
+                       
                        unsigned Shrink();
                private:                
                                
@@ -61,9 +118,6 @@ namespace IPDF
                        std::vector<digit_t> m_digits;
                        bool m_sign;
                        void Zero();
-
-                       
-                       
                        
        };      
 
@@ -72,6 +126,7 @@ extern "C"
        typedef int64_t digit_t;
        digit_t add_digits(digit_t * dst, digit_t * add, digit_t size);
        digit_t sub_digits(digit_t * dst, digit_t * add, digit_t size);
+       digit_t mul_digits(digit_t * dst, digit_t mul, digit_t size);
 }
 
 }

diff --git a/src/tests/arb.cpp b/src/tests/arb.cpp
index 354c337..b6e58cb 100644 (file)
--- a/src/tests/arb.cpp
+++ b/src/tests/arb.cpp
@@ -1,25 +1,54 @@
 #include <cstdlib>
 #include <cstdio>
 #include <iostream>
-
+#include <cassert>
 #include "arbint.h"
 
 using namespace std;
 using namespace IPDF;
 
+#define TEST_CASES 100
+
+
 int main(int argc, char ** argv)
 {
-       int64_t test[] = {12L, 5L};
-       test[1] = 0xE000000000000000;
-       int64_t size = sizeof(test)/sizeof(int64_t);
        
-       int64_t mul = 2L;
-       
-       int64_t overflow = mul_digits(test, mul, size);
-       
-       for (int64_t i = 0; i < size; ++i)
+
+       for (unsigned i = 0; i < TEST_CASES; ++i)
        {
-               printf("digit[%li] = %.16lx\n", i, test[i]);
+               Arbint::digit_t a = rand();
+               Arbint::digit_t b = rand();
+               
+               Arbint arb_a(a);
+               Arbint arb_b(b);
+               
+               Debug("Test %u: a = %li, b = %li", i, a, b);
+               
+               Debug("a < b = %d", a < b);
+               Debug("Arb a<b = %d", arb_a < arb_b);
+               assert((arb_a < arb_b) == (a < b));
+               
+               Debug("a > b = %d", a > b);
+               Debug("Arb a>b = %d", arb_a > arb_b);
+               assert((arb_a > arb_b) == (a > b));
+               
+               Debug("a + b = %.16lx", a+b);
+               Debug("Arb a+b = %s", (arb_a+arb_b).DigitStr().c_str());
+               assert((arb_a+arb_b).AsDigit() == a + b);
+               
+               Debug("a - b = %li %.16lx", (a-b), (a-b));
+               Debug("Arb a-b = %s %.16lx", (arb_a-arb_b).DigitStr().c_str(), (arb_a-arb_b).AsDigit());
+               assert((arb_a-arb_b).AsDigit() == a - b);
+               
+               Debug("a * b = %.16lx", a*b);
+               Debug("Arb a*b = %s", (arb_a*arb_b).DigitStr().c_str());
+               assert((arb_a*arb_b).AsDigit() == a * b);
+               
+               Debug("a / b = %.16lx", a/b);
+               Debug("Arb a/b = %s", (arb_a/arb_b).DigitStr().c_str());
+               assert((arb_a/arb_b).AsDigit() == a / b);
+               assert((arb_a%arb_b).AsDigit() == a % b);
        }
-       printf("Overflow is %.16lx\n", overflow);
+       printf("All tests successful!\n");
+       return 0;
 }