|
|
Boost-Commit : |
From: zeux_at_[hidden]
Date: 2007-06-07 13:09:56
Author: zeux
Date: 2007-06-07 13:09:53 EDT (Thu, 07 Jun 2007)
New Revision: 4483
URL: http://svn.boost.org/trac/boost/changeset/4483
Log:
Removed bigint_simple_test, implemented arithmetics test, fixed division and modulo
Added:
sandbox/SOC/2007/bigint/libs/bigint/test/arithmetics.cpp
Removed:
sandbox/SOC/2007/bigint/libs/bigint/test/bigint_simple_test.cpp
Text files modified:
sandbox/SOC/2007/bigint/boost/bigint/bigint_gmp.hpp | 4 ++--
sandbox/SOC/2007/bigint/libs/bigint/test/Jamfile.v2 | 2 +-
sandbox/SOC/2007/bigint/libs/bigint/todo.txt | 17 ++++++++++-------
3 files changed, 13 insertions(+), 10 deletions(-)
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-06-07 13:09:53 EDT (Thu, 07 Jun 2007)
@@ -182,12 +182,12 @@
void div(const bigint_gmp_implementation& lhs, const bigint_gmp_implementation& rhs)
{
- mpz_div(data, lhs.data, rhs.data);
+ mpz_tdiv_q(data, lhs.data, rhs.data);
}
void mod(const bigint_gmp_implementation& lhs, const bigint_gmp_implementation& rhs)
{
- mpz_mod(data, lhs.data, rhs.data);
+ mpz_tdiv_r(data, lhs.data, rhs.data);
}
void or_(const bigint_gmp_implementation& lhs, const bigint_gmp_implementation& rhs)
Modified: sandbox/SOC/2007/bigint/libs/bigint/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2007/bigint/libs/bigint/test/Jamfile.v2 (original)
+++ sandbox/SOC/2007/bigint/libs/bigint/test/Jamfile.v2 2007-06-07 13:09:53 EDT (Thu, 07 Jun 2007)
@@ -9,10 +9,10 @@
{
test-suite bigint
:
- [ run bigint_simple_test.cpp ]
[ run number_conversion.cpp ]
[ run string_conversion.cpp ]
[ run can_convert_to.cpp ]
+ [ run arithmetics.cpp ]
;
}
Added: sandbox/SOC/2007/bigint/libs/bigint/test/arithmetics.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/test/arithmetics.cpp 2007-06-07 13:09:53 EDT (Thu, 07 Jun 2007)
@@ -0,0 +1,186 @@
+/* Boost arithmetics.cpp test 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)
+ */
+
+#define BOOST_DISABLE_WIN32
+
+#include <boost/test/included/test_exec_monitor.hpp>
+
+#include <boost/bigint/bigint.hpp>
+
+#include <sstream>
+
+#include <iostream>
+
+#pragma comment(lib, "libgmp-3.lib")
+
+// This macro is not quite good, but - it's ok for our needs
+#define ARRAY_SIZE(array) sizeof(array) / sizeof(array[0])
+
+template <typename I> void test()
+{
+ typedef boost::bigint_base<I> number;
+
+ struct test_entry
+ {
+ const char* lhs;
+ char op;
+ const char* rhs;
+ const char* result;
+ };
+
+ test_entry entries[] =
+ {
+ // addition
+
+ // same sign, no carries
+ {"3", '+', "1", "4"},
+ {"1", '+', "3", "4"},
+ // same sign, carries
+ {"18446744073709551615", '+', "1", "18446744073709551616"},
+ {"1", '+', "18446744073709551615", "18446744073709551616"},
+ {"18446744073709551615", '+', "18446744073709551615", "36893488147419103230"},
+ // different sign, positive result
+ {"138493849343434", '+', "-128932839", "138493720410595"},
+ {"-128932839", '+', "138493849343434", "138493720410595"},
+ // different sign, negative result
+ {"-2903920392323129", '+', "5293092323", "-2903915099230806"},
+ {"5293092323", '+', "-2903920392323129", "-2903915099230806"},
+ // negative numbers
+ {"-18446744073709551615", '+', "-4", "-18446744073709551619"},
+ {"-4", '+', "-18446744073709551615", "-18446744073709551619"},
+
+ // subtraction
+
+ // same sign, no borrows
+ {"3", '-', "1", "2"},
+ {"-39043434", '-', "-599509", "-38443925"},
+ // same sign, borrows
+ {"3", '-', "4", "-1"},
+ {"-39043434304928394", '-', "-523243892384923499509", "523204848950618571115"},
+ // different sign, positive result
+ {"2390492304934", '-', "-2342930493043943434", "2342932883536248368"},
+ {"123940", '-', "-1003", "124943"},
+ // different sign, negative result
+ {"-239402390434", '-', "2349034", "-239404739468"},
+ {"239049304", '-', "39049230492304", "-39048991443000"},
+
+ // multiplication
+
+ // zero
+ {"234902394023940234", '*', "0", "0"},
+ {"0", '*', "234902394023940234", "0"},
+ // positive * positive
+ {"2389428394283434234234", '*', "895489472863784783", "2139707973242632227811083664960586861222"},
+ {"895489472863784783", '*', "2389428394283434234234", "2139707973242632227811083664960586861222"},
+ // different magnitudes
+ {"2384", '*', "2389428349283942034234", "5696397184692917809613856"},
+ {"2389428349283942034234", '*', "2384", "5696397184692917809613856"},
+ // 10^n
+ {"1000000000000000", '*', "100000000", "100000000000000000000000"},
+ {"10000", '*', "10000000000000000000", "100000000000000000000000"},
+ // different signs
+ {"123940932409302930429304", '*', "-23940239409234", "-2967175594482401511466585794961793136"},
+ {"-4895849540949", '*', "5906390354334334989", "-28916798504933355408364838964561"},
+ // negative * negative
+ {"-23489238492334893", '*', "-2930482394829348293489234", "68834799869735267747353413198446618041962"},
+ {"-39403940", '*', "-90689586573473848347384834", "3573527027965969111849451155845960"},
+
+ // division
+
+ // zero
+ {"0", '/', "23904293402394023940", "0"},
+ // positive / larger positive
+ {"239409034", '/', "23489023049230492304230493049034", "0"},
+ {"-239409034", '/', "23489023049230492304230493049034", "0"},
+ {"239409034", '/', "-23489023049230492304230493049034", "0"},
+ // ~ equal magnitudes
+ {"39049204923049203490234", '/', "39049204923049203490230", "1"},
+ {"-39049204923049203490234", '/', "39049204923049203490230", "-1"},
+ {"39049204923049203490234", '/', "-39049204923049203490230", "-1"},
+ // some other numbers
+ {"13940239402394034213904", '/', "49850", "279643719205497175"},
+ {"-9049594859482398349", '/', "-3401", "2660862940159482"},
+ // proper rounding for positive numbers
+ {"3", '/', "2", "1"},
+ {"9304", '/', "3", "3101"},
+ {"394093", '/', "11", "35826"},
+ // proper rounding for positive results (negative numbers)
+ {"-3", '/', "-2", "1"},
+ {"-9304", '/', "-3", "3101"},
+ {"-394093", '/', "-11", "35826"},
+ // proper rounding for positive / negative (towards zero)
+ {"-3", '/', "2", "-1"},
+ {"-9304", '/', "3", "-3101"},
+ {"-394093", '/', "11", "-35826"},
+ // proper rounding for negative / positive (towards zero)
+ {"3", '/', "-2", "-1"},
+ {"9304", '/', "-3", "-3101"},
+ {"394093", '/', "-11", "-35826"},
+
+ // modulo
+
+ // zero
+ {"0", '%', "134", "0"},
+ // sign of the left hand value has to be equal to the sign of the remainder
+ {"34", '%', "5", "4"},
+ {"34", '%', "-5", "4"},
+ {"-34", '%', "5", "-4"},
+ {"-34", '%', "-5", "-4"},
+ // some other numbers
+ {"2394023940394034", '%', "100", "34"},
+ {"2394023940394034", '%', "9", "5"},
+ {"2394023940394034", '%', "8", "2"},
+ {"2394023940394034", '%', "234890234034", "22675119506"},
+ };
+
+ for (size_t i = 0; i < ARRAY_SIZE(entries); ++i)
+ {
+ const test_entry& e = entries[i];
+
+ number a(e.lhs), b(e.rhs), c(e.result);
+
+#define GEN_OP(op, chop) case chop: \
+ { \
+ BOOST_CHECK_EQUAL(a op b, c); \
+ \
+ number d = a; \
+ d op##= b; \
+ \
+ BOOST_CHECK_EQUAL(d, c); \
+ \
+ if (a.can_convert_to<boost::int64_t>()) \
+ { \
+ BOOST_CHECK_EQUAL(a.to_number<boost::int64_t>() op b, c); \
+ } \
+ \
+ if (b.can_convert_to<boost::int64_t>()) \
+ { \
+ BOOST_CHECK_EQUAL(a op b.to_number<boost::int64_t>(), c); \
+ } \
+ } break
+
+ switch (e.op)
+ {
+ GEN_OP(+, '+');
+ GEN_OP(-, '-');
+ GEN_OP(*, '*');
+ GEN_OP(/, '/');
+ GEN_OP(%, '%');
+ }
+
+#undef GEN_OP
+ }
+}
+
+int test_main(int argc, char* argv[])
+{
+ test<boost::detail::bigint_gmp_implementation>();
+
+ return 0;
+}
Deleted: sandbox/SOC/2007/bigint/libs/bigint/test/bigint_simple_test.cpp
==============================================================================
--- sandbox/SOC/2007/bigint/libs/bigint/test/bigint_simple_test.cpp 2007-06-07 13:09:53 EDT (Thu, 07 Jun 2007)
+++ (empty file)
@@ -1,137 +0,0 @@
-/* Boost bigint_simple_test.cpp test 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)
- */
-
-#define BOOST_DISABLE_WIN32
-
-#include <boost/test/included/test_exec_monitor.hpp>
-
-#include <boost/bigint/bigint.hpp>
-
-#include <sstream>
-
-#pragma comment(lib, "libgmp-3.lib")
-
-void test()
-{
- using boost::bigint;
-
- bigint d = 1;
- d += 4;
-
- d = d + 4;
- d = d + bigint(4);
-
- bigint a = bigint("13849832498234928394234");
- bigint b = bigint("86150167501765071605765");
-
- bigint c = a + b;
-
- BOOST_CHECK_EQUAL(c++, bigint("99999999999999999999999"));
- BOOST_CHECK_EQUAL(c, bigint("100000000000000000000000"));
-
- b %= a;
-
- BOOST_CHECK_EQUAL(!(a / b), false);
- BOOST_CHECK(a);
-
- BOOST_CHECK_EQUAL(a * b, bigint("42258228219342334666689684483132205000478474"));
- BOOST_CHECK_EQUAL(!(a / b), false);
- BOOST_CHECK_EQUAL(a % b, bigint("1645142448812923432790"));
-
- BOOST_CHECK_EQUAL(a | b, bigint("13870766920526448295931"));
- BOOST_CHECK_EQUAL(a & b, bigint("3030238090063981338664"));
- BOOST_CHECK_EQUAL(a ^ b, bigint("10840528830462466957267"));
-
- BOOST_CHECK_EQUAL(a << 12323, bigint("54210209824998674960706151957171243776334817615992549286033832481286245106274830183430035889395592421429139828952807123487077092054006867964850440524460972559587769408718171158946497028119023782272098259724152691027872962733955514126021668316226079027055513323024368575084988607770611282498269102675003254352062804123613103837221987914939902110340739604264343039365892061448818559397135613345306938522003803494120751512279929368262990664328617120718740461624884548210663403481351798397716730743376547281832957722999748874728361670364167061164659574539537090121176058332274255169884200640406996554466588956804941503716387500495829665315052731815607862789692277641335464325322615767195011146302817172252379961868212588242741947065364583568723291471751004963530907347999874193186816934579353181408041195080801229409434080706121573961587551916571167934706798462022309293903657749708884314025294000029436115635836381878774958815264983930841350011810794735656320381551019972503379916134197
039200013499971564803048001762960809164762637488021962891398097772313146888407589383735998154442192501165230754898274044006394361249836440929908647042463530462376928313533941666423346007473304923333190289810516791325668708180010939837790292671875407855673469398330145542063611309681313256360971034826170030180373909291169403509612303609989577949821249028435431979570734248293804686082931379639847711011932132921366544233487956494759945107399072700832945099061491784643683597456599800868407795111393137978610252558272046172738440958307179817823202293493567043148504408225728052354115585270281805052806542365810126131655357464895619002653633526617201837910067434195719328525341908783221901491136694060142051394957465738922756111915452802175945697390517424975816802227286258530895733377835898716687001920198998468448201430847634183837881878233754975458803985499341847677648819159077378693806478606120472192735237308089844393639932283785281168904446541985039131642002762335681598179424992803731329137148115030753206917272155723
670778142387185554420058265251870684011332123183650190995767874298206358606115242964147204963162126201886987891018787690434308236836499346656790213359159875159742564637898659613474209293887654355046009422058758292733785348269613356005926577170575989471100266260931914619468078598688997277906838153589503330900090781191812549674167934726480016569418226786749589167504064797728919100656717692969146379870286429802144638044650704314051117635702178907751971885034427049357891080670830078569333035533221376988439363681737385900027509595782280132585647042001663149723427627146024591594850135672147437314944517409695158803844637284046910988011470139667877464442515550125392919619816954413530833557977515808716337194728187777533124153821521284321968370402360778685298742203233491005298326645715923174261708156503501100450193594239326592705866222831356815212029165638741358913759743650671492153263000348503637918221175355027474631738752349630470314508900772920786507743346507015132846776261173136038012599265553669061110476098772194
7987651052200490474467685344315603511565148128907900886854643373305490827988832857965982489788282339573097276547608904545269820140608635061243211688508065865415564489887520878115786887330460859916782610805213428984931292958242857552508803483374776140927180323134713226342853874523978900371318863698471909861423140464604309269071265335210720089276101171746349379219156670536008796216903162551900000164124244707346775377306633500136743133402111070612007697383513998143624055526721057240426797375334222177746493729517389043488959509605784317189782088070297384587362776609016571148764168858304798093182811678055912813300404454752102341916041445631171769468296541125975611633951795548330426208740683150262272"));
- BOOST_CHECK_EQUAL(a >> 34783, 0);
-
- BOOST_CHECK_EQUAL(b, bigint("3051172512355501240361"));
-
- BOOST_CHECK_EQUAL(sqrt(b), bigint("55237419493"));
-
- BOOST_CHECK_EQUAL(b.can_convert_to<short>(), false);
-
- boost::uint64_t ee = 0xffffffff;
- bigint e = bigint(ee + 1);
-
- bigint f = ee;
-
- BOOST_CHECK_EQUAL(e, bigint("4294967296"));
-
- unsigned short xx = 34;
- bigint g = xx;
-
- BOOST_CHECK_EQUAL(bigint(L"11011101", 2), bigint("221"));
- BOOST_CHECK_EQUAL(bigint("fF", 16), bigint("255"));
-
- BOOST_CHECK_EQUAL(bigint("5").str(2), "101");
- BOOST_CHECK(bigint("5").wstr(2) == L"101"); // if we use BOOST_CHECK_EQUAL here it complains about not being able to print log value
-
- std::ostringstream oss;
- oss << std::dec << bigint(10) << std::hex << bigint(10) << std::oct << bigint(10);
-
- BOOST_CHECK_EQUAL(oss.str(), "10a12");
-
- // can_convert_to
- BOOST_CHECK( bigint("127").can_convert_to<char>());
- BOOST_CHECK(!bigint("128").can_convert_to<char>());
- BOOST_CHECK(!bigint("129").can_convert_to<char>());
-
- BOOST_CHECK( bigint("-127").can_convert_to<char>());
- BOOST_CHECK( bigint("-128").can_convert_to<char>());
- BOOST_CHECK(!bigint("-129").can_convert_to<char>());
-
- BOOST_CHECK( bigint("127").can_convert_to<unsigned char>());
- BOOST_CHECK( bigint("128").can_convert_to<unsigned char>());
- BOOST_CHECK( bigint("129").can_convert_to<unsigned char>());
-
- BOOST_CHECK( bigint("255").can_convert_to<unsigned char>());
- BOOST_CHECK(!bigint("256").can_convert_to<unsigned char>());
-
- BOOST_CHECK( bigint("ffffffff", 16).can_convert_to<unsigned int>());
- BOOST_CHECK(!bigint("100000000", 16).can_convert_to<unsigned int>());
-
- BOOST_CHECK( bigint("7fffffff", 16).can_convert_to<int>());
- BOOST_CHECK(!bigint("80000000", 16).can_convert_to<int>());
-
- BOOST_CHECK( bigint("-7fffffff", 16).can_convert_to<int>());
- BOOST_CHECK( bigint("-80000000", 16).can_convert_to<int>());
- BOOST_CHECK(!bigint("-80000001", 16).can_convert_to<int>());
-
- BOOST_CHECK( bigint("ffffffff", 16).can_convert_to<boost::uint64_t>());
- BOOST_CHECK( bigint("100000000", 16).can_convert_to<boost::uint64_t>());
-
- BOOST_CHECK( bigint("7fffffff", 16).can_convert_to<boost::int64_t>());
- BOOST_CHECK( bigint("80000000", 16).can_convert_to<boost::int64_t>());
-
- BOOST_CHECK( bigint("-7fffffff", 16).can_convert_to<boost::int64_t>());
- BOOST_CHECK( bigint("-80000000", 16).can_convert_to<boost::int64_t>());
- BOOST_CHECK( bigint("-80000001", 16).can_convert_to<boost::int64_t>());
-
- BOOST_CHECK_EQUAL(bigint("ffffffff", 16).to_number<unsigned int>(), 0xffffffff);
- BOOST_CHECK_EQUAL(bigint("7fffffff", 16).to_number<int>(), 0x7fffffff);
- BOOST_CHECK_EQUAL(bigint("-80000000", 16).to_number<int>(), -static_cast<boost::int64_t>(0x80000000));
-
- // 3 == 11
- // -3 = 1....1101
- // 0...01101
- BOOST_CHECK_EQUAL((bigint("-3") | bigint("1101", 2)).str(2), "-11");
- BOOST_CHECK_EQUAL((bigint("-3") & bigint("1101", 2)).str(2), "1101");
- BOOST_CHECK_EQUAL((bigint("-3") ^ bigint("1101", 2)).str(2), "-10000");
-
- BOOST_CHECK_EQUAL(bigint("-1") << 5, -32);
- BOOST_CHECK_EQUAL(bigint("-33") >> 3, -5); // 33 is 100001, -33 is 1....1011111, >>3 is 1...1011, which is complement for 101
-}
-
-int test_main( int argc, char* argv[] )
-{
- test();
-
- 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-06-07 13:09:53 EDT (Thu, 07 Jun 2007)
@@ -45,9 +45,6 @@
+ extend implementation interface for efficient operator!() and safe bool
Status: implemented
-* make sure it works on a wide range of compilers (test framework setup is needed)
-Status: made some setup, it works for me but: 1. linking gmp is done via a hack, 2. not sure it works for others :/
-
+ converting to/from string - there was a suggestion to use static functions
My opinion: performance wise it is the same if compiler has NRVO support, and ctors/member functions are more convenient
Status: leaving it as is for now. Changing it later it trivial anyway.
@@ -59,6 +56,9 @@
+ remove warnings for both MSVC and GCC
Status: all non-GMP-implementation-specific warnings were fixed
+* make sure it works on a wide range of compilers (test framework setup is needed)
+Status: made some setup, it works for me but: 1. linking gmp is done via a hack, 2. not sure it works for others :/
+
2. GMP implementation
+ conversion from string with different bases (2-36, use 26 letters + 10 digits)
@@ -97,6 +97,9 @@
+ fix bug in can_convert_to() - fails for boundary case (-2^63-1) for boost::int64_t
Status: fixed
++ fix division and remainder to truncating ones
+Status: fixed
+
- remove warnings for both MSVC and GCC
Status: needs fixing
@@ -117,11 +120,11 @@
+ test to_number (char, short, int, int64 - both signed and unsigned, boundary cases)
Status: implemented
-- test copy construction and assignment
-Status: needs implementing
+* test copy construction and assignment
+Status: it's all over the place, no additional test needed
-- test basic arithmetics and modulo (both op= and op) - bigint op/= bigint, bigint op/= number, number op bigint
-Status: needs implementing
++ test basic arithmetics and modulo (both op= and op) - bigint op/= bigint, bigint op/= number, number op bigint
+Status: implemented
- test bit arithmetics - bigint op/= bigint, bigint op/= number, number op bigint (except << and >>)
Status: needs implementing
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