From eaebb5a37393bb02c3272d6259d60ce75d197b6f Mon Sep 17 00:00:00 2001 From: Sam Moore Date: Sat, 5 Jul 2014 15:31:02 +0800 Subject: [PATCH] Arbint class implemented Seems to not explode, at least, when it only has one digit... --- src/arbint.cpp | 83 +++++++++++++++++++++++++++++++++++++++++++---- src/arbint.h | 73 ++++++++++++++++++++++++++++++++++++----- src/tests/arb.cpp | 51 ++++++++++++++++++++++------- 3 files changed, 180 insertions(+), 27 deletions(-) diff --git a/src/arbint.cpp b/src/arbint.cpp index 4f8aff2..3a1757b 100644 --- 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 #include @@ -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 & 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 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 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 --- 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 & 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 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 --- a/src/tests/arb.cpp +++ b/src/tests/arb.cpp @@ -1,25 +1,54 @@ #include #include #include - +#include #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", 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; } -- 2.20.1