|
|
Boost-Commit : |
From: zeux_at_[hidden]
Date: 2007-07-22 16:08:58
Author: zeux
Date: 2007-07-22 16:08:56 EDT (Sun, 22 Jul 2007)
New Revision: 7503
URL: http://svn.boost.org/trac/boost/changeset/7503
Log:
Parts of default implementation, vector-based and fixed capacity storage, modified tests (some of them are passed already), fixed documentation, fixed gmp implementation (internal function naming)
Added:
sandbox/SOC/2007/bigint/boost/bigint/bigint_default.hpp
sandbox/SOC/2007/bigint/boost/bigint/bigint_storage_fixed.hpp
sandbox/SOC/2007/bigint/boost/bigint/bigint_storage_vector.hpp
Text files modified:
sandbox/SOC/2007/bigint/boost/bigint/bigint.hpp | 15 ++++--
sandbox/SOC/2007/bigint/boost/bigint/bigint_gmp.hpp | 8 +-
sandbox/SOC/2007/bigint/libs/bigint/index.html | 2
sandbox/SOC/2007/bigint/libs/bigint/test/can_convert_to.cpp | 7 +++
sandbox/SOC/2007/bigint/libs/bigint/test/comparison.cpp | 7 +++
sandbox/SOC/2007/bigint/libs/bigint/test/number_conversion.cpp | 7 +++
sandbox/SOC/2007/bigint/libs/bigint/test/stream.cpp | 7 +++
sandbox/SOC/2007/bigint/libs/bigint/test/string_conversion.cpp | 7 +++
sandbox/SOC/2007/bigint/libs/bigint/test/unary.cpp | 7 +++
sandbox/SOC/2007/bigint/libs/bigint/todo.txt | 84 ++++++++++++++++++++++++++++++++++++++-
10 files changed, 138 insertions(+), 13 deletions(-)
Modified: sandbox/SOC/2007/bigint/boost/bigint/bigint.hpp
==============================================================================
--- sandbox/SOC/2007/bigint/boost/bigint/bigint.hpp (original)
+++ sandbox/SOC/2007/bigint/boost/bigint/bigint.hpp 2007-07-22 16:08:56 EDT (Sun, 22 Jul 2007)
@@ -248,12 +248,12 @@
// conversion to numeric types (including 64 bit)
template <typename T> bool can_convert_to() const
{
- return impl.can_convert_to<T>();
+ return impl.template can_convert_to<T>();
}
template <typename T> T to_number() const
{
- return impl.to_number<T>();
+ return impl.template to_number<T>();
}
// - basic arithmetic operations (addition, subtraction, multiplication, division)
@@ -650,7 +650,6 @@
else return lhs;
}
};
-
} // namespace boost
// Do we have GMP?
@@ -666,8 +665,14 @@
#else
-// The default implementation should be here, but there's none yet
-#error "No default implementation for now"
+#include <boost/bigint/bigint_default.hpp>
+#include <boost/bigint/bigint_storage_vector.hpp>
+
+namespace boost {
+
+typedef bigint_base<detail::bigint_default_implementation<detail::bigint_storage_vector> > bigint;
+
+} // namespace boost
#endif
Added: sandbox/SOC/2007/bigint/boost/bigint/bigint_default.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/boost/bigint/bigint_default.hpp 2007-07-22 16:08:56 EDT (Sun, 22 Jul 2007)
@@ -0,0 +1,790 @@
+/* Boost bigint_default.hpp header file
+ *
+ * Copyright 2007 Arseny Kapoulkine
+ *
+ * Distributed under the Boost Software License, Version 1.0.
+ * (See accompanying file LICENSE_1_0.txt or
+ * copy at http://www.boost.org/LICENSE_1_0.txt)
+ */
+
+#ifndef BOOST_BIGINT_BIGINT_DEFAULT_HPP
+#define BOOST_BIGINT_BIGINT_DEFAULT_HPP
+
+#include <limits>
+
+#include <boost/scoped_array.hpp>
+
+#include <boost/bigint/bigint_util.hpp>
+
+namespace boost { namespace detail {
+ // Default implementation
+ template <template <class> class Storage> struct bigint_default_implementation
+ {
+ typedef unsigned int limb_t;
+ typedef boost::uint64_t limb2_t;
+
+ enum { limb_bit_number = sizeof(limb_t) * 8 };
+ #define limb_max std::numeric_limits<limb_t>::max()
+
+ Storage<limb_t> data;
+ bool negative;
+
+ bigint_default_implementation(): negative(false)
+ {
+ }
+
+ void assign(int number)
+ {
+ assign(static_cast<int64_t>(number));
+ }
+
+ void assign(unsigned int number)
+ {
+ assign(static_cast<uint64_t>(number));
+ }
+
+ void assign(int64_t number)
+ {
+ // number is [-2^32, 2^32-1]
+ // if number == -2^32, it's bit representation is 10...0, -number is 01...1+1 = 10...0 (the same)
+ // converting to uint64_t yields still 10...0, it's exactly 2^32. In other cases we're safe.
+ assign(static_cast<uint64_t>(number >= 0 ? number : -number));
+
+ negative = (number < 0);
+ }
+
+ void assign(uint64_t number)
+ {
+ size_t size = 0;
+
+ if (number != 0)
+ {
+ data.resize(1);
+ data[0] = static_cast<limb_t>(number & limb_max);
+
+ size = 1;
+ }
+
+ if (number > limb_max)
+ {
+ data.resize(64 / limb_bit_number); // we know that limb_bit_number is 2^n
+
+ number >>= limb_bit_number;
+
+ while (number > 0)
+ {
+ data[size++] = static_cast<limb_t>(number & limb_max);
+ number >>= limb_bit_number;
+ }
+ }
+
+ data.resize(size);
+ negative = false;
+ }
+
+ // *this = *this * a + b
+ void _mul_add(limb_t a, limb_t b)
+ {
+ limb_t carry = b;
+
+ for (limb_t* i = data.begin(); i != data.end(); ++i)
+ {
+ limb2_t result = static_cast<limb2_t>(*i) * a + carry;
+
+ *i = static_cast<limb_t>(result & limb_max);
+
+ carry = static_cast<limb_t>(result >> limb_bit_number);
+ }
+
+ if (carry != 0)
+ {
+ data.resize(data.size() + 1);
+ data[data.size()-1] = carry;
+ }
+ }
+
+ template <typename Ch> void _assign_str(const Ch* str, int base)
+ {
+ assert(base >= 2 && base <= 36);
+
+ // skip whitespace
+ while (detail::bigint::isspace(*str)) ++str;
+
+ negative = false;
+
+ if (*str == Ch('-'))
+ {
+ negative = true;
+ ++str;
+ }
+ else if (*str == Ch('+'))
+ {
+ ++str;
+ }
+
+ static const unsigned char digit_value_tab[] =
+ {
+ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+ 0xff, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
+ 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 0xff, 0xff, 0xff, 0xff, 0xff,
+ 0xff, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
+ 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 0xff, 0xff, 0xff, 0xff, 0xff,
+ };
+
+ // skip zeros
+ while (*str == Ch('0')) ++str;
+
+ // is there anything left?
+ if (!*str)
+ {
+ assign(0);
+ return;
+ }
+
+ data.resize(0);
+
+ for (; *str; ++str)
+ {
+ if (!detail::bigint::is_ascii(*str) || digit_value_tab[static_cast<unsigned int>(*str)] >= base)
+ {
+ break;
+ }
+
+ _mul_add(static_cast<limb_t>(base), digit_value_tab[static_cast<unsigned int>(*str)]);
+ }
+ }
+
+ void assign(const char* str, int base)
+ {
+ _assign_str(str, base);
+ }
+
+ void assign(const wchar_t* str, int base)
+ {
+ _assign_str(str, base);
+ }
+
+ void _add_unsigned(const bigint_default_implementation& lhs, const bigint_default_implementation& rhs)
+ {
+ limb_t carry = 0;
+
+ size_t li_size = lhs.data.size();
+ size_t ri_size = rhs.data.size();
+
+ data.resize((std::max)(lhs.data.size(), rhs.data.size()) + 1);
+
+ const limb_t* li = lhs.data.begin();
+ const limb_t* li_end = li + li_size;
+ const limb_t* ri = rhs.data.begin();
+ const limb_t* ri_end = ri + ri_size;
+
+ limb_t* i = data.begin();
+
+ for (; li != li_end && ri != ri_end; ++li, ++ri)
+ {
+ limb2_t result = static_cast<limb2_t>(*li) + *ri + carry;
+
+ *i++ = static_cast<limb_t>(result & limb_max);
+
+ carry = static_cast<limb_t>(result >> limb_bit_number);
+ }
+
+ for (; li != li_end; ++li)
+ {
+ limb2_t result = static_cast<limb2_t>(*li) + carry;
+
+ *i++ = static_cast<limb_t>(result & limb_max);
+
+ carry = static_cast<limb_t>(result >> limb_bit_number);
+ }
+
+ for (; ri != ri_end; ++ri)
+ {
+ limb2_t result = static_cast<limb2_t>(*ri) + carry;
+
+ *i++ = static_cast<limb_t>(result & limb_max);
+
+ carry = static_cast<limb_t>(result >> limb_bit_number);
+ }
+
+ if (carry != 0)
+ {
+ *i = carry;
+ }
+ else
+ {
+ data.resize(data.size() - 1);
+ }
+ }
+
+ void _normalize()
+ {
+ if (data.empty()) return;
+
+ // strip zeroes
+ const limb_t* i = data.end();
+
+ do
+ {
+ --i;
+ }
+ while (i != data.begin() && *i == 0);
+
+ if (i == data.begin() && *i == 0)
+ {
+ data.resize(0);
+ negative = false;
+ }
+ else
+ {
+ data.resize((i - data.begin()) + 1);
+ }
+ }
+
+ bool _sub_unsigned(const bigint_default_implementation& lhs, const bigint_default_implementation& rhs)
+ {
+ limb_t borrow = 0;
+
+ size_t li_size = lhs.data.size();
+ size_t ri_size = rhs.data.size();
+
+ data.resize((std::max)(lhs.data.size(), rhs.data.size()));
+
+ const limb_t* li = lhs.data.begin();
+ const limb_t* li_end = li + li_size;
+ const limb_t* ri = rhs.data.begin();
+ const limb_t* ri_end = ri + ri_size;
+
+ limb_t* i = data.begin();
+
+ for (; li != li_end && ri != ri_end; ++li, ++ri)
+ {
+ limb2_t result = static_cast<limb2_t>(*ri) + borrow;
+
+ if (result > *li)
+ {
+ result = static_cast<limb2_t>(limb_max) + 1 + *li - result;
+ borrow = 1;
+ }
+ else
+ {
+ result = *li - result;
+ borrow = 0;
+ }
+
+ *i++ = static_cast<limb_t>(result & limb_max);
+ }
+
+ for (; li != li_end; ++li)
+ {
+ limb2_t result = borrow;
+
+ if (result > *li)
+ {
+ result = static_cast<limb2_t>(limb_max) + 1 + *li - result;
+ borrow = 1;
+ }
+ else
+ {
+ result = *li - result;
+ borrow = 0;
+ }
+
+ *i++ = static_cast<limb_t>(result & limb_max);
+ }
+
+ for (; ri != ri_end; ++ri)
+ {
+ limb2_t result = static_cast<limb2_t>(*ri) + borrow;
+
+ if (result > 0)
+ {
+ result = static_cast<limb2_t>(limb_max) + 1 - result;
+ borrow = 1;
+ }
+ else
+ {
+ borrow = 0;
+ }
+
+ *i++ = static_cast<limb_t>(result & limb_max);
+ }
+
+ if (borrow != 0)
+ {
+ // we borrowed 2^number of bits in our number - we have to subtract it
+ // for this we need to complement all limbs to 2, and add 1 to the last limb.
+ for (limb_t* j = data.begin(); j != data.end(); ++j)
+ *j = limb_max- *j;
+
+ data[0]++;
+ }
+
+ _normalize();
+
+ return borrow != 0;
+ }
+
+ void add(const bigint_default_implementation& lhs, const bigint_default_implementation& rhs)
+ {
+ if (lhs.negative == rhs.negative) // positive + positive or negative + negative
+ {
+ negative = lhs.negative;
+ _add_unsigned(lhs, rhs);
+ }
+ else if (lhs.negative) // negative + positive
+ {
+ negative = _sub_unsigned(rhs, lhs);
+ }
+ else // positive + negative
+ {
+ negative = _sub_unsigned(lhs, rhs);
+ }
+ }
+
+ void sub(const bigint_default_implementation& lhs, const bigint_default_implementation& rhs)
+ {
+ if (lhs.negative != rhs.negative) // positive - negative or negative - positive
+ {
+ negative = lhs.negative;
+ _add_unsigned(lhs, rhs);
+ }
+ else if (lhs.negative) // negative - negative
+ {
+ negative = _sub_unsigned(rhs, lhs);
+ }
+ else // positive - positive
+ {
+ negative = _sub_unsigned(lhs, rhs);
+ }
+ }
+
+ void mul(const bigint_default_implementation& lhs, const bigint_default_implementation& rhs)
+ {
+ if (lhs.is_zero() || rhs.is_zero())
+ {
+ assign(0);
+ return;
+ }
+
+ if (this == &lhs || this == &rhs)
+ {
+ bigint_default_implementation copy;
+ copy.mul(lhs, rhs);
+ *this = copy;
+ return;
+ }
+
+ data.resize(lhs.data.size() + rhs.data.size());
+ std::fill(data.begin(), data.end(), 0);
+
+ limb_t* i = data.begin();
+
+ for (const limb_t* li = lhs.data.begin(); li != lhs.data.end(); ++li, ++i)
+ {
+ limb_t carry = 0;
+
+ limb_t* ci = i;
+
+ for (const limb_t* ri = rhs.data.begin(); ri != rhs.data.end(); ++ri)
+ {
+ limb2_t result = static_cast<limb2_t>(*li) * *ri + *ci + carry;
+
+ *ci++ = static_cast<limb_t>(result & limb_max);
+
+ carry = static_cast<limb_t>(result >> limb_bit_number);
+ }
+
+ while (carry != 0)
+ {
+ limb2_t result = static_cast<limb2_t>(*ci) + carry;
+
+ *ci++ = static_cast<limb_t>(result & limb_max);
+
+ carry = static_cast<limb_t>(result >> limb_bit_number);
+ }
+ }
+
+ _normalize();
+
+ negative = lhs.negative ? !rhs.negative : rhs.negative;
+ }
+
+ void div(const bigint_default_implementation& lhs, const bigint_default_implementation& rhs)
+ {
+ }
+
+ void mod(const bigint_default_implementation& lhs, const bigint_default_implementation& rhs)
+ {
+ }
+
+ template <bool complement> limb_t _convert(limb_t limb)
+ {
+ return complement ? limb_max - limb : limb;
+ }
+
+ template <bool complement> limb_t _convert_first(limb_t limb)
+ {
+ return complement ? limb_max - limb + 1 : limb;
+ }
+
+ template <bool lhs_neg, bool rhs_neg> void _or_(const bigint_default_implementation& lhs, const bigint_default_implementation& rhs)
+ {
+ const bool neg = lhs_neg || rhs_neg; // sign bit is or-ed
+ negative = neg;
+
+ size_t li_size = lhs.data.size();
+ size_t ri_size = rhs.data.size();
+
+ data.resize((std::max)(lhs.data.size(), rhs.data.size()));
+
+ const limb_t* li = lhs.data.begin();
+ const limb_t* li_end = li + li_size;
+ const limb_t* ri = rhs.data.begin();
+ const limb_t* ri_end = ri + ri_size;
+
+ limb_t* i = data.begin();
+
+ if (li != li_end && ri != ri_end)
+ {
+ *i++ = _convert_first<neg>(_convert_first<lhs_neg>(*li) | _convert_first<rhs_neg>(*ri));
+ ++li;
+ ++ri;
+ }
+
+ for (; li != li_end && ri != ri_end; ++li, ++ri)
+ {
+ *i++ = _convert<neg>(_convert<lhs_neg>(*li) | _convert<rhs_neg>(*ri));
+ }
+
+ for (; li != li_end; ++li)
+ {
+ *i++ = _convert<neg>(_convert<lhs_neg>(*li) | _convert<rhs_neg>(0)); // or with rhs sign bit
+ }
+
+ for (; ri != ri_end; ++ri)
+ {
+ *i++ = _convert<neg>(_convert<lhs_neg>(0) | _convert<rhs_neg>(*ri)); // or with lhs sign bit
+ }
+
+ _normalize();
+ }
+
+ void or_(const bigint_default_implementation& lhs, const bigint_default_implementation& rhs)
+ {
+ if (lhs.negative)
+ rhs.negative ? _or_<true, true>(lhs, rhs) : _or_<true, false>(lhs, rhs);
+ else
+ rhs.negative ? _or_<false, true>(lhs, rhs) : _or_<false, false>(lhs, rhs);
+ }
+
+ template <bool lhs_neg, bool rhs_neg> void _and_(const bigint_default_implementation& lhs, const bigint_default_implementation& rhs)
+ {
+ const bool neg = lhs_neg && rhs_neg; // sign bit is and-ed
+ negative = neg;
+
+ size_t li_size = lhs.data.size();
+ size_t ri_size = rhs.data.size();
+
+ data.resize((std::max)(lhs.data.size(), rhs.data.size()));
+
+ const limb_t* li = lhs.data.begin();
+ const limb_t* li_end = li + li_size;
+ const limb_t* ri = rhs.data.begin();
+ const limb_t* ri_end = ri + ri_size;
+
+ limb_t* i = data.begin();
+
+ if (li != li_end && ri != ri_end)
+ {
+ *i++ = _convert_first<neg>(_convert_first<lhs_neg>(*li) & _convert_first<rhs_neg>(*ri));
+ ++li;
+ ++ri;
+ }
+
+ for (; li != li_end && ri != ri_end; ++li, ++ri)
+ {
+ *i++ = _convert<neg>(_convert<lhs_neg>(*li) & _convert<rhs_neg>(*ri));
+ }
+
+ for (; li != li_end; ++li)
+ {
+ *i++ = _convert<neg>(_convert<lhs_neg>(*li) & _convert<rhs_neg>(0)); // and with rhs sign bit
+ }
+
+ for (; ri != ri_end; ++ri)
+ {
+ *i++ = _convert<neg>(_convert<lhs_neg>(0) & _convert<rhs_neg>(*ri)); // and with lhs sign bit
+ }
+
+ _normalize();
+ }
+
+ void and_(const bigint_default_implementation& lhs, const bigint_default_implementation& rhs)
+ {
+ if (lhs.negative)
+ rhs.negative ? _and_<true, true>(lhs, rhs) : _and_<true, false>(lhs, rhs);
+ else
+ rhs.negative ? _and_<false, true>(lhs, rhs) : _and_<false, false>(lhs, rhs);
+ }
+
+ template <bool lhs_neg, bool rhs_neg> void _xor_(const bigint_default_implementation& lhs, const bigint_default_implementation& rhs)
+ {
+ const bool neg = lhs_neg ? !rhs_neg : rhs_neg; // sign bit is xor-ed
+ negative = neg;
+
+ size_t li_size = lhs.data.size();
+ size_t ri_size = rhs.data.size();
+
+ data.resize((std::max)(lhs.data.size(), rhs.data.size()));
+
+ const limb_t* li = lhs.data.begin();
+ const limb_t* li_end = li + li_size;
+ const limb_t* ri = rhs.data.begin();
+ const limb_t* ri_end = ri + ri_size;
+
+ limb_t* i = data.begin();
+
+ if (li != li_end && ri != ri_end)
+ {
+ *i++ = _convert_first<neg>(_convert_first<lhs_neg>(*li) ^ _convert_first<rhs_neg>(*ri));
+ ++li;
+ ++ri;
+ }
+
+ for (; li != li_end && ri != ri_end; ++li, ++ri)
+ {
+ *i++ = _convert<neg>(_convert<lhs_neg>(*li) ^ _convert<rhs_neg>(*ri));
+ }
+
+ for (; li != li_end; ++li)
+ {
+ *i++ = _convert<neg>(_convert<lhs_neg>(*li) ^ _convert<rhs_neg>(0)); // xor with rhs sign bit
+ }
+
+ for (; ri != ri_end; ++ri)
+ {
+ *i++ = _convert<neg>(_convert<lhs_neg>(0) ^ _convert<rhs_neg>(*ri)); // xor with lhs sign bit
+ }
+
+ _normalize();
+ }
+
+ void xor_(const bigint_default_implementation& lhs, const bigint_default_implementation& rhs)
+ {
+ if (lhs.negative)
+ rhs.negative ? _xor_<true, true>(lhs, rhs) : _xor_<true, false>(lhs, rhs);
+ else
+ rhs.negative ? _xor_<false, true>(lhs, rhs) : _xor_<false, false>(lhs, rhs);
+ }
+
+ void not_(const bigint_default_implementation& lhs)
+ {
+ // ~value == -(value + 1) == -value-1
+ negate(lhs);
+ dec();
+ }
+
+ void negate(const bigint_default_implementation& lhs)
+ {
+ data = lhs.data;
+ negative = !lhs.negative;
+ if (data.empty()) negative = false;
+ }
+
+ void lshift(const bigint_default_implementation& lhs, boost::uint64_t rhs)
+ {
+ }
+
+ void rshift(const bigint_default_implementation& lhs, boost::uint64_t rhs)
+ {
+ }
+
+ void inc()
+ {
+ bigint_default_implementation one;
+ one.assign(1);
+
+ add(*this, one);
+ }
+
+ void dec()
+ {
+ bigint_default_implementation one;
+ one.assign(1);
+
+ sub(*this, one);
+ }
+
+ int compare(const bigint_default_implementation& rhs) const
+ {
+ if (negative != rhs.negative) return negative > rhs.negative ? -1 : 1;
+
+ int result = negative ? -1 : 1;
+
+ if (data.size() != rhs.data.size()) return result * (data.size() < rhs.data.size() ? -1 : 1);
+ if (data.empty()) return 0;
+
+ const limb_t* li = data.end();
+ const limb_t* ri = rhs.data.end();
+
+ do
+ {
+ --li; --ri;
+
+ if (*li < *ri)
+ {
+ return -result;
+ }
+ else if (*li > *ri)
+ {
+ return result;
+ }
+ }
+ while (li != data.begin());
+
+ return 0;
+ }
+
+ // *this = *this / a, return division remainder
+ limb_t _div_rem(limb_t a)
+ {
+ if (data.empty()) return 0;
+
+ limb_t remainder = 0;
+
+ limb_t* i = data.end();
+
+ do
+ {
+ --i;
+
+ limb2_t result = (static_cast<limb2_t>(remainder) << limb_bit_number) + *i;
+
+ *i = static_cast<limb_t>(result / a);
+
+ remainder = static_cast<limb_t>(result % a);
+ }
+ while (i != data.begin());
+
+ if (*(data.end() - 1) == 0) data.resize(data.size() - 1);
+
+ return remainder;
+ }
+
+ template <typename Ch> std::basic_string<Ch> _to_str(int base) const
+ {
+ assert(base >= 2 && base <= 36);
+
+ if (data.empty()) return std::basic_string<Ch>(1, Ch('0'));
+
+ std::basic_string<Ch> result;
+
+ bigint_default_implementation copy = *this;
+
+ static const Ch digit_char_tab[] =
+ {
+ Ch('0'), Ch('1'), Ch('2'), Ch('3'), Ch('4'), Ch('5'), Ch('6'), Ch('7'), Ch('8'), Ch('9'),
+ Ch('a'), Ch('b'), Ch('c'), Ch('d'), Ch('e'), Ch('f'), Ch('g'), Ch('h'), Ch('i'), Ch('j'),
+ Ch('k'), Ch('l'), Ch('m'), Ch('n'), Ch('o'), Ch('p'), Ch('q'), Ch('r'), Ch('s'), Ch('t'),
+ Ch('u'), Ch('v'), Ch('w'), Ch('x'), Ch('y'), Ch('z')
+ };
+
+ while (!copy.data.empty())
+ {
+ result += digit_char_tab[copy._div_rem(static_cast<limb_t>(base))];
+ }
+
+ if (negative) result += '-';
+
+ std::reverse(result.begin(), result.end());
+
+ return result;
+ }
+
+ std::string str(int base) const
+ {
+ return _to_str<char>(base);
+ }
+
+ std::wstring wstr(int base) const
+ {
+ return _to_str<wchar_t>(base);
+ }
+
+ boost::uint64_t _to_uint64() const
+ {
+ boost::uint64_t value = 0;
+ boost::uint64_t power = 1;
+
+ for (const limb_t* i = data.begin(); i != data.end(); ++i)
+ {
+ value += *i * power;
+ power <<= limb_bit_number;
+ }
+
+ return value;
+ }
+
+ template <typename T> bool can_convert_to() const
+ {
+ // Only integer types supported
+ if (!std::numeric_limits<T>::is_integer) return false;
+
+ boost::uint64_t max_value;
+
+ size_t count = data.size();
+
+ if (negative)
+ {
+ max_value = static_cast<boost::uint64_t>(-static_cast<boost::int64_t>((std::numeric_limits<T>::min)()));
+ }
+ else
+ {
+ max_value = (std::numeric_limits<T>::max)();
+ }
+
+ if (count * limb_bit_number > sizeof(boost::uint64_t) * 8) // we can't fit in uint64 => we won't fit in anything else
+ return false;
+
+ return max_value >= _to_uint64();
+ }
+
+ template <typename T> T to_number() const
+ {
+ if (!std::numeric_limits<T>::is_integer) return T();
+
+ boost::uint64_t value = _to_uint64();
+
+ return negative ? static_cast<T>(-static_cast<boost::int64_t>(value)) : static_cast<T>(value);
+ }
+
+ bool is_zero() const
+ {
+ return data.empty();
+ }
+
+ void abs(const bigint_default_implementation& rhs)
+ {
+ data = rhs.data;
+ negative = false;
+ }
+
+ void pow(const bigint_default_implementation& lhs, boost::uint64_t rhs)
+ {
+ }
+
+ void div(const bigint_default_implementation& lhs, const bigint_default_implementation& rhs, bigint_default_implementation& remainder)
+ {
+ }
+
+ void sqrt(const bigint_default_implementation& lhs)
+ {
+ }
+ };
+} } // namespace boost::detail
+
+#endif // BOOST_BIGINT_BIGINT_DEFAULT_HPP
Modified: sandbox/SOC/2007/bigint/boost/bigint/bigint_gmp.hpp
==============================================================================
--- sandbox/SOC/2007/bigint/boost/bigint/bigint_gmp.hpp (original)
+++ sandbox/SOC/2007/bigint/boost/bigint/bigint_gmp.hpp 2007-07-22 16:08:56 EDT (Sun, 22 Jul 2007)
@@ -92,7 +92,7 @@
data->_mp_size = size;
}
- template <typename Ch> void assign_str(const Ch* str, int base)
+ template <typename Ch> void _assign_str(const Ch* str, int base)
{
assert(base >= 2 && base <= 36);
@@ -127,7 +127,7 @@
while (*str == Ch('0')) ++str;
// is there anything left?
- if (!str)
+ if (!*str)
{
assign(0);
return;
@@ -162,12 +162,12 @@
void assign(const char* str, int base)
{
- assign_str(str, base);
+ _assign_str(str, base);
}
void assign(const wchar_t* str, int base)
{
- assign_str(str, base);
+ _assign_str(str, base);
}
void add(const bigint_gmp_implementation& lhs, const bigint_gmp_implementation& rhs)
Added: sandbox/SOC/2007/bigint/boost/bigint/bigint_storage_fixed.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/boost/bigint/bigint_storage_fixed.hpp 2007-07-22 16:08:56 EDT (Sun, 22 Jul 2007)
@@ -0,0 +1,83 @@
+/* Boost bigint_storage_fixed.hpp header file
+ *
+ * Copyright 2007 Arseny Kapoulkine
+ *
+ * Distributed under the Boost Software License, Version 1.0.
+ * (See accompanying file LICENSE_1_0.txt or
+ * copy at http://www.boost.org/LICENSE_1_0.txt)
+ */
+
+#ifndef BOOST_BIGINT_BIGINT_STORAGE_FIXED_HPP
+#define BOOST_BIGINT_BIGINT_STORAGE_FIXED_HPP
+
+#include <vector>
+
+namespace boost { namespace detail {
+template <size_t N> struct bigint_storage_fixed
+{
+ template <typename T> class type
+ {
+ T data[N / sizeof(T)];
+ size_t count;
+
+ public:
+ type(): count(0)
+ {
+ }
+
+ size_t _max_size()
+ {
+ return (N / sizeof(T));
+ }
+
+ void resize(size_t size)
+ {
+ if (size > _max_size()) throw std::bad_alloc();
+
+ count = size;
+ }
+
+ size_t size() const
+ {
+ return count;
+ }
+
+ bool empty() const
+ {
+ return count == 0;
+ }
+
+ const T* begin() const
+ {
+ return data;
+ }
+
+ T* begin()
+ {
+ return data;
+ }
+
+ const T* end() const
+ {
+ return data + count;
+ }
+
+ T* end()
+ {
+ return data + count;
+ }
+
+ const T& operator[](size_t index) const
+ {
+ return begin()[index];
+ }
+
+ T& operator[](size_t index)
+ {
+ return begin()[index];
+ }
+ };
+};
+} } // namespace boost::detail
+
+#endif // BOOST_BIGINT_BIGINT_STORAGE_FIXED_HPP
Added: sandbox/SOC/2007/bigint/boost/bigint/bigint_storage_vector.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/boost/bigint/bigint_storage_vector.hpp 2007-07-22 16:08:56 EDT (Sun, 22 Jul 2007)
@@ -0,0 +1,68 @@
+/* Boost bigint_storage_vector.hpp header file
+ *
+ * Copyright 2007 Arseny Kapoulkine
+ *
+ * Distributed under the Boost Software License, Version 1.0.
+ * (See accompanying file LICENSE_1_0.txt or
+ * copy at http://www.boost.org/LICENSE_1_0.txt)
+ */
+
+#ifndef BOOST_BIGINT_BIGINT_STORAGE_VECTOR_HPP
+#define BOOST_BIGINT_BIGINT_STORAGE_VECTOR_HPP
+
+#include <vector>
+
+namespace boost { namespace detail {
+template <typename T> class bigint_storage_vector
+{
+ std::vector<T> data;
+
+public:
+ void resize(size_t size)
+ {
+ data.resize(size);
+ }
+
+ size_t size() const
+ {
+ return data.size();
+ }
+
+ bool empty() const
+ {
+ return data.empty();
+ }
+
+ const T* begin() const
+ {
+ return data.empty() ? 0 : &*data.begin();
+ }
+
+ T* begin()
+ {
+ return data.empty() ? 0 : &*data.begin();
+ }
+
+ const T* end() const
+ {
+ return data.empty() ? 0 : &*(data.end()-1)+1;
+ }
+
+ T* end()
+ {
+ return data.empty() ? 0 : &*(data.end()-1)+1;
+ }
+
+ const T& operator[](size_t index) const
+ {
+ return begin()[index];
+ }
+
+ T& operator[](size_t index)
+ {
+ return begin()[index];
+ }
+};
+} } // namespace boost::detail
+
+#endif // BOOST_BIGINT_BIGINT_STORAGE_VECTOR_HPP
Modified: sandbox/SOC/2007/bigint/libs/bigint/index.html
==============================================================================
--- sandbox/SOC/2007/bigint/libs/bigint/index.html (original)
+++ sandbox/SOC/2007/bigint/libs/bigint/index.html 2007-07-22 16:08:56 EDT (Sun, 22 Jul 2007)
@@ -498,7 +498,7 @@
during the project.</p>
<p>Jarrad Waterloo reminded me of some issues in the initial design that were
-overlooked (64-bit integer support, various bases for string conversion</p>
+overlooked (64-bit integer support, various bases for string conversion).</p>
<p>Phil Endecott reminded me to take special care of negative numbers in implementation
and documentation of bitwise operators.</p>
Modified: sandbox/SOC/2007/bigint/libs/bigint/test/can_convert_to.cpp
==============================================================================
--- sandbox/SOC/2007/bigint/libs/bigint/test/can_convert_to.cpp (original)
+++ sandbox/SOC/2007/bigint/libs/bigint/test/can_convert_to.cpp 2007-07-22 16:08:56 EDT (Sun, 22 Jul 2007)
@@ -13,6 +13,11 @@
#include <boost/bigint/bigint.hpp>
+#include <boost/bigint/bigint_gmp.hpp>
+#include <boost/bigint/bigint_default.hpp>
+#include <boost/bigint/bigint_storage_vector.hpp>
+#include <boost/bigint/bigint_storage_fixed.hpp>
+
#pragma comment(lib, "libgmp-3.lib")
template <typename I> void test()
@@ -149,6 +154,8 @@
int test_main(int argc, char* argv[])
{
test<boost::detail::bigint_gmp_implementation>();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type> >();
return 0;
}
Modified: sandbox/SOC/2007/bigint/libs/bigint/test/comparison.cpp
==============================================================================
--- sandbox/SOC/2007/bigint/libs/bigint/test/comparison.cpp (original)
+++ sandbox/SOC/2007/bigint/libs/bigint/test/comparison.cpp 2007-07-22 16:08:56 EDT (Sun, 22 Jul 2007)
@@ -13,6 +13,11 @@
#include <boost/bigint/bigint.hpp>
+#include <boost/bigint/bigint_gmp.hpp>
+#include <boost/bigint/bigint_default.hpp>
+#include <boost/bigint/bigint_storage_vector.hpp>
+#include <boost/bigint/bigint_storage_fixed.hpp>
+
#pragma comment(lib, "libgmp-3.lib")
// This macro is not quite good, but - it's ok for our needs
@@ -295,6 +300,8 @@
int test_main(int argc, char* argv[])
{
test<boost::detail::bigint_gmp_implementation>();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type> >();
return 0;
}
Modified: sandbox/SOC/2007/bigint/libs/bigint/test/number_conversion.cpp
==============================================================================
--- sandbox/SOC/2007/bigint/libs/bigint/test/number_conversion.cpp (original)
+++ sandbox/SOC/2007/bigint/libs/bigint/test/number_conversion.cpp 2007-07-22 16:08:56 EDT (Sun, 22 Jul 2007)
@@ -13,6 +13,11 @@
#include <boost/bigint/bigint.hpp>
+#include <boost/bigint/bigint_gmp.hpp>
+#include <boost/bigint/bigint_default.hpp>
+#include <boost/bigint/bigint_storage_vector.hpp>
+#include <boost/bigint/bigint_storage_fixed.hpp>
+
#include <sstream>
#pragma comment(lib, "libgmp-3.lib")
@@ -143,6 +148,8 @@
int test_main(int argc, char* argv[])
{
test<boost::detail::bigint_gmp_implementation>();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type> >();
return 0;
}
Modified: sandbox/SOC/2007/bigint/libs/bigint/test/stream.cpp
==============================================================================
--- sandbox/SOC/2007/bigint/libs/bigint/test/stream.cpp (original)
+++ sandbox/SOC/2007/bigint/libs/bigint/test/stream.cpp 2007-07-22 16:08:56 EDT (Sun, 22 Jul 2007)
@@ -13,6 +13,11 @@
#include <boost/bigint/bigint.hpp>
+#include <boost/bigint/bigint_gmp.hpp>
+#include <boost/bigint/bigint_default.hpp>
+#include <boost/bigint/bigint_storage_vector.hpp>
+#include <boost/bigint/bigint_storage_fixed.hpp>
+
#include <string>
#include <sstream>
@@ -279,6 +284,8 @@
int test_main(int argc, char* argv[])
{
test<boost::detail::bigint_gmp_implementation>();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type> >();
return 0;
}
Modified: sandbox/SOC/2007/bigint/libs/bigint/test/string_conversion.cpp
==============================================================================
--- sandbox/SOC/2007/bigint/libs/bigint/test/string_conversion.cpp (original)
+++ sandbox/SOC/2007/bigint/libs/bigint/test/string_conversion.cpp 2007-07-22 16:08:56 EDT (Sun, 22 Jul 2007)
@@ -13,6 +13,11 @@
#include <boost/bigint/bigint.hpp>
+#include <boost/bigint/bigint_gmp.hpp>
+#include <boost/bigint/bigint_default.hpp>
+#include <boost/bigint/bigint_storage_vector.hpp>
+#include <boost/bigint/bigint_storage_fixed.hpp>
+
#include <string>
#pragma comment(lib, "libgmp-3.lib")
@@ -110,6 +115,8 @@
int test_main(int argc, char* argv[])
{
test<boost::detail::bigint_gmp_implementation>();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type> >();
return 0;
}
Modified: sandbox/SOC/2007/bigint/libs/bigint/test/unary.cpp
==============================================================================
--- sandbox/SOC/2007/bigint/libs/bigint/test/unary.cpp (original)
+++ sandbox/SOC/2007/bigint/libs/bigint/test/unary.cpp 2007-07-22 16:08:56 EDT (Sun, 22 Jul 2007)
@@ -13,6 +13,11 @@
#include <boost/bigint/bigint.hpp>
+#include <boost/bigint/bigint_gmp.hpp>
+#include <boost/bigint/bigint_default.hpp>
+#include <boost/bigint/bigint_storage_vector.hpp>
+#include <boost/bigint/bigint_storage_fixed.hpp>
+
#pragma comment(lib, "libgmp-3.lib")
template <typename I> void test()
@@ -99,6 +104,8 @@
int test_main(int argc, char* argv[])
{
test<boost::detail::bigint_gmp_implementation>();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type> >();
return 0;
}
Modified: sandbox/SOC/2007/bigint/libs/bigint/todo.txt
==============================================================================
--- sandbox/SOC/2007/bigint/libs/bigint/todo.txt (original)
+++ sandbox/SOC/2007/bigint/libs/bigint/todo.txt 2007-07-22 16:08:56 EDT (Sun, 22 Jul 2007)
@@ -15,9 +15,9 @@
3. Correctness tests 7 June In progress
4. Documentation 21 June In progress
5. Performance tests 7 July In progress
-4. Interface for storage 14 July N/A
-5. Storage implementation 14 July N/A
-6. Default implementation 30 July N/A
+6. Interface for storage 14 July In progress
+7. Storage implementation 14 July In progress
+8. Default implementation 30 July In progress
Note that perhaps some features will be completed before the deadline and probably some features will not make the deadline,
and instead be finished several days later. So the list is by no means static.
@@ -165,6 +165,84 @@
* Is it possible to test cases when bigint must cause illegal operations (division by zero, sqrt(negative number))?
Status: investigated; there is no portable way
+4. Documentation
+
+- do we have to change the current behaviour for string conversions for bases outside [2, 36]?
+Status: needs investigating & implementing
+
+- provide accurate information for 'Performance' table
+
+5. Performance tests
+
+6. Interface for storage
+
+- refactor
+Status: needs implementing
+
+- do we need push_back?
+Status: needs investigation
+
+- perhaps move bool negative to storage?
+Status: needs investigation
+
+7. Storage implementation
+
+- implement all functionality for vector-based interface as set by interface requirements
+Status: needs implementing
+
+- implement stack based fixed capacity storage; add corresponding tests
+Status: needs implementing
+
+8. Default implementation
+
++ conversion from string with different bases (2-36, use 26 letters + 10 digits)
+Status: implemented
+
++ wide string support
+Status: implemented conversion to both strings and wide strings
+
++ proper 64-bit support for converting to bigint
+Status: implemented
+
++ proper converting to numbers (including 64-bit)
+Status: implemented
+
++ comparison operators
+Status: implemented
+
++ abs function
+Status: implemented
+
++ unary operators (+, -, ~, ++, --)
+Status: implemented
+
++ linear arithmetic operators (+, -)
+Status: implemented
+
++ bitwise operators (&, |, ^)
+Status: implemented
+
++ multiplication (*)
+Status: implemented
+
+- bitwise shifts (<<, >>)
+Status: needs implementing
+
+- division (/, %, div function)
+Status: needs implementing
+
+- sqrt function
+Status: needs implementing
+
+- pow function
+Status: needs implementing
+
+- make implementation parametrizable by config structure, make a default structure
+Status: needs implementing
+
+- add limb=unsigned char, limb=unsigned short tests
+Status: needs implementing
+
-----------------------------------------------
Problem: GMP calls abort() when failing to allocate memory.
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk