From: arseny.kapoulkine_at_[hidden]
Date: 2007-08-19 14:28:55
Author: zeux
Date: 2007-08-19 14:28:53 EDT (Sun, 19 Aug 2007)
New Revision: 38767
URL: http://svn.boost.org/trac/boost/changeset/38767
Log:
Performance test suite
Added:
sandbox/SOC/2007/bigint/libs/bigint/perf-test/
sandbox/SOC/2007/bigint/libs/bigint/perf-test/impl_aors.inl (contents, props changed)
sandbox/SOC/2007/bigint/libs/bigint/perf-test/impl_bitwise.inl (contents, props changed)
sandbox/SOC/2007/bigint/libs/bigint/perf-test/impl_moddiv.inl (contents, props changed)
sandbox/SOC/2007/bigint/libs/bigint/perf-test/main.cpp (contents, props changed)
sandbox/SOC/2007/bigint/libs/bigint/perf-test/match.hpp (contents, props changed)
sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_add.inl (contents, props changed)
sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_and.inl (contents, props changed)
sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_div.inl (contents, props changed)
sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_fib.inl (contents, props changed)
sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_from_string.inl (contents, props changed)
sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_gcd.inl (contents, props changed)
sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_isprime.inl (contents, props changed)
sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_lshift.inl (contents, props changed)
sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_mod.inl (contents, props changed)
sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_mul.inl (contents, props changed)
sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_or.inl (contents, props changed)
sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_rshift.inl (contents, props changed)
sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_sqrt.inl (contents, props changed)
sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_sub.inl (contents, props changed)
sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_to_string.inl (contents, props changed)
sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_xor.inl (contents, props changed)
Added: sandbox/SOC/2007/bigint/libs/bigint/perf-test/impl_aors.inl
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/perf-test/impl_aors.inl 2007-08-19 14:28:53 EDT (Sun, 19 Aug 2007)
@@ -0,0 +1,46 @@
+/* Boost impl_aors.inl 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)
+ */
+
+template <typename number> struct TEST_AORS_SMALL
+{
+ number a, b;
+
+ TEST_AORS_SMALL()
+ {
+ a = 23943;
+ b = 39048;
+ }
+
+ void run()
+ {
+ for (int i = 0; i < 10000000; ++i)
+ {
+ a AORS_OP b;
+ }
+ }
+};
+
+template <typename number> struct TEST_AORS_LARGE
+{
+ number a, b;
+
+ TEST_AORS_LARGE()
+ {
+ a = pow(number("2394823409283409273487324"), 100);
+ b = pow(number("9203402349384209348209234"), 100);
+ }
+
+ void run()
+ {
+ for (int i = 0; i < 500000; ++i)
+ {
+ a AORS_OP b;
+ }
+ }
+};
Added: sandbox/SOC/2007/bigint/libs/bigint/perf-test/impl_bitwise.inl
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/perf-test/impl_bitwise.inl 2007-08-19 14:28:53 EDT (Sun, 19 Aug 2007)
@@ -0,0 +1,50 @@
+/* Boost impl_bitwise.inl 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)
+ */
+
+template <typename number> struct TEST_BITWISE_SMALL
+{
+ number a, b;
+
+ TEST_BITWISE_SMALL()
+ {
+ a = 23943;
+ b = 39048;
+ }
+
+ void run()
+ {
+ number c;
+
+ for (int i = 0; i < 1500000; ++i)
+ {
+ c = a BITWISE_OP b;
+ }
+ }
+};
+
+template <typename number> struct TEST_BITWISE_LARGE
+{
+ number a, b;
+
+ TEST_BITWISE_LARGE()
+ {
+ a = pow(number("2394823409283409273487324"), 50000);
+ b = pow(number("9203402349384209348209234"), 50000);
+ }
+
+ void run()
+ {
+ number c;
+
+ for (int i = 0; i < 300; ++i)
+ {
+ c = a BITWISE_OP b;
+ }
+ }
+};
Added: sandbox/SOC/2007/bigint/libs/bigint/perf-test/impl_moddiv.inl
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/perf-test/impl_moddiv.inl 2007-08-19 14:28:53 EDT (Sun, 19 Aug 2007)
@@ -0,0 +1,50 @@
+/* Boost impl_moddiv.inl 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)
+ */
+
+template <typename number> struct TEST_MODDIV_SMALL
+{
+ number a, b;
+
+ TEST_MODDIV_SMALL()
+ {
+ a = 3239443;
+ b = 39048;
+ }
+
+ void run()
+ {
+ number c;
+
+ for (int i = 0; i < 500000; ++i)
+ {
+ c = a MODDIV_OP b;
+ }
+ }
+};
+
+template <typename number> struct TEST_MODDIV_MEDIUM
+{
+ number a, b;
+
+ TEST_MODDIV_MEDIUM()
+ {
+ a = pow(number("2394823409283409273487324"), 100);
+ b = pow(number("9203402349384209348209234"), 50);
+ }
+
+ void run()
+ {
+ number c;
+
+ for (int i = 0; i < 500; ++i)
+ {
+ c = a MODDIV_OP b;
+ }
+ }
+};
Added: sandbox/SOC/2007/bigint/libs/bigint/perf-test/main.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/perf-test/main.cpp 2007-08-19 14:28:53 EDT (Sun, 19 Aug 2007)
@@ -0,0 +1,349 @@
+#include <iostream>
+#include <ctime>
+#include <vector>
+#include <set>
+
+#include <boost/bigint/bigint.hpp>
+
+#ifdef BOOST_BIGINT_HAS_GMP_SUPPORT
+# include <boost/bigint/bigint_gmp.hpp>
+#endif
+
+#include <boost/bigint/bigint_default.hpp>
+#include <boost/bigint/bigint_storage_vector.hpp>
+#include <boost/bigint/bigint_storage_fixed.hpp>
+
+#include "match.hpp"
+
+#include "test_add.inl"
+#include "test_sub.inl"
+
+#include "test_mul.inl"
+#include "test_div.inl"
+#include "test_mod.inl"
+
+#include "test_and.inl"
+#include "test_or.inl"
+#include "test_xor.inl"
+
+#include "test_lshift.inl"
+#include "test_rshift.inl"
+
+#include "test_sqrt.inl"
+
+#include "test_to_string.inl"
+#include "test_from_string.inl"
+
+#include "test_fib.inl"
+#include "test_isprime.inl"
+#include "test_gcd.inl"
+
+enum output_type
+{
+ ot_none,
+ ot_csv,
+ ot_html,
+ ot_list_tests,
+ ot_list_implementations
+};
+
+class performance_tool
+{
+ const char* test_mask;
+ const char* impl_mask;
+ output_type output;
+
+ std::vector<std::vector<std::pair<const char*, float> > > results;
+ std::vector<const char*> impls;
+
+ std::vector<std::pair<const char*, float> >* impl_results;
+
+ template <typename impl, template <class> class test> void run_test(const char* impl_name, const char* test_name)
+ {
+ if (output == ot_list_tests)
+ {
+ std::cout << test_name << std::endl;
+ return;
+ }
+
+ if (match(test_name, test_mask))
+ {
+ std::clog << "Running " << test_name << "/" << impl_name << "..." << std::endl;
+
+ test<boost::bigint_base<impl> > t;
+
+ clock_t start = clock();
+ t.run();
+ clock_t end = clock();
+
+ impl_results->push_back(std::make_pair(test_name, float(end-start)/CLOCKS_PER_SEC));
+ }
+ }
+
+ template <typename impl> void run_impl(const char* impl_name)
+ {
+ if (output == ot_list_implementations)
+ {
+ std::cout << impl_name << std::endl;
+ return;
+ }
+
+ if (match(impl_name, impl_mask))
+ {
+ impls.push_back(impl_name);
+
+ results.push_back(std::vector<std::pair<const char*, float> >());
+ impl_results = &results.back();
+
+ // test_add.inl
+ run_test<impl, test_add_small>(impl_name, "add_small");
+ run_test<impl, test_add_large>(impl_name, "add_large");
+
+ // test_sub.inl
+ run_test<impl, test_sub_small>(impl_name, "sub_small");
+ run_test<impl, test_sub_large>(impl_name, "sub_large");
+
+ // test_mul.inl
+ run_test<impl, test_mul_small>(impl_name, "mul_small");
+ run_test<impl, test_mul_medium>(impl_name, "mul_medium");
+ run_test<impl, test_mul_large>(impl_name, "mul_large");
+
+ // test_div.inl
+ run_test<impl, test_div_small>(impl_name, "div_small");
+ run_test<impl, test_div_medium>(impl_name, "div_medium");
+
+ // test_mod.inl
+ run_test<impl, test_mod_small>(impl_name, "mod_small");
+ run_test<impl, test_mod_medium>(impl_name, "mod_medium");
+
+ // test_and.inl
+ run_test<impl, test_and_small>(impl_name, "and_small");
+ run_test<impl, test_and_large>(impl_name, "and_large");
+
+ // test_or.inl
+ run_test<impl, test_or_small>(impl_name, "or_small");
+ run_test<impl, test_or_large>(impl_name, "or_large");
+
+ // test_xor.inl
+ run_test<impl, test_xor_small>(impl_name, "xor_small");
+ run_test<impl, test_xor_large>(impl_name, "xor_large");
+
+ // test_lshift.inl
+ run_test<impl, test_lshift_small>(impl_name, "lshift_small");
+ run_test<impl, test_lshift_large>(impl_name, "lshift_large");
+ run_test<impl, test_lshift_exact>(impl_name, "lshift_exact");
+
+ // test_rshift.inl
+ run_test<impl, test_rshift_small>(impl_name, "rshift_small");
+ run_test<impl, test_rshift_large>(impl_name, "rshift_large");
+ run_test<impl, test_rshift_exact>(impl_name, "rshift_exact");
+
+ // test_sqrt.inl
+ run_test<impl, test_sqrt_small>(impl_name, "sqrt_small");
+ run_test<impl, test_sqrt_medium>(impl_name, "sqrt_medium");
+
+ // test_to_string.inl
+ run_test<impl, test_to_string_small>(impl_name, "to_string_small");
+ run_test<impl, test_to_string_medium>(impl_name, "to_string_medium");
+
+ // test_from_string.inl
+ run_test<impl, test_from_string_small>(impl_name, "from_string_small");
+ run_test<impl, test_from_string_medium>(impl_name, "from_string_medium");
+
+ // test_fib.inl
+ run_test<impl, test_fib_small>(impl_name, "fib_small");
+ run_test<impl, test_fib_large>(impl_name, "fib_large");
+
+ // test_isprime.inl
+ run_test<impl, test_isprime_small>(impl_name, "isprime_small");
+ run_test<impl, test_isprime_medium>(impl_name, "isprime_medium");
+
+ // test_gcd.inl
+ run_test<impl, test_gcd_small>(impl_name, "gcd_small");
+ run_test<impl, test_gcd_medium>(impl_name, "gcd_medium");
+
+ impl_results = 0;
+ }
+ }
+
+public:
+ performance_tool(const char* test, const char* impl, output_type out): test_mask(test), impl_mask(impl), output(out), impl_results(0)
+ {
+ if (output == ot_list_implementations)
+ {
+ std::cout << "Available implementations:" << std::endl;
+ }
+
+ if (output == ot_list_tests)
+ {
+ std::cout << "Available tests:" << std::endl;
+ }
+ }
+
+ void run()
+ {
+ if (output == ot_list_tests)
+ {
+ impl_mask = "default_32";
+ run_impl<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 32> >("default_32");
+ return;
+ }
+
+#ifdef BOOST_BIGINT_HAS_GMP_SUPPORT
+ run_impl<boost::detail::bigint_gmp_implementation>("gmp");
+#endif
+
+ run_impl<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 8> >("default_8");
+ run_impl<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 16> >("default_16");
+ run_impl<boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 32> >("default_32");
+ }
+
+ ~performance_tool()
+ {
+ if (output == ot_csv)
+ {
+ for (size_t i = 0; i < impls.size(); ++i)
+ std::cout << ", " << impls[i];
+
+ std::cout << std::endl;
+ }
+ else if (output == ot_html)
+ {
+ std::cout << "<html><head><title>Performance test results</title></head><body>\n";
+ std::cout << "<h1>Performance tests results (test mask = " << test_mask << ", implementation mask = " << impl_mask << ")</h1>\n";
+ std::cout << "<table border=1 cellspacing=0>\n";
+ std::cout << "<tr><td></td>";
+
+ for (size_t i = 0; i < impls.size(); ++i)
+ std::cout << "<th>" << impls[i] << "</th>";
+
+ std::cout << "</tr>\n";
+ }
+
+ std::set<std::string> tests_avail;
+ std::vector<std::string> tests;
+
+ for (size_t i = 0; i < results.size(); ++i)
+ for (size_t j = 0; j < results[i].size(); ++j)
+ {
+ if (tests_avail.count(results[i][j].first) == 0)
+ {
+ tests_avail.insert(results[i][j].first);
+ tests.push_back(results[i][j].first);
+ }
+ }
+
+ for (std::vector<std::string>::iterator ti = tests.begin(); ti != tests.end(); ++ti)
+ {
+ std::vector<float> values;
+
+ for (size_t i = 0; i < results.size(); ++i)
+ {
+ for (size_t j = 0; j < results[i].size(); ++j)
+ {
+ if (*ti == results[i][j].first)
+ {
+ values.push_back(results[i][j].second);
+ break;
+ }
+ }
+ }
+
+ if (output == ot_html)
+ {
+ std::cout << "<tr><th>" << *ti << "</th>";
+
+ float min = 0;
+
+ if (!values.empty())
+ min = *std::min_element(values.begin(), values.end());
+
+ for (size_t i = 0; i < values.size(); ++i)
+ {
+ std::cout << "<td>";
+
+ if (values[i] > min)
+ std::cout << values[i];
+ else
+ std::cout << "<b>" << values[i] << "</b>";
+
+ std::cout << "</td>";
+ }
+
+ std::cout << "</tr>\n";
+ }
+ else if (output == ot_csv)
+ {
+ std::cout << *ti;
+
+ for (size_t i = 0; i < values.size(); ++i)
+ {
+ std::cout << ", " << values[i];
+ }
+
+ std::cout << "\n";
+ }
+ }
+
+ if (output == ot_html)
+ {
+ std::cout << "</table></body></html>\n";
+ }
+ }
+};
+
+void run(const char* test_mask, const char* impl_mask, output_type output)
+{
+ performance_tool tool(test_mask, impl_mask, output);
+
+ tool.run();
+}
+
+int main(int argc, char** argv)
+{
+ output_type output = ot_none;
+ const char* test_mask = 0;
+ const char* impl_mask = 0;
+
+ // parsing arguments
+ for (int i = 1; i < argc; ++i)
+ {
+ if (argv[i][0] == '-')
+ {
+ if (strcmp(argv[i], "--list-tests") == 0 && output == ot_none) output = ot_list_tests;
+ else if (strcmp(argv[i], "--list-impls") == 0 && output == ot_none) output = ot_list_implementations;
+ else if (strcmp(argv[i], "--output-csv") == 0 && output == ot_none) output = ot_csv;
+ else if (strcmp(argv[i], "--output-html") == 0 && output == ot_none) output = ot_html;
+ else
+ {
+ test_mask = 0;
+ break;
+ }
+ }
+ else if (!test_mask && !impl_mask)
+ {
+ test_mask = argv[i];
+ }
+ else if (!impl_mask)
+ {
+ impl_mask = argv[i];
+ }
+ else
+ {
+ test_mask = 0;
+ break;
+ }
+ }
+
+ if (output != ot_list_tests && output != ot_list_implementations && (!test_mask || !impl_mask))
+ {
+ std::cout << "Usage: perf-test testmask implmask [--output-csv] [--output-html]" << std::endl;
+ std::cout << "Usage: perf-test --list-tests" << std::endl;
+ std::cout << "Usage: perf-test --list-impls" << std::endl;
+ return -1;
+ }
+
+ if (output == ot_none) output = ot_csv;
+
+ run(test_mask, impl_mask, output);
+}
Added: sandbox/SOC/2007/bigint/libs/bigint/perf-test/match.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/perf-test/match.hpp 2007-08-19 14:28:53 EDT (Sun, 19 Aug 2007)
@@ -0,0 +1,108 @@
+/* Boost match.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)
+ *
+ * Implementation taken from pugxml library
+ */
+
+#ifndef MATCH_HPP
+#define MATCH_HPP
+
+namespace detail
+{
+ int strcmpwild(const char* src, const char* dst);
+
+ // Character set pattern match.
+ inline int strcmpwild_cset(const char** src, const char** dst)
+ {
+ int find = 0, excl = 0, star = 0;
+
+ if (**src == '!')
+ {
+ excl = 1;
+ ++(*src);
+ }
+
+ while (**src != ']' || star == 1)
+ {
+ if (find == 0)
+ {
+ if (**src == '-' && *(*src-1) < *(*src+1) && *(*src+1) != ']' && star == 0)
+ {
+ if (**dst >= *(*src-1) && **dst <= *(*src+1))
+ {
+ find = 1;
+ ++(*src);
+ }
+ }
+ else if (**src == **dst) find = 1;
+ }
+ ++(*src);
+ star = 0;
+ }
+
+ if (excl == 1) find = (1 - find);
+ if (find == 1) ++(*dst);
+
+ return find;
+ }
+
+ // Wildcard pattern match.
+ inline int strcmpwild_astr(const char** src, const char** dst)
+ {
+ int find = 1;
+ ++(*src);
+ while ((**dst != 0 && **src == '?') || **src == '*')
+ {
+ if(**src == '?') ++(*dst);
+ ++(*src);
+ }
+ while (**src == '*') ++(*src);
+ if (**dst == 0 && **src != 0) return 0;
+ if (**dst == 0 && **src == 0) return 1;
+ else
+ {
+ if (strcmpwild(*src,*dst))
+ {
+ do
+ {
+ ++(*dst);
+ while(**src != **dst && **src != '[' && **dst != 0)
+ ++(*dst);
+ }
+ while ((**dst != 0) ? strcmpwild(*src,*dst) : 0 != (find=0));
+ }
+ if (**dst == 0 && **src == 0) find = 1;
+ return find;
+ }
+ }
+
+ // Compare two strings, with globbing, and character sets.
+ int strcmpwild(const char* src, const char* dst)
+ {
+ int find = 1;
+ for(; *src != 0 && find == 1 && *dst != 0; ++src)
+ {
+ switch (*src)
+ {
+ case '?': ++dst; break;
+ case '[': ++src; find = strcmpwild_cset(&src,&dst); break;
+ case '*': find = strcmpwild_astr(&src,&dst); --src; break;
+ default : find = (int) (*src == *dst); ++dst;
+ }
+ }
+ while (*src == '*' && find == 1) ++src;
+ return (find == 1 && *dst == 0 && *src == 0) ? 0 : 1;
+ }
+}
+
+inline bool match(const char* string, const char* pattern)
+{
+ return detail::strcmpwild(pattern, string) == 0;
+}
+
+#endif
Added: sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_add.inl
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_add.inl 2007-08-19 14:28:53 EDT (Sun, 19 Aug 2007)
@@ -0,0 +1,18 @@
+/* Boost test_add.inl 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)
+ */
+
+#define TEST_AORS_SMALL test_add_small
+#define TEST_AORS_LARGE test_add_large
+#define AORS_OP +=
+
+#include "impl_aors.inl"
+
+#undef AORS_OP
+#undef TEST_AORS_LARGE
+#undef TEST_AORS_SMALL
Added: sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_and.inl
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_and.inl 2007-08-19 14:28:53 EDT (Sun, 19 Aug 2007)
@@ -0,0 +1,18 @@
+/* Boost test_and.inl 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)
+ */
+
+#define TEST_BITWISE_SMALL test_and_small
+#define TEST_BITWISE_LARGE test_and_large
+#define BITWISE_OP &
+
+#include "impl_bitwise.inl"
+
+#undef BITWISE_OP
+#undef TEST_BITWISE_LARGE
+#undef TEST_BITWISE_SMALL
Added: sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_div.inl
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_div.inl 2007-08-19 14:28:53 EDT (Sun, 19 Aug 2007)
@@ -0,0 +1,18 @@
+/* Boost test_div.inl 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)
+ */
+
+#define TEST_MODDIV_SMALL test_div_small
+#define TEST_MODDIV_MEDIUM test_div_medium
+#define MODDIV_OP /
+
+#include "impl_moddiv.inl"
+
+#undef MODDIV_OP
+#undef TEST_MODDIV_MEDIUM
+#undef TEST_MODDIV_SMALL
Added: sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_fib.inl
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_fib.inl 2007-08-19 14:28:53 EDT (Sun, 19 Aug 2007)
@@ -0,0 +1,83 @@
+/* Boost test_fib.inl 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)
+ */
+
+template <typename number> inline const number fibonacci(unsigned int n)
+{
+ if (n == 0) return 0;
+ else if (n < 3) return 1;
+
+ number cur(1), prev(0), fn1_2, fn_2;
+
+ unsigned int index = 1;
+ unsigned int pot = 1;
+
+ while (pot < n && static_cast<unsigned int>(pot << 1) != 0)
+ pot <<= 1;
+
+ if (pot > n)
+ pot >>= 1;
+
+ pot >>= 1; // skipping first bit: it's '1' and we've already computed fib(1)
+
+ while (pot > 0)
+ {
+ // (fib(n-1),fib(n)) -> (fib(2n-1),fib(2n))
+ // (fib(n-1),fib(n)) -> (fib(2n),fib(2n+1))
+
+ // fib(2n-1)=fib(n-1)^2+fib(n)^2
+ // fib(2n+1)=4*fib(n)^2-fib(n-1)^2+2*(-1)^n
+ // fib(2n)=fib(2n+1)-fib(2n-1)
+
+ fn_2 = cur * cur;
+ fn1_2 = prev * prev;
+
+ prev = fn_2 + fn1_2;
+ cur = fn_2 << 2;
+
+ cur -= fn1_2;
+
+ if (index & 1) cur -= 2;
+ else cur += 2;
+
+ index *= 2;
+
+ if ((n & pot) != 0)
+ {
+ n = n & (~pot);
+
+ prev = cur - prev;
+
+ ++index;
+ }
+ else cur -= prev;
+
+ pot >>= 1;
+ }
+
+ return cur;
+}
+
+template <typename number> struct test_fib_small
+{
+ void run()
+ {
+ for (int i = 0; i < 5000; ++i)
+ {
+ number f = fibonacci<number>(1000);
+ }
+ }
+};
+
+template <typename number> struct test_fib_large
+{
+ void run()
+ {
+ number f = fibonacci<number>(5000000);
+ }
+};
Added: sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_from_string.inl
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_from_string.inl 2007-08-19 14:28:53 EDT (Sun, 19 Aug 2007)
@@ -0,0 +1,30 @@
+/* Boost test_from_string.inl 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)
+ */
+
+template <typename number> struct test_from_string_small
+{
+ void run()
+ {
+ for (int i = 0; i < 1000000; ++i)
+ {
+ number a("23943");
+ }
+ }
+};
+
+template <typename number> struct test_from_string_medium
+{
+ void run()
+ {
+ for (int i = 0; i < 200; ++i)
+ {
+ number a("2394823428918340912384091823409182349012384091384091238409124209134120938420913482091421309842130941230948213098120938409134218348902239482342891834091238409182340918234901238409138409123840912420913412093842091348209142130984213094123094821309812093840913421834890223948234289183409123840918234091823490123840913840912384091242091341209384209134820914213098421309412309482130981209384091342183489022394823428918340912384091823409182349012384091384091238409124209134120938420913482091421309842130941230948213098120938409134218348902239482342891834091238409182340918234901238409138409123840912420913412093842091348209142130984213094123094821309812093840913421834890223948234289183409123840918234091823490123840913840912384091242091341209384209134820914213098421309412309482130981209384091342183489022394823428918340912384091823409182349012384091384091238409124209134120938420913482091421309842130941230948213098120938409134218348902239482342891834091238409182340918234901238409138409123840912420913412093842091
348209142130984213094123094821309812093840913421834890223948234289183409123840918234091823490123840913840912384091242091341209384209134820914213098421309412309482130981209384091342183489022394823428918340912384091823409182349012384091384091238409124209134120938420913482091421309842130941230948213098120938409134218348902239482342891834091238409182340918234901238409138409123840912420913412093842091348209142130984213094123094821309812093840913421834890223948234289183409123840918234091823490123840913840912384091242091341209384209134820914213098421309412309482130981209384091342183489022394823428918340912384091823409182349012384091384091238409124209134120938420913482091421309842130941230948213098120938409134218348902239482342891834091238409182340918234901238409138409123840912420913412093842091348209142130984213094123094821309812093840913421834890223948234289183409123840918234091823490123840913840912384091242091341209384209134820914213098421309412309482130981209384091342183489022394823428918340912384091823409182349
012384091384091238409124209134120938420913482091421309842130941230948213098120938409134218348902239482342891834091238409182340918234901238409138409123840912420913412093842091348209142130984213094123094821309812093840913421834890223948234289183409123840918234091823490123840913840912384091242091341209384209134820914213098421309412309482130981209384091342183489022394823428918340912384091823409182349012384091384091238409124209134120938420913482091421309842130941230948213098120938409134218348902");
+ }
+ }
+};
Added: sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_gcd.inl
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_gcd.inl 2007-08-19 14:28:53 EDT (Sun, 19 Aug 2007)
@@ -0,0 +1,82 @@
+/* Boost test_gcd.inl 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)
+ */
+
+template <typename number> inline number gcd(const number& lhs, const number& rhs)
+{
+ number a = lhs, b = rhs;
+
+ unsigned int k = 0;
+
+ while (a % 2 == 0 && b % 2 == 0)
+ {
+ ++k;
+ a >>= 1;
+ b >>= 1;
+ }
+
+ while (a % 2 == 0)
+ {
+ a >>= 1;
+ }
+
+ while (b % 2 == 0)
+ {
+ b >>= 1;
+ }
+
+ while (a != 0 && b != 0)
+ {
+ if (a > b) a -= b;
+ else b -= a;
+ }
+
+ return (a != 0 ? a : b) << k;
+}
+
+template <typename number> struct test_gcd_small
+{
+ number a, b;
+
+ test_gcd_small()
+ {
+ a = 364;
+ b = 389;
+ }
+
+ void run()
+ {
+ number c;
+
+ for (int i = 0; i < 30000; ++i)
+ {
+ c = gcd(a, b);
+ }
+ }
+};
+
+template <typename number> struct test_gcd_medium
+{
+ number a, b;
+
+ test_gcd_medium()
+ {
+ a = number("2384972234238747238423428374209384728934384723847823849722342387472384234283742093847289343847238478");
+ b = number("78836475634756123847238427384723948723847238472377883647563475612384723842738472394872384723847237");
+ }
+
+ void run()
+ {
+ number c;
+
+ for (int i = 0; i < 150; ++i)
+ {
+ c = gcd(a, b);
+ }
+ }
+};
Added: sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_isprime.inl
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_isprime.inl 2007-08-19 14:28:53 EDT (Sun, 19 Aug 2007)
@@ -0,0 +1,58 @@
+/* Boost test_isprime.inl 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)
+ */
+
+template <typename number> inline bool isprime(const number& n)
+{
+ if (n <= 1) return false;
+
+ number sqrtn = sqrt(n);
+
+ for (number i = 2; i <= sqrtn; ++i)
+ {
+ if (n % i == 0) return false;
+ }
+
+ return true;
+}
+
+template <typename number> struct test_isprime_small
+{
+ number a;
+
+ test_isprime_small()
+ {
+ a = 997;
+ }
+
+ void run()
+ {
+ for (int i = 0; i < 10000; ++i)
+ {
+ number f = isprime(a);
+ }
+ }
+};
+
+template <typename number> struct test_isprime_medium
+{
+ number a;
+
+ test_isprime_medium()
+ {
+ a = number("2013265921");
+ }
+
+ void run()
+ {
+ for (int i = 0; i < 5; ++i)
+ {
+ isprime(a);
+ }
+ }
+};
Added: sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_lshift.inl
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_lshift.inl 2007-08-19 14:28:53 EDT (Sun, 19 Aug 2007)
@@ -0,0 +1,68 @@
+/* Boost test_lshift.inl 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)
+ */
+
+template <typename number> struct test_lshift_small
+{
+ number a;
+
+ test_lshift_small()
+ {
+ a = 3239443;
+ }
+
+ void run()
+ {
+ number b;
+
+ for (int i = 0; i < 500000; ++i)
+ {
+ b = a << 39;
+ }
+ }
+};
+
+template <typename number> struct test_lshift_large
+{
+ number a;
+
+ test_lshift_large()
+ {
+ a = pow(number("2394823409283409273487324"), 100);
+ }
+
+ void run()
+ {
+ number b;
+
+ for (int i = 0; i < 20000; ++i)
+ {
+ b = a << 38943;
+ }
+ }
+};
+
+template <typename number> struct test_lshift_exact
+{
+ number a;
+
+ test_lshift_exact()
+ {
+ a = pow(number("2394823409283409273487324"), 100);
+ }
+
+ void run()
+ {
+ number b;
+
+ for (int i = 0; i < 100000; ++i)
+ {
+ b = a << 38944;
+ }
+ }
+};
Added: sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_mod.inl
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_mod.inl 2007-08-19 14:28:53 EDT (Sun, 19 Aug 2007)
@@ -0,0 +1,18 @@
+/* Boost test_mod.inl 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)
+ */
+
+#define TEST_MODDIV_SMALL test_mod_small
+#define TEST_MODDIV_MEDIUM test_mod_medium
+#define MODDIV_OP %
+
+#include "impl_moddiv.inl"
+
+#undef MODDIV_OP
+#undef TEST_MODDIV_MEDIUM
+#undef TEST_MODDIV_SMALL
Added: sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_mul.inl
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_mul.inl 2007-08-19 14:28:53 EDT (Sun, 19 Aug 2007)
@@ -0,0 +1,71 @@
+/* Boost test_mul.inl 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)
+ */
+
+template <typename number> struct test_mul_small
+{
+ number a, b;
+
+ test_mul_small()
+ {
+ a = 23943;
+ b = 39048;
+ }
+
+ void run()
+ {
+ number c;
+
+ for (int i = 0; i < 500000; ++i)
+ {
+ c = a * b;
+ }
+ }
+};
+
+template <typename number> struct test_mul_medium
+{
+ number a, b;
+
+ test_mul_medium()
+ {
+ a = pow(number("2394823409283409273487324"), 100);
+ b = pow(number("9203402349384209348209234"), 100);
+ }
+
+ void run()
+ {
+ number c;
+
+ for (int i = 0; i < 500; ++i)
+ {
+ c = a * b;
+ }
+ }
+};
+
+template <typename number> struct test_mul_large
+{
+ number a, b;
+
+ test_mul_large()
+ {
+ a = pow(number("2394823409283409273487324"), 50000);
+ b = pow(number("9203402349384209348209234"), 50000);
+ }
+
+ void run()
+ {
+ number c;
+
+ for (int i = 0; i < 2; ++i)
+ {
+ c = a * b;
+ }
+ }
+};
Added: sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_or.inl
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_or.inl 2007-08-19 14:28:53 EDT (Sun, 19 Aug 2007)
@@ -0,0 +1,18 @@
+/* Boost test_or.inl 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)
+ */
+
+#define TEST_BITWISE_SMALL test_or_small
+#define TEST_BITWISE_LARGE test_or_large
+#define BITWISE_OP |
+
+#include "impl_bitwise.inl"
+
+#undef BITWISE_OP
+#undef TEST_BITWISE_LARGE
+#undef TEST_BITWISE_SMALL
Added: sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_rshift.inl
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_rshift.inl 2007-08-19 14:28:53 EDT (Sun, 19 Aug 2007)
@@ -0,0 +1,68 @@
+/* Boost test_rshift.inl 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)
+ */
+
+template <typename number> struct test_rshift_small
+{
+ number a;
+
+ test_rshift_small()
+ {
+ a = 3239443;
+ }
+
+ void run()
+ {
+ number b;
+
+ for (int i = 0; i < 500000; ++i)
+ {
+ b = a >> 7;
+ }
+ }
+};
+
+template <typename number> struct test_rshift_large
+{
+ number a;
+
+ test_rshift_large()
+ {
+ a = pow(number("2394823409283409273487324"), 100);
+ }
+
+ void run()
+ {
+ number b;
+
+ for (int i = 0; i < 20000; ++i)
+ {
+ b = a >> 3893;
+ }
+ }
+};
+
+template <typename number> struct test_rshift_exact
+{
+ number a;
+
+ test_rshift_exact()
+ {
+ a = pow(number("2394823409283409273487324"), 100);
+ }
+
+ void run()
+ {
+ number b;
+
+ for (int i = 0; i < 200000; ++i)
+ {
+ b = a >> 3904;
+ }
+ }
+};
Added: sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_sqrt.inl
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_sqrt.inl 2007-08-19 14:28:53 EDT (Sun, 19 Aug 2007)
@@ -0,0 +1,48 @@
+/* Boost test_sqrt.inl 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)
+ */
+
+template <typename number> struct test_sqrt_small
+{
+ number a;
+
+ test_sqrt_small()
+ {
+ a = 23943;
+ }
+
+ void run()
+ {
+ number b;
+
+ for (int i = 0; i < 50000; ++i)
+ {
+ b = sqrt(a);
+ }
+ }
+};
+
+template <typename number> struct test_sqrt_medium
+{
+ number a;
+
+ test_sqrt_medium()
+ {
+ a = pow(number("2394823409283409273487324"), 100) * number("9203402349384209348209234") + 34982349;
+ }
+
+ void run()
+ {
+ number b;
+
+ for (int i = 0; i < 15; ++i)
+ {
+ b = sqrt(a);
+ }
+ }
+};
Added: sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_sub.inl
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_sub.inl 2007-08-19 14:28:53 EDT (Sun, 19 Aug 2007)
@@ -0,0 +1,18 @@
+/* Boost test_sub.inl 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)
+ */
+
+#define TEST_AORS_SMALL test_sub_small
+#define TEST_AORS_LARGE test_sub_large
+#define AORS_OP -=
+
+#include "impl_aors.inl"
+
+#undef AORS_OP
+#undef TEST_AORS_LARGE
+#undef TEST_AORS_SMALL
Added: sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_to_string.inl
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_to_string.inl 2007-08-19 14:28:53 EDT (Sun, 19 Aug 2007)
@@ -0,0 +1,44 @@
+/* Boost test_to_string.inl 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)
+ */
+
+template <typename number> struct test_to_string_small
+{
+ number a;
+
+ test_to_string_small()
+ {
+ a = 23943;
+ }
+
+ void run()
+ {
+ for (int i = 0; i < 1000000; ++i)
+ {
+ a.str();
+ }
+ }
+};
+
+template <typename number> struct test_to_string_medium
+{
+ number a;
+
+ test_to_string_medium()
+ {
+ a = pow(number("2394823409283409273487324"), 100);
+ }
+
+ void run()
+ {
+ for (int i = 0; i < 100; ++i)
+ {
+ a.str();
+ }
+ }
+};
Added: sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_xor.inl
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/perf-test/test_xor.inl 2007-08-19 14:28:53 EDT (Sun, 19 Aug 2007)
@@ -0,0 +1,18 @@
+/* Boost test_xor.inl 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)
+ */
+
+#define TEST_BITWISE_SMALL test_xor_small
+#define TEST_BITWISE_LARGE test_xor_large
+#define BITWISE_OP ^
+
+#include "impl_bitwise.inl"
+
+#undef BITWISE_OP
+#undef TEST_BITWISE_LARGE
+#undef TEST_BITWISE_SMALL