|
|
Boost-Commit : |
From: arseny.kapoulkine_at_[hidden]
Date: 2007-07-29 15:24:01
Author: zeux
Date: 2007-07-29 15:23:58 EDT (Sun, 29 Jul 2007)
New Revision: 7579
URL: http://svn.boost.org/trac/boost/changeset/7579
Log:
Default implementation improvements (proper configuration, division and modulo implementation, left/right shifts implementation, fixed bitwise operations with negative numbers, optimized string conversion, pow and sqrt functions), added performance table for default implementation, enhanced arithmetics and string conversion tests, added all available implementations to all tests, todo.txt changes
Text files modified:
sandbox/SOC/2007/bigint/boost/bigint/bigint_default.hpp | 452 ++++++++++++++++++++++++++++++++++-----
sandbox/SOC/2007/bigint/libs/bigint/index.html | 48 ++--
sandbox/SOC/2007/bigint/libs/bigint/test/arithmetics.cpp | 82 +++++++
sandbox/SOC/2007/bigint/libs/bigint/test/can_convert_to.cpp | 12
sandbox/SOC/2007/bigint/libs/bigint/test/comparison.cpp | 12
sandbox/SOC/2007/bigint/libs/bigint/test/functions.cpp | 17 +
sandbox/SOC/2007/bigint/libs/bigint/test/number_conversion.cpp | 12
sandbox/SOC/2007/bigint/libs/bigint/test/serialization.cpp | 12
sandbox/SOC/2007/bigint/libs/bigint/test/stream.cpp | 12
sandbox/SOC/2007/bigint/libs/bigint/test/string_conversion.cpp | 17 +
sandbox/SOC/2007/bigint/libs/bigint/test/unary.cpp | 12
sandbox/SOC/2007/bigint/libs/bigint/todo.txt | 33 +-
12 files changed, 595 insertions(+), 126 deletions(-)
Modified: sandbox/SOC/2007/bigint/boost/bigint/bigint_default.hpp
==============================================================================
--- sandbox/SOC/2007/bigint/boost/bigint/bigint_default.hpp (original)
+++ sandbox/SOC/2007/bigint/boost/bigint/bigint_default.hpp 2007-07-29 15:23:58 EDT (Sun, 29 Jul 2007)
@@ -17,14 +17,36 @@
#include <boost/bigint/bigint_util.hpp>
namespace boost { namespace detail {
+ template <size_t N> struct bigint_default_implementation_config;
+
+ template <> struct bigint_default_implementation_config<8>
+ {
+ typedef boost::uint8_t first;
+ typedef boost::uint16_t second;
+ };
+
+ template <> struct bigint_default_implementation_config<16>
+ {
+ typedef boost::uint16_t first;
+ typedef boost::uint32_t second;
+ };
+
+ template <> struct bigint_default_implementation_config<32>
+ {
+ typedef boost::uint32_t first;
+ typedef boost::uint64_t second;
+ };
+
// Default implementation
- template <template <class> class Storage> struct bigint_default_implementation
+ template <template <class> class Storage, size_t limb_bit_number = 32> struct bigint_default_implementation
{
- typedef unsigned int limb_t;
- typedef boost::uint64_t limb2_t;
+ typedef typename bigint_default_implementation_config<limb_bit_number>::first limb_t;
+ typedef typename bigint_default_implementation_config<limb_bit_number>::second limb2_t;
- enum { limb_bit_number = sizeof(limb_t) * 8 };
- #define limb_max std::numeric_limits<limb_t>::max()
+ static limb_t limb_max()
+ {
+ return std::numeric_limits<limb_t>::max();
+ }
Storage<limb_t> data;
bool negative;
@@ -60,12 +82,12 @@
if (number != 0)
{
data.resize(1);
- data[0] = static_cast<limb_t>(number & limb_max);
+ data[0] = static_cast<limb_t>(number & limb_max());
size = 1;
}
- if (number > limb_max)
+ if (number > limb_max())
{
data.resize(64 / limb_bit_number); // we know that limb_bit_number is 2^n
@@ -73,7 +95,7 @@
while (number > 0)
{
- data[size++] = static_cast<limb_t>(number & limb_max);
+ data[size++] = static_cast<limb_t>(number & limb_max());
number >>= limb_bit_number;
}
}
@@ -91,7 +113,7 @@
{
limb2_t result = static_cast<limb2_t>(*i) * a + carry;
- *i = static_cast<limb_t>(result & limb_max);
+ *i = static_cast<limb_t>(result & limb_max());
carry = static_cast<limb_t>(result >> limb_bit_number);
}
@@ -187,7 +209,7 @@
{
limb2_t result = static_cast<limb2_t>(*li) + *ri + carry;
- *i++ = static_cast<limb_t>(result & limb_max);
+ *i++ = static_cast<limb_t>(result & limb_max());
carry = static_cast<limb_t>(result >> limb_bit_number);
}
@@ -196,7 +218,7 @@
{
limb2_t result = static_cast<limb2_t>(*li) + carry;
- *i++ = static_cast<limb_t>(result & limb_max);
+ *i++ = static_cast<limb_t>(result & limb_max());
carry = static_cast<limb_t>(result >> limb_bit_number);
}
@@ -205,7 +227,7 @@
{
limb2_t result = static_cast<limb2_t>(*ri) + carry;
- *i++ = static_cast<limb_t>(result & limb_max);
+ *i++ = static_cast<limb_t>(result & limb_max());
carry = static_cast<limb_t>(result >> limb_bit_number);
}
@@ -266,7 +288,7 @@
if (result > *li)
{
- result = static_cast<limb2_t>(limb_max) + 1 + *li - result;
+ result = static_cast<limb2_t>(limb_max()) + 1 + *li - result;
borrow = 1;
}
else
@@ -275,7 +297,7 @@
borrow = 0;
}
- *i++ = static_cast<limb_t>(result & limb_max);
+ *i++ = static_cast<limb_t>(result & limb_max());
}
for (; li != li_end; ++li)
@@ -284,7 +306,7 @@
if (result > *li)
{
- result = static_cast<limb2_t>(limb_max) + 1 + *li - result;
+ result = static_cast<limb2_t>(limb_max()) + 1 + *li - result;
borrow = 1;
}
else
@@ -293,7 +315,7 @@
borrow = 0;
}
- *i++ = static_cast<limb_t>(result & limb_max);
+ *i++ = static_cast<limb_t>(result & limb_max());
}
for (; ri != ri_end; ++ri)
@@ -302,7 +324,7 @@
if (result > 0)
{
- result = static_cast<limb2_t>(limb_max) + 1 - result;
+ result = static_cast<limb2_t>(limb_max()) + 1 - result;
borrow = 1;
}
else
@@ -310,7 +332,7 @@
borrow = 0;
}
- *i++ = static_cast<limb_t>(result & limb_max);
+ *i++ = static_cast<limb_t>(result & limb_max());
}
if (borrow != 0)
@@ -318,7 +340,7 @@
// 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;
+ *j = limb_max()- *j;
data[0]++;
}
@@ -393,7 +415,7 @@
{
limb2_t result = static_cast<limb2_t>(*li) * *ri + *ci + carry;
- *ci++ = static_cast<limb_t>(result & limb_max);
+ *ci++ = static_cast<limb_t>(result & limb_max());
carry = static_cast<limb_t>(result >> limb_bit_number);
}
@@ -402,7 +424,7 @@
{
limb2_t result = static_cast<limb2_t>(*ci) + carry;
- *ci++ = static_cast<limb_t>(result & limb_max);
+ *ci++ = static_cast<limb_t>(result & limb_max());
carry = static_cast<limb_t>(result >> limb_bit_number);
}
@@ -413,24 +435,163 @@
negative = lhs.negative ? !rhs.negative : rhs.negative;
}
+ void _div_unsigned(const bigint_default_implementation& lhs, const bigint_default_implementation& rhs, bigint_default_implementation& r)
+ {
+ if (rhs.data.empty())
+ {
+ volatile int i = 0;
+ i /= i;
+ return;
+ }
+
+ if (lhs.data.empty())
+ {
+ r.assign(0);
+ assign(0);
+ return;
+ }
+
+ if (this == &r)
+ {
+ bigint_default_implementation rem;
+ _div_unsigned(lhs, rhs, rem);
+ r = rem;
+ return;
+ }
+
+ bigint_default_implementation x(lhs);
+ x.negative = false;
+
+ bigint_default_implementation y(rhs);
+ y.negative = false;
+
+ // without this our estimates for qd become very bad
+ limb_t d = static_cast<limb_t>((static_cast<limb2_t>(limb_max()) + 1) / (static_cast<limb_t>(y.data[y.data.size() - 1]) + 1));
+ x._mul_add(d, 0);
+ y._mul_add(d, 0);
+
+ data.resize(x.data.size());
+ r.data.resize(0);
+
+ limb_t* p = data.end();
+ limb_t* i = x.data.end();
+
+ do
+ {
+ --i;
+ --p;
+
+ // xx = r * (limb_max() + 1) + x[i]
+ bigint_default_implementation xx;
+ xx.data.resize(r.data.size() + 1);
+ xx.data[0] = *i;
+
+ limb_t* xx_data = xx.data.begin() + 1;
+ for (const limb_t* ri = r.data.begin(); ri != r.data.end(); ++ri)
+ *xx_data++ = *ri;
+
+ if (xx.data.size() < y.data.size())
+ {
+ *p = 0;
+ r = xx;
+ }
+ else if (xx.data.size() == y.data.size())
+ {
+ bigint_default_implementation z;
+ z.sub(xx, y);
+
+ if (z.negative)
+ {
+ *p = 0;
+ r = xx;
+ }
+ else
+ {
+ *p = 1;
+ r = z;
+ }
+ }
+ else
+ {
+ // Guess a value for q [Knuth, vol.2, section 4.3.1]
+ limb_t qd;
+
+ if (xx.data[xx.data.size()-1] >= y.data[y.data.size()-1])
+ qd = limb_max();
+ else
+ qd = static_cast<limb_t>(
+ ((static_cast<limb2_t>(limb_max()) + 1) * xx.data[xx.data.size()-1] + xx.data[xx.data.size()-2])
+ / y.data[y.data.size()-1]
+ );
+
+ bigint_default_implementation rs = y;
+ rs._mul_add(qd, 0);
+ rs.sub(xx, rs);
+
+ // rs = xx - qd * y
+
+ if (!rs.negative)
+ {
+ while (rs.compare(y) >= 0)
+ {
+ ++qd;
+ rs.sub(rs, y);
+ }
+ }
+ else
+ {
+ while (rs.negative)
+ {
+ --qd;
+ rs.add(rs, y);
+ }
+ }
+
+ *p = static_cast<limb_t>(qd);
+ r = rs;
+ }
+ }
+ while (i != x.data.begin());
+
+ _normalize();
+
+ if (!r.data.empty() && d > 1)
+ {
+ r._div_rem(d);
+ }
+
+ }
+
void div(const bigint_default_implementation& lhs, const bigint_default_implementation& rhs)
{
+ bool neg = lhs.negative ? !rhs.negative : rhs.negative;
+ bigint_default_implementation r;
+ _div_unsigned(lhs, rhs, r);
+ negative = data.empty() ? false : neg;
}
void mod(const bigint_default_implementation& lhs, const bigint_default_implementation& rhs)
{
+ bool neg = lhs.negative;
+ bigint_default_implementation q;
+ q._div_unsigned(lhs, rhs, *this);
+ negative = data.empty() ? false : neg;
}
- template <bool complement> limb_t _convert(limb_t limb)
+ // carry = 0 or carry = 1
+ template <bool complement> limb_t _convert(limb_t limb, limb_t& carry)
{
- return complement ? limb_max - limb : limb;
+ if (complement)
+ {
+ limb2_t r = static_cast<limb2_t>(limb_max() - limb) + carry;
+
+ carry = static_cast<limb_t>(r >> limb_bit_number);
+ return static_cast<limb_t>(r & limb_max());
+ }
+ else
+ return 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
@@ -448,26 +609,21 @@
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;
- }
-
+ limb_t carry = 1, lcarry = 1, rcarry = 1;
+
for (; li != li_end && ri != ri_end; ++li, ++ri)
{
- *i++ = _convert<neg>(_convert<lhs_neg>(*li) | _convert<rhs_neg>(*ri));
+ *i++ = _convert<neg>(_convert<lhs_neg>(*li, lcarry) | _convert<rhs_neg>(*ri, rcarry), carry);
}
for (; li != li_end; ++li)
{
- *i++ = _convert<neg>(_convert<lhs_neg>(*li) | _convert<rhs_neg>(0)); // or with rhs sign bit
+ *i++ = _convert<neg>(_convert<lhs_neg>(*li, lcarry) | _convert<rhs_neg>(0, rcarry), carry); // 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
+ *i++ = _convert<neg>(_convert<lhs_neg>(0, lcarry) | _convert<rhs_neg>(*ri, rcarry), carry); // or with lhs sign bit
}
_normalize();
@@ -498,26 +654,21 @@
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;
- }
+ limb_t carry = 1, lcarry = 1, rcarry = 1;
for (; li != li_end && ri != ri_end; ++li, ++ri)
{
- *i++ = _convert<neg>(_convert<lhs_neg>(*li) & _convert<rhs_neg>(*ri));
+ *i++ = _convert<neg>(_convert<lhs_neg>(*li, lcarry) & _convert<rhs_neg>(*ri, rcarry), carry);
}
for (; li != li_end; ++li)
{
- *i++ = _convert<neg>(_convert<lhs_neg>(*li) & _convert<rhs_neg>(0)); // and with rhs sign bit
+ *i++ = _convert<neg>(_convert<lhs_neg>(*li, lcarry) & _convert<rhs_neg>(0, rcarry), carry); // 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
+ *i++ = _convert<neg>(_convert<lhs_neg>(0, lcarry) & _convert<rhs_neg>(*ri, rcarry), carry); // and with lhs sign bit
}
_normalize();
@@ -548,26 +699,21 @@
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;
- }
+ limb_t carry = 1, lcarry = 1, rcarry = 1;
for (; li != li_end && ri != ri_end; ++li, ++ri)
{
- *i++ = _convert<neg>(_convert<lhs_neg>(*li) ^ _convert<rhs_neg>(*ri));
+ *i++ = _convert<neg>(_convert<lhs_neg>(*li, lcarry) ^ _convert<rhs_neg>(*ri, rcarry), carry);
}
for (; li != li_end; ++li)
{
- *i++ = _convert<neg>(_convert<lhs_neg>(*li) ^ _convert<rhs_neg>(0)); // xor with rhs sign bit
+ *i++ = _convert<neg>(_convert<lhs_neg>(*li, lcarry) ^ _convert<rhs_neg>(0, rcarry), carry); // 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
+ *i++ = _convert<neg>(_convert<lhs_neg>(0, lcarry) ^ _convert<rhs_neg>(*ri, rcarry), carry); // xor with lhs sign bit
}
_normalize();
@@ -597,10 +743,94 @@
void lshift(const bigint_default_implementation& lhs, boost::uint64_t rhs)
{
+ if (this == &lhs)
+ {
+ bigint_default_implementation copy = lhs;
+ return lshift(copy, rhs);
+ }
+
+ if (lhs.data.empty())
+ {
+ assign(0);
+ return;
+ }
+
+ data.resize(lhs.data.size() + rhs / limb_bit_number);
+
+ limb_t* di = data.begin() + rhs / limb_bit_number;
+
+ for (limb_t* i = data.begin(); i != di; ++i)
+ *i = 0;
+
+ for (const limb_t* li = lhs.data.begin(); li != lhs.data.end(); ++li)
+ *di++ = *li;
+
+ _mul_add(1 << (rhs % limb_bit_number), 0);
+
+ negative = lhs.negative;
}
void rshift(const bigint_default_implementation& lhs, boost::uint64_t rhs)
{
+ if (this == &lhs)
+ {
+ bigint_default_implementation copy = lhs;
+ return rshift(copy, rhs);
+ }
+
+ if (lhs.data.empty())
+ {
+ assign(0);
+ return;
+ }
+
+ if (rhs / limb_bit_number > lhs.data.size())
+ {
+ assign(lhs.negative ? -1 : 0);
+ return;
+ }
+
+ data.resize(lhs.data.size() - rhs / limb_bit_number);
+
+ limb_t* di = data.begin();
+
+ for (const limb_t* li = lhs.data.begin() + rhs / limb_bit_number; li != lhs.data.end(); ++li)
+ *di++ = *li;
+
+ limb_t r = _div_rem(1 << (rhs % limb_bit_number));
+
+ if (lhs.negative)
+ {
+ // if the result is zero, add sign bit
+ if (data.empty())
+ {
+ assign(-1);
+ return;
+ }
+
+ negative = true;
+
+ // we need to correct the result if there was a remainder
+ bool correct = (r != 0);
+
+ if (!correct)
+ {
+ const limb_t* li_end = lhs.data.begin() + rhs / limb_bit_number;
+
+ for (const limb_t* li = lhs.data.begin(); li != li_end; ++li)
+ if (*li != 0)
+ {
+ correct = true;
+ break;
+ }
+ }
+
+ if (correct) dec();
+ }
+ else
+ {
+ negative = false;
+ }
}
void inc()
@@ -693,11 +923,29 @@
Ch('u'), Ch('v'), Ch('w'), Ch('x'), Ch('y'), Ch('z')
};
+ limb_t base_power = base;
+ size_t count = 1;
+
+ while (static_cast<limb2_t>(base_power) * base <= limb_max())
+ {
+ base_power *= base;
+ ++count;
+ }
+
while (!copy.data.empty())
{
- result += digit_char_tab[copy._div_rem(static_cast<limb_t>(base))];
+ limb_t r = copy._div_rem(base_power);
+
+ for (size_t i = 0; i < count; ++i)
+ {
+ result += digit_char_tab[r % base];
+ r /= base;
+ }
}
+ while (result.size() > 1 && result[result.size() - 1] == '0')
+ result.erase(result.size() - 1);
+
if (negative) result += '-';
std::reverse(result.begin(), result.end());
@@ -775,14 +1023,104 @@
void pow(const bigint_default_implementation& lhs, boost::uint64_t rhs)
{
+ if (lhs.data.empty())
+ {
+ assign(rhs == 0 ? 1 : 0);
+ return;
+ }
+
+ if (lhs.data.size() == 1 && lhs.data[0] == 1)
+ {
+ assign(lhs.negative ? (rhs % 2 ? -1 : 1) : 1);
+ return;
+ }
+
+ assign(1);
+
+ boost::uint64_t pot = 1;
+
+ // Find largest power of two that is >= rhs
+ while (pot < rhs && (pot << 1) != 0)
+ pot <<= 1;
+
+ // Now pot is the highest bit of rhs
+ if (pot > rhs)
+ pot >>= 1;
+
+ while (pot > 0)
+ {
+ mul(*this, *this);
+
+ if ((rhs & pot) != 0)
+ {
+ mul(*this, lhs);
+ }
+
+ pot >>= 1;
+ }
}
void div(const bigint_default_implementation& lhs, const bigint_default_implementation& rhs, bigint_default_implementation& remainder)
{
+ bool q_neg = lhs.negative ? !rhs.negative : rhs.negative;
+ bool r_neg = lhs.negative;
+ _div_unsigned(lhs, rhs, remainder);
+ negative = data.empty() ? false : q_neg;
+ remainder.negative = remainder.data.empty() ? false : r_neg;
}
void sqrt(const bigint_default_implementation& lhs)
{
+ if (lhs.negative)
+ {
+ volatile int i = 0;
+ i /= i;
+ return;
+ }
+
+ if (lhs.data.empty())
+ {
+ assign(0);
+ return;
+ }
+
+ bigint_default_implementation a; // approximation
+ a.data.resize((lhs.data.size() + 1) / 2);
+
+ for (limb_t* i = a.data.begin(); i != a.data.end(); ++i)
+ *i = 0;
+
+ a.data[a.data.size() - 1] = lhs.data[lhs.data.size() - 1] / 2;
+
+ if (a.data[a.data.size() - 1] == 0)
+ a.data[a.data.size() - 1] = 1;
+
+ // iterate
+ for (;;)
+ {
+ bigint_default_implementation ia;
+ ia.div(lhs, a);
+
+ bigint_default_implementation na;
+ na.add(ia, a);
+ na._div_rem(2);
+ // na = (lhs / a + a) / 2
+
+ // if |ia-a|=1, then na = min(ia, a), and it's our result
+ if (na.compare(a) == 0) // a = na
+ {
+ *this = na;
+ return;
+ }
+
+ if (na.compare(ia) == 0) // a = ia
+ {
+ *this = na;
+ return;
+ }
+
+ a = na;
+ }
}
};
} } // namespace boost::detail
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-29 15:23:58 EDT (Sun, 29 Jul 2007)
@@ -450,29 +450,29 @@
<p>'Length' means number of bits for integer arguments and number of characters for strings.</p>
-<table><tr><th>Function(s)</th><th>'gmp' implementation</th></tr>
-<tr><td>default ctor</td><td>O(1)</td></tr>
-<tr><td>integer ctors</td><td>O(1)</td></tr>
-<tr><td>string ctors</td><td>O(A1) <font color="#ff0000">check</font></td></tr>
-<tr><td>+, -, +=, -=</td><td>O(M)</td></tr>
-<tr><td>*, *=</td><td><= O(M<sup>2</sup>) <font color="#ff0000">provide more precise info</font></td></tr>
-<tr><td>/, /=</td><td><= O(M<sup>2</sup>) <font color="#ff0000">provide more precise info</font></td></tr>
-<tr><td>%, %=</td><td><= O(M<sup>2</sup>) <font color="#ff0000">provide more precise info</font></td></tr>
-<tr><td>&, &=, |, |=, ^, ^=</td><td>O(M)</td></tr>
-<tr><td><<, >></td><td>O(max(A1, 2<sup>A2</sup>)) <font color="#808080"> NB. O(2<sup>A2</sup>) is equal to O(shift amount)</font></td></tr>
-<tr><td><<=, >>=</td><td>O(max(N, 2<sup>A1</sup>)) <font color="#808080"> NB. O(2<sup>A1</sup>) is equal to O(shift amount)</font></td></tr>
-<tr><td>++, --</td><td>O(N)</td></tr>
-<tr><td>+, -</td><td>O(1)</td></tr>
-<tr><td>~</td><td>O(N)</td></tr>
-<tr><td>bool conversions</td><td>O(1)</td></tr>
-<tr><td>string conversions</td><td>O(N) <font color="#ff0000">check</font></td></tr>
-<tr><td>can_convert_to</td><td>O(1)</font></td></tr>
-<tr><td>to_number</td><td>O(N)</font></td></tr>
-<tr><td>comparison operators</td><td>O(M)</font></td></tr>
-<tr><td>abs</td><td>O(M)</font></td></tr>
-<tr><td>pow</td><td>O(A1 * A2) <font color="#ff0000">check</font></td></tr>
-<tr><td>div</td><td><= O(M<sup>2</sup>) <font color="#ff0000">provide more precise info</font></td></tr>
-<tr><td>sqrt</td><td><= O(M<sup>2</sup>) <font color="#ff0000">provide more precise info</font></td></tr>
+<table><tr><th>Function(s)</th><th>'gmp' implementation</th><th>'default' implementation</th></tr>
+<tr><td>default ctor</td><td>O(1)</td><td>O(1)</td></tr>
+<tr><td>integer ctors</td><td>O(1)</td><td>O(1)</td></tr>
+<tr><td>string ctors</td><td>O(A1) <font color="#ff0000">check</font></td><td>O(A1<sup>2</sup>)</td></tr>
+<tr><td>+, -, +=, -=</td><td>O(M)</td><td>O(M)</td></tr>
+<tr><td>*, *=</td><td><= O(M<sup>2</sup>) <font color="#ff0000">provide more precise info</font></td><td>O(M<sup>2</sup>)</td></tr>
+<tr><td>/, /=</td><td><= O(M<sup>2</sup>) <font color="#ff0000">provide more precise info</font></td><td>O(M<sup>2</sup>)</td></tr>
+<tr><td>%, %=</td><td><= O(M<sup>2</sup>) <font color="#ff0000">provide more precise info</font></td><td>O(M<sup>2</sup>)</td></tr>
+<tr><td>&, &=, |, |=, ^, ^=</td><td>O(M)</td><td>O(M)</td></tr>
+<tr><td><<, >></td><td>O(max(A1, 2<sup>A2</sup>)) <font color="#808080"> NB. O(2<sup>A2</sup>) is equal to O(shift amount)</font></td><td>O(max(A1, 2<sup>A2</sup>))</td></tr>
+<tr><td><<=, >>=</td><td>O(max(N, 2<sup>A1</sup>)) <font color="#808080"> NB. O(2<sup>A1</sup>) is equal to O(shift amount)</font></td><td>O(max(N, 2<sup>A1</sup>))</td></tr>
+<tr><td>++, --</td><td>O(N)</td><td>O(N)</td></tr>
+<tr><td>+, -</td><td>O(1)</td><td>O(1)</td></tr>
+<tr><td>~</td><td>O(N)</td><td>O(N)</td></tr>
+<tr><td>bool conversions</td><td>O(1)</td><td>O(1)</td></tr>
+<tr><td>string conversions</td><td>O(N) <font color="#ff0000">check</font></td><td>O(N<sup>2</sup>)</td></tr>
+<tr><td>can_convert_to</td><td>O(1)</font></td><td>O(1)</td></tr>
+<tr><td>to_number</td><td>O(N)</font></td><td>O(N)</td></tr>
+<tr><td>comparison operators</td><td>O(M)</td><td>O(M)</td></tr>
+<tr><td>abs</td><td>O(1)</font></td><td>O(1)</td></tr>
+<tr><td>pow</td><td>O(A1 * A2) <font color="#ff0000">check</font></td><td>???</td></tr>
+<tr><td>div</td><td><= O(M<sup>2</sup>) <font color="#ff0000">provide more precise info</font></td><td>O(M<sup>2</sup>)</tr>
+<tr><td>sqrt</td><td><= O(M<sup>2</sup>) <font color="#ff0000">provide more precise info</font></td><td>???</td></tr>
</table>
<h2><a name="Exceptions">Exceptions</a></h2>
@@ -507,6 +507,8 @@
the whole structure of this file on it), which was written by Paul Moore and
Daryle Walker.</p>
+<p>I shamelessly stole some data for unit tests from Big Integer Libary by Richard Peters.</p>
+
<p>Revised June 16, 2007</p>
<p>© Copyright Arseny Kapoulkine 2007. Permission to
Modified: sandbox/SOC/2007/bigint/libs/bigint/test/arithmetics.cpp
==============================================================================
--- sandbox/SOC/2007/bigint/libs/bigint/test/arithmetics.cpp (original)
+++ sandbox/SOC/2007/bigint/libs/bigint/test/arithmetics.cpp 2007-07-29 15:23:58 EDT (Sun, 29 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
@@ -50,6 +55,21 @@
// negative numbers
{"-18446744073709551615", '+', "-4", "-18446744073709551619"},
{"-4", '+', "-18446744073709551615", "-18446744073709551619"},
+ // result is zero
+ {"-18446744073709551615", '+', "18446744073709551615", "0"},
+ {"18446744073709551615", '+', "-18446744073709551615", "0"},
+
+ // from Big Integer Library by Richard Peters
+ {"144331033935567457577760483977112339622", '+', "144331033935567457577760483977112339622", "288662067871134915155520967954224679244"},
+ {"144331033935567457577760483977112339622", '+', "-201953533416687960474015014674164876681177661631133973318", "-201953533416687960329683980738597419103417177654021633696"},
+ {"144331033935567457577760483977112339622", '+', "33258231137356853400843467155353708599218251522729505441041591237", "33258231137356853400843467299684742534785709100489989418153930859"},
+ {"144331033935567457577760483977112339622", '+', "202681457102058583257910713873340545496276314517960701795263144802871633", "202681457102058583257910713873340689827310250085418279555747121915211255"},
+ {"-201953533416687960474015014674164876681177661631133973318", '+', "-201953533416687960474015014674164876681177661631133973318", "-403907066833375920948030029348329753362355323262267946636"},
+ {"-201953533416687960474015014674164876681177661631133973318", '+', "33258231137356853400843467155353708599218251522729505441041591237", "33258230935403319984155506681338693925053374841551843809907617919"},
+ {"-201953533416687960474015014674164876681177661631133973318", '+', "202681457102058583257910713873340545496276314517960701795263144802871633", "202681457102058381304377297185380071481261640353084020617601513668898315"},
+ {"33258231137356853400843467155353708599218251522729505441041591237", '+', "33258231137356853400843467155353708599218251522729505441041591237", "66516462274713706801686934310707417198436503045459010882083182474"},
+ {"33258231137356853400843467155353708599218251522729505441041591237", '+', "202681457102058583257910713873340545496276314517960701795263144802871633", "202681490360289720614764114716807700849984913736212224524768585844462870"},
+ {"202681457102058583257910713873340545496276314517960701795263144802871633", '+', "202681457102058583257910713873340545496276314517960701795263144802871633", "405362914204117166515821427746681090992552629035921403590526289605743266"},
// subtraction
@@ -65,6 +85,21 @@
// different sign, negative result
{"-239402390434", '-', "2349034", "-239404739468"},
{"239049304", '-', "39049230492304", "-39048991443000"},
+ // result is zero
+ {"-18446744073709551615", '-', "-18446744073709551615", "0"},
+ {"18446744073709551615", '-', "18446744073709551615", "0"},
+
+ // from Big Integer Library by Richard Peters
+ {"144331033935567457577760483977112339622", '-', "144331033935567457577760483977112339622", "0"},
+ {"144331033935567457577760483977112339622", '-', "-201953533416687960474015014674164876681177661631133973318", "201953533416687960618346048609732334258938145608246312940"},
+ {"144331033935567457577760483977112339622", '-', "33258231137356853400843467155353708599218251522729505441041591237", "-33258231137356853400843467011022674663650793944969021463929251615"},
+ {"144331033935567457577760483977112339622", '-', "202681457102058583257910713873340545496276314517960701795263144802871633", "-202681457102058583257910713873340401165242378950503124034779167690532011"},
+ {"-201953533416687960474015014674164876681177661631133973318", '-', "-201953533416687960474015014674164876681177661631133973318", "0"},
+ {"-201953533416687960474015014674164876681177661631133973318", '-', "33258231137356853400843467155353708599218251522729505441041591237", "-33258231339310386817531427629368723273383128203907167072175564555"},
+ {"-201953533416687960474015014674164876681177661631133973318", '-', "202681457102058583257910713873340545496276314517960701795263144802871633", "-202681457102058785211444130561301019511290988682837382972924775936844951"},
+ {"33258231137356853400843467155353708599218251522729505441041591237", '-', "33258231137356853400843467155353708599218251522729505441041591237", "0"},
+ {"33258231137356853400843467155353708599218251522729505441041591237", '-', "202681457102058583257910713873340545496276314517960701795263144802871633", "-202681423843827445901057313029873390142567715299709179065757703761280396"},
+ {"202681457102058583257910713873340545496276314517960701795263144802871633", '-', "202681457102058583257910713873340545496276314517960701795263144802871633", "0"},
// multiplication
@@ -87,6 +122,18 @@
{"-23489238492334893", '*', "-2930482394829348293489234", "68834799869735267747353413198446618041962"},
{"-39403940", '*', "-90689586573473848347384834", "3573527027965969111849451155845960"},
+ // from Big Integer Library by Richard Peters
+ {"144331033935567457577760483977112339622", '*', "144331033935567457577760483977112339622", "20831447356909925062050164636507807502299831464416847033282039093578671102884"},
+ {"144331033935567457577760483977112339622", '*', "-201953533416687960474015014674164876681177661631133973318", "-29148162284971746581373804476336682757699657139555873885010408383164260114557170019679902205796"},
+ {"144331033935567457577760483977112339622", '*', "33258231137356853400843467155353708599218251522729505441041591237", "4800194886922798289683761441724659466646965587105046561478640138067153373379183258124815665194843092414"},
+ {"144331033935567457577760483977112339622", '*', "202681457102058583257910713873340545496276314517960701795263144802871633", "29253224263107477267259633707204673908171590310734050748188031160733891198210577108075962524562010304765742726"},
+ {"-201953533416687960474015014674164876681177661631133973318", '*', "-201953533416687960474015014674164876681177661631133973318", "40785229659485300726212230220983180513132175206583821232262327224829652995464585331893205979113390672165935929124"},
+ {"-201953533416687960474015014674164876681177661631133973318", '*', "33258231137356853400843467155353708599218251522729505441041591237", "-6716617293378129327662011328220644005702996700056417620898494874171306532918252666663893949355252692095436122901020614366"},
+ {"-201953533416687960474015014674164876681177661631133973318", '*', "202681457102058583257910713873340545496276314517960701795263144802871633", "-40932236419803595447668075585915625205735648128249743480498808995089542692372861318551693654245696360311077380994768591601088294"},
+ {"33258231137356853400843467155353708599218251522729505441041591237", '*', "33258231137356853400843467155353708599218251522729505441041591237", "1106109938385852938543680427168136603410954248378521220168491554819810960946208227772891785974501289220063511976380570864995190169"},
+ {"33258231137356853400843467155353708599218251522729505441041591237", '*', "202681457102058583257910713873340545496276314517960701795263144802871633", "6740826747556542127761131910207818991713914643291451903775309886139361506308151690778975214694000820227431267338394269630916705368680021"},
+ {"202681457102058583257910713873340545496276314517960701795263144802871633", '*', "202681457102058583257910713873340545496276314517960701795263144802871633", "41079773053013613718554254944129443500101234432431175613774528976328697103926347327658851266012357988396264836364789165142640820591163076086689"},
+
// division
// zero
@@ -119,6 +166,18 @@
{"9304", '/', "-3", "-3101"},
{"394093", '/', "-11", "-35826"},
+ // from Big Integer Library by Richard Peters
+ {"144331033935567457577760483977112339622", '/', "144331033935567457577760483977112339622", "1"},
+ {"144331033935567457577760483977112339622", '/', "-201953533416687960474015014674164876681177661631133973318", "0"},
+ {"33258231137356853400843467155353708599218251522729505441041591237", '/', "144331033935567457577760483977112339622", "230430214697998061766383430"},
+ {"202681457102058583257910713873340545496276314517960701795263144802871633", '/', "144331033935567457577760483977112339622", "1404281889870892463084548210312903"},
+ {"-201953533416687960474015014674164876681177661631133973318", '/', "-201953533416687960474015014674164876681177661631133973318", "1"},
+ {"33258231137356853400843467155353708599218251522729505441041591237", '/', "-201953533416687960474015014674164876681177661631133973318", "-164682590"},
+ {"-201953533416687960474015014674164876681177661631133973318", '/', "202681457102058583257910713873340545496276314517960701795263144802871633", "0"},
+ {"33258231137356853400843467155353708599218251522729505441041591237", '/', "33258231137356853400843467155353708599218251522729505441041591237", "1"},
+ {"202681457102058583257910713873340545496276314517960701795263144802871633", '/', "33258231137356853400843467155353708599218251522729505441041591237", "6094174"},
+ {"202681457102058583257910713873340545496276314517960701795263144802871633", '/', "202681457102058583257910713873340545496276314517960701795263144802871633", "1"},
+
// modulo
// zero
@@ -134,6 +193,18 @@
{"2394023940394034", '%', "8", "2"},
{"2394023940394034", '%', "234890234034", "22675119506"},
+ // from Big Integer Library by Richard Peters
+ {"144331033935567457577760483977112339622", '%', "144331033935567457577760483977112339622", "0"},
+ {"144331033935567457577760483977112339622", '%', "-201953533416687960474015014674164876681177661631133973318", "144331033935567457577760483977112339622"},
+ {"33258231137356853400843467155353708599218251522729505441041591237", '%', "144331033935567457577760483977112339622", "24800979404810559550560636164208327777"},
+ {"202681457102058583257910713873340545496276314517960701795263144802871633", '%', "144331033935567457577760483977112339622", "57147793758571412114807420585778128967"},
+ {"-201953533416687960474015014674164876681177661631133973318", '%', "-201953533416687960474015014674164876681177661631133973318", "0"},
+ {"33258231137356853400843467155353708599218251522729505441041591237", '%', "-201953533416687960474015014674164876681177661631133973318", "194645130848165046839924230620331309955170738078042457617"},
+ {"-201953533416687960474015014674164876681177661631133973318", '%', "202681457102058583257910713873340545496276314517960701795263144802871633", "-201953533416687960474015014674164876681177661631133973318"},
+ {"33258231137356853400843467155353708599218251522729505441041591237", '%', "33258231137356853400843467155353708599218251522729505441041591237", "0"},
+ {"202681457102058583257910713873340545496276314517960701795263144802871633", '%', "33258231137356853400843467155353708599218251522729505441041591237", "9618788018540678878265330013747344025762682140703608946567718395"},
+ {"202681457102058583257910713873340545496276314517960701795263144802871633", '%', "202681457102058583257910713873340545496276314517960701795263144802871633", "0"},
+
// bit-and
// zero
@@ -215,6 +286,7 @@
{"3474347253302854482051234871283", '>', "65", "94172371000"},
// negative numbers - a >> n is equal to floor(a / 2^n) (rounding to -infinity!)
{"-1024", '>', "10", "-1"},
+ {"-1024", '>', "100", "-1"}, // sign bit!
{"-442302464", '>', "15", "-13498"},
{"-3474347253302854482051203072", '>', "65", "-94172371"},
{"-33", '>', "4", "-3"},
@@ -284,7 +356,13 @@
int test_main(int argc, char* argv[])
{
- test<boost::detail::bigint_gmp_implementation>();
+ test<boost::detail::bigint_gmp_implementation>();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 8> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 16> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 32> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 8> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 16> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 32> >();
- return 0;
+ return 0;
}
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-29 15:23:58 EDT (Sun, 29 Jul 2007)
@@ -153,9 +153,13 @@
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> >();
+ test<boost::detail::bigint_gmp_implementation>();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 8> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 16> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 32> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 8> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 16> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 32> >();
- return 0;
+ 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-29 15:23:58 EDT (Sun, 29 Jul 2007)
@@ -299,9 +299,13 @@
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> >();
+ test<boost::detail::bigint_gmp_implementation>();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 8> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 16> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 32> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 8> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 16> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 32> >();
- return 0;
+ return 0;
}
Modified: sandbox/SOC/2007/bigint/libs/bigint/test/functions.cpp
==============================================================================
--- sandbox/SOC/2007/bigint/libs/bigint/test/functions.cpp (original)
+++ sandbox/SOC/2007/bigint/libs/bigint/test/functions.cpp 2007-07-29 15:23:58 EDT (Sun, 29 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")
#define ARRAY_SIZE(array) sizeof(array) / sizeof(array[0])
@@ -108,7 +113,7 @@
BOOST_CHECK_EQUAL(rem, number(e.rem));
}
}
-
+
// sqrt
{
// zero
@@ -132,7 +137,13 @@
int test_main(int argc, char* argv[])
{
- test<boost::detail::bigint_gmp_implementation>();
+ test<boost::detail::bigint_gmp_implementation>();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 8> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 16> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 32> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 8> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 16> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 32> >();
- return 0;
+ 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-29 15:23:58 EDT (Sun, 29 Jul 2007)
@@ -147,9 +147,13 @@
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> >();
+ test<boost::detail::bigint_gmp_implementation>();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 8> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 16> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 32> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 8> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 16> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 32> >();
- return 0;
+ return 0;
}
Modified: sandbox/SOC/2007/bigint/libs/bigint/test/serialization.cpp
==============================================================================
--- sandbox/SOC/2007/bigint/libs/bigint/test/serialization.cpp (original)
+++ sandbox/SOC/2007/bigint/libs/bigint/test/serialization.cpp 2007-07-29 15:23:58 EDT (Sun, 29 Jul 2007)
@@ -64,9 +64,13 @@
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> >();
+ test<boost::detail::bigint_gmp_implementation>();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 8> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 16> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 32> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 8> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 16> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 32> >();
- return 0;
+ 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-29 15:23:58 EDT (Sun, 29 Jul 2007)
@@ -283,9 +283,13 @@
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> >();
+ test<boost::detail::bigint_gmp_implementation>();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 8> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 16> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 32> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 8> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 16> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 32> >();
- return 0;
+ 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-29 15:23:58 EDT (Sun, 29 Jul 2007)
@@ -86,7 +86,10 @@
{-10, "ABCDEF", 0, 0},
{-10, "\xff", 0, 0},
// handling non-ASCII symbols
- {-36, "sa3mx\xa3\xb3", 47500521, 0}
+ {-36, "sa3mx\xa3\xb3", 47500521, 0},
+
+ // check full alphabet
+ {36, "abcdefghijklmnopqrstuvwxyz1234567890", 0, "30483235087530204251026473460499750369628113087340027780"}
};
for (size_t i = 0; i < ARRAY_SIZE(entries); ++i)
@@ -114,9 +117,13 @@
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> >();
+ test<boost::detail::bigint_gmp_implementation>();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 8> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 16> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 32> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 8> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 16> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 32> >();
- return 0;
+ 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-29 15:23:58 EDT (Sun, 29 Jul 2007)
@@ -103,9 +103,13 @@
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> >();
+ test<boost::detail::bigint_gmp_implementation>();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 8> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 16> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 32> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 8> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 16> >();
+ test<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_fixed<1024>::type, 32> >();
- return 0;
+ 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-29 15:23:58 EDT (Sun, 29 Jul 2007)
@@ -225,23 +225,29 @@
+ multiplication (*)
Status: implemented
-- bitwise shifts (<<, >>)
-Status: needs implementing
++ bitwise shifts (<<, >>)
+Status: implemented
-- division (/, %, div function)
-Status: needs implementing
++ pow function
+Status: implemented
-- sqrt function
-Status: needs implementing
++ sqrt function
+Status: implemented
-- pow function
-Status: needs implementing
++ division (/, %, div function)
+Status: implemented
-- make implementation parametrizable by config structure, make a default structure
-Status: needs implementing
++ make implementation parametrizable by config structure, make a default structure
+Status: implemented
-- add limb=unsigned char, limb=unsigned short tests
-Status: needs implementing
++ add limb=unsigned char, limb=unsigned short tests
+Status: implemented
+
++ fix bug with bitwise operations for negative numbers
+Status: fixed
+
++ optimize string conversion
+Status: implemented; 6x speedup for fibonacci(10^6)
-----------------------------------------------
@@ -256,6 +262,9 @@
Alternatively, only parts of GMP that actually are not exception safe may be rewritten (if they do not include system layer
(mpn), of course).
+28.07.07. Further research showed that limb allocation in system layer (mpn) occurs for multiplication (Toom-3 and FFT),
+string <-> number conversions, division, sqrt, and perhaps somewhere else :(
+
-----------------------------------------------
Extra features:
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