Boost logo

Boost-Commit :

From: arseny.kapoulkine_at_[hidden]
Date: 2007-08-19 14:31:28


Author: zeux
Date: 2007-08-19 14:31:27 EDT (Sun, 19 Aug 2007)
New Revision: 38768
URL: http://svn.boost.org/trac/boost/changeset/38768

Log:
Multiplication speed test
Added:
   sandbox/SOC/2007/bigint/libs/bigint/src/mul_test.cpp (contents, props changed)

Added: sandbox/SOC/2007/bigint/libs/bigint/src/mul_test.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/src/mul_test.cpp 2007-08-19 14:31:27 EDT (Sun, 19 Aug 2007)
@@ -0,0 +1,129 @@
+#include <iostream>
+#include <ctime>
+
+#include <boost/bigint/bigint_default.hpp>
+#include <boost/bigint/bigint_storage_vector.hpp>
+
+typedef boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 8> default_8;
+typedef boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 16> default_16;
+typedef boost::detail::bigint_default_implementation<boost::detail::bigint_storage_vector, 32> default_32;
+
+ static size_t log2(size_t value)
+ {
+ size_t r = 0;
+
+ while (value > 1)
+ {
+ ++r;
+ value >>= 1;
+ }
+
+ return r;
+ }
+
+template <typename impl> void measure_basecase(const char* impl_name, unsigned int limbs_left, unsigned int limbs_right, unsigned int count)
+{
+ impl a, b;
+
+ a.data.resize(limbs_left);
+ std::fill(a.data.begin(), a.data.end(), impl::limb_max());
+
+ b.data.resize(limbs_left);
+ std::fill(b.data.begin(), b.data.end(), impl::limb_max());
+
+ impl c;
+ c._mul_unsigned_basecase(a, b);
+
+ clock_t start = clock();
+ for (unsigned int i = 0; i < count; ++i)
+ {
+ c._mul_unsigned_basecase(a, b);
+ }
+ clock_t end = clock();
+
+ std::cout << impl_name << " basecase: " << limbs_left << "x" << limbs_right << " multiplication: " << count << " times take " << (end-start) << " clocks, "
+ << double(end - start) / count / limbs_left / limbs_right * 100000 << " per limb"
+ << std::endl;
+}
+
+template <typename impl> void measure_fft(const char* impl_name, unsigned int limbs_left, unsigned int limbs_right, unsigned int count)
+{
+ impl a, b;
+
+ a.data.resize(limbs_left);
+ std::fill(a.data.begin(), a.data.end(), impl::limb_max());
+
+ b.data.resize(limbs_left);
+ std::fill(b.data.begin(), b.data.end(), impl::limb_max());
+
+ impl c;
+ c._mul_unsigned_fft(a, b);
+
+ clock_t start = clock();
+ for (unsigned int i = 0; i < count; ++i)
+ {
+ c._mul_unsigned_fft(a, b);
+ }
+ clock_t end = clock();
+
+ // find FFT (uint16) size
+ size_t max_size = (std::max)(limbs_left, limbs_right);
+
+ // round up to the nearest power of two
+ size_t N = 1;
+ while (N < max_size) N *= 2;
+
+ // fix N depending on limb_type
+ N = N * sizeof(impl::limb_t) / sizeof(unsigned short);
+ if (N == 0) N = 1;
+
+ // destination size
+ N *= 2;
+
+ std::cout << impl_name << " fft: " << limbs_left << "x" << limbs_right << " multiplication: " << count << " times take " << (end-start) << " clocks, "
+ << double(end - start) / count / N / log2(N) * 100000 << " per element"
+ << std::endl;
+}
+
+int main()
+{
+ measure_basecase<default_8>("default_8", 4, 4, 2000000);
+ measure_basecase<default_16>("default_16", 4, 4, 2000000);
+ measure_basecase<default_32>("default_32", 4, 4, 2000000);
+
+ measure_basecase<default_8>("default_8", 16, 16, 200000);
+ measure_basecase<default_16>("default_16", 16, 16, 200000);
+ measure_basecase<default_32>("default_32", 16, 16, 200000);
+
+ measure_basecase<default_8>("default_8", 256, 256, 1000);
+ measure_basecase<default_16>("default_16", 256, 256, 1000);
+ measure_basecase<default_32>("default_32", 256, 256, 1000);
+
+ measure_basecase<default_8>("default_8", 1024, 1024, 64);
+ measure_basecase<default_16>("default_16", 1024, 1024, 64);
+ measure_basecase<default_32>("default_32", 1024, 1024, 64);
+
+ measure_basecase<default_8>("default_8", 8192, 8192, 1);
+ measure_basecase<default_16>("default_16", 8192, 8192, 1);
+ measure_basecase<default_32>("default_32", 8192, 8192, 1);
+
+ measure_fft<default_8>("default_8", 4, 4, 100000);
+ measure_fft<default_16>("default_16", 4, 4, 100000);
+ measure_fft<default_32>("default_32", 4, 4, 100000);
+
+ measure_fft<default_8>("default_8", 16, 16, 20000);
+ measure_fft<default_16>("default_16", 16, 16, 20000);
+ measure_fft<default_32>("default_32", 16, 16, 20000);
+
+ measure_fft<default_8>("default_8", 256, 256, 1000);
+ measure_fft<default_16>("default_16", 256, 256, 1000);
+ measure_fft<default_32>("default_32", 256, 256, 1000);
+
+ measure_fft<default_8>("default_8", 1024, 1024, 64);
+ measure_fft<default_16>("default_16", 1024, 1024, 64);
+ measure_fft<default_32>("default_32", 1024, 1024, 64);
+
+ measure_fft<default_8>("default_8", 8192, 8192, 10);
+ measure_fft<default_16>("default_16", 8192, 8192, 10);
+ measure_fft<default_32>("default_32", 8192, 8192, 10);
+}


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