Subject: [Boost-commit] svn:boost r49572 - in sandbox/mp_math: boost/mp_math/mp_int libs/mp_math/test libs/mp_math/tools/benchmark
From: baraclese_at_[hidden]
Date: 2008-11-03 14:18:44
Author: baraclese
Date: 2008-11-03 14:18:42 EST (Mon, 03 Nov 2008)
New Revision: 49572
URL: http://svn.boost.org/trac/boost/changeset/49572
Log:
* Removed char* and wchar_t* overloads and replaced them by a templatized
version.
* Added new nth_root overload.
* Added a new mode to the benchmark tool meant to benchmark large numbers. On
the way I fixed a few bugs in it.
* some other minor changes
Added:
sandbox/mp_math/libs/mp_math/tools/benchmark/modes.cpp (contents, props changed)
sandbox/mp_math/libs/mp_math/tools/benchmark/modes.hpp (contents, props changed)
Text files modified:
sandbox/mp_math/boost/mp_math/mp_int/jacobi.hpp | 8
sandbox/mp_math/boost/mp_math/mp_int/mp_int.hpp | 91 +++-------
sandbox/mp_math/boost/mp_math/mp_int/operators.hpp | 245 +++++++-----------------------
sandbox/mp_math/boost/mp_math/mp_int/root.hpp | 70 ++++++++
sandbox/mp_math/libs/mp_math/test/integral_ops.cpp | 6
sandbox/mp_math/libs/mp_math/test/jamfile.v2 | 1
sandbox/mp_math/libs/mp_math/tools/benchmark/benchmark.cpp | 33 ----
sandbox/mp_math/libs/mp_math/tools/benchmark/benchmark.hpp | 9
sandbox/mp_math/libs/mp_math/tools/benchmark/benchmark_runner.cpp | 319 +++------------------------------------
sandbox/mp_math/libs/mp_math/tools/benchmark/benchmark_runner.hpp | 55 +-----
sandbox/mp_math/libs/mp_math/tools/benchmark/jamfile.v2 | 7
sandbox/mp_math/libs/mp_math/tools/benchmark/main.cpp | 143 ++++++++++++++---
12 files changed, 318 insertions(+), 669 deletions(-)
Modified: sandbox/mp_math/boost/mp_math/mp_int/jacobi.hpp
==============================================================================
--- sandbox/mp_math/boost/mp_math/mp_int/jacobi.hpp (original)
+++ sandbox/mp_math/boost/mp_math/mp_int/jacobi.hpp 2008-11-03 14:18:42 EST (Mon, 03 Nov 2008)
@@ -29,10 +29,10 @@
if (a == digit_type(1))
return 1;
- /* default */
+ // default
int s = 0;
- /* write a = a1 * 2**k */
+ // write a = a1 * 2**k
mp_int<A,T> a1(a);
// find largest power of two that divides a1
@@ -40,7 +40,7 @@
// now divide by it
a1.shift_right(k,0);
- /* if k is even set s=1 */
+ // if k is even set s=1
if ((k & 1) == 0)
s = 1;
else
@@ -54,7 +54,7 @@
s = -1;
}
- /* if p == 3 (mod 4) *and* a1 == 3 (mod 4) then s = -s */
+ // if p == 3 (mod 4) *and* a1 == 3 (mod 4) then s = -s
if (((p[0] & 3) == 3) && ((a1[0] & 3) == 3))
s = -s;
Modified: sandbox/mp_math/boost/mp_math/mp_int/mp_int.hpp
==============================================================================
--- sandbox/mp_math/boost/mp_math/mp_int/mp_int.hpp (original)
+++ sandbox/mp_math/boost/mp_math/mp_int/mp_int.hpp 2008-11-03 14:18:42 EST (Mon, 03 Nov 2008)
@@ -84,20 +84,14 @@
template<typename IntegralT>
mp_int& operator = (IntegralT rhs);
- mp_int& operator = (const char*);
-
- #ifndef BOOST_NO_CWCHAR
- mp_int& operator = (const wchar_t*);
- #endif
+ template<typename charT>
+ mp_int& operator = (const charT*);
template<typename charT, class traits, class Alloc>
mp_int& operator = (const std::basic_string<charT,traits,Alloc>&);
- void assign(const char*, std::ios_base::fmtflags);
-
- #ifndef BOOST_NO_CWCHAR
- void assign(const wchar_t*, std::ios_base::fmtflags);
- #endif
+ template<typename charT>
+ void assign(const charT*, std::ios_base::fmtflags);
template<typename charT, class traits, class Alloc>
void assign(const std::basic_string<charT,traits,Alloc>&,
@@ -139,25 +133,14 @@
template<typename IntegralT> mp_int& operator &= (IntegralT);
template<typename IntegralT> mp_int& operator ^= (IntegralT);
- mp_int& operator += (const char*);
- mp_int& operator -= (const char*);
- mp_int& operator *= (const char*);
- mp_int& operator /= (const char*);
- mp_int& operator %= (const char*);
- mp_int& operator |= (const char*);
- mp_int& operator &= (const char*);
- mp_int& operator ^= (const char*);
-
- #ifndef BOOST_NO_CWCHAR
- mp_int& operator += (const wchar_t*);
- mp_int& operator -= (const wchar_t*);
- mp_int& operator *= (const wchar_t*);
- mp_int& operator /= (const wchar_t*);
- mp_int& operator %= (const wchar_t*);
- mp_int& operator |= (const wchar_t*);
- mp_int& operator &= (const wchar_t*);
- mp_int& operator ^= (const wchar_t*);
- #endif
+ template<typename charT> mp_int& operator += (const charT*);
+ template<typename charT> mp_int& operator -= (const charT*);
+ template<typename charT> mp_int& operator *= (const charT*);
+ template<typename charT> mp_int& operator /= (const charT*);
+ template<typename charT> mp_int& operator %= (const charT*);
+ template<typename charT> mp_int& operator |= (const charT*);
+ template<typename charT> mp_int& operator &= (const charT*);
+ template<typename charT> mp_int& operator ^= (const charT*);
template<typename charT, class traits, class Alloc>
mp_int& operator += (const std::basic_string<charT,traits,Alloc>&);
@@ -453,22 +436,13 @@
}
template<class A, class T>
-mp_int<A,T>& mp_int<A,T>::operator = (const char* s)
-{
- size_ = 0;
- init(s, s + std::strlen(s));
- return *this;
-}
-
-#ifndef BOOST_NO_CWCHAR
-template<class A, class T>
-mp_int<A,T>& mp_int<A,T>::operator = (const wchar_t* s)
+template<typename charT>
+mp_int<A,T>& mp_int<A,T>::operator = (const charT* s)
{
size_ = 0;
- init(s, s + std::wcslen(s));
+ init(s, s + std::char_traits<charT>::length(s));
return *this;
}
-#endif
template<class A, class T>
template<typename charT, class traits, class Alloc>
@@ -480,21 +454,13 @@
}
template<class A, class T>
+template<typename charT>
inline void
-mp_int<A,T>::assign(const char* s, std::ios_base::fmtflags f)
+mp_int<A,T>::assign(const charT* s, std::ios_base::fmtflags f)
{
- assign(s, s + std::strlen(s), f);
+ assign(s, s + std::char_traits<charT>::length(s), f);
}
-#ifndef BOOST_NO_CWCHAR
-template<class A, class T>
-inline void
-mp_int<A,T>::assign(const wchar_t* s, std::ios_base::fmtflags f)
-{
- assign(s, s + std::wcslen(s), f);
-}
-#endif
-
template<class A, class T>
template<typename charT, class traits, class Alloc>
inline void
@@ -606,16 +572,19 @@
{
if (capacity() < n)
{
- if (n >= sign_bit)
+ if (n < sign_bit)
+ {
+ const size_type new_cap = capacity() + capacity();
+ if (new_cap > n)
+ n = new_cap;
+ digit_type* d = this->allocate(n, digits_);
+ std::memcpy(d, digits_, sizeof(digit_type) * size_);
+ this->deallocate(digits_, capacity());
+ digits_ = d;
+ set_capacity(n);
+ }
+ else
throw std::bad_alloc();
- const size_type new_cap = capacity() + capacity();
- if (new_cap > n)
- n = new_cap;
- digit_type* d = this->allocate(n, digits_);
- std::memcpy(d, digits_, sizeof(digit_type) * size_);
- this->deallocate(digits_, capacity());
- digits_ = d;
- set_capacity(n);
}
}
Modified: sandbox/mp_math/boost/mp_math/mp_int/operators.hpp
==============================================================================
--- sandbox/mp_math/boost/mp_math/mp_int/operators.hpp (original)
+++ sandbox/mp_math/boost/mp_math/mp_int/operators.hpp 2008-11-03 14:18:42 EST (Mon, 03 Nov 2008)
@@ -111,108 +111,55 @@
operator >= (IntegralT lhs, const mp_int<A,T>& rhs) { return rhs <= lhs; }
-// compare mp_int to const char*
-template<class A, class T>
+// compare mp_int to character string
+template<class A, class T, typename charT>
inline bool
-operator == (const mp_int<A,T>& lhs, const char* rhs) { return lhs == mp_int<A,T>(rhs); }
+operator == (const mp_int<A,T>& lhs, const charT* rhs) { return lhs == mp_int<A,T>(rhs); }
-template<class A, class T>
+template<class A, class T, typename charT>
inline bool
-operator != (const mp_int<A,T>& lhs, const char* rhs) { return lhs != mp_int<A,T>(rhs); }
+operator != (const mp_int<A,T>& lhs, const charT* rhs) { return lhs != mp_int<A,T>(rhs); }
-template<class A, class T>
+template<class A, class T, typename charT>
inline bool
-operator < (const mp_int<A,T>& lhs, const char* rhs) { return lhs < mp_int<A,T>(rhs); }
+operator < (const mp_int<A,T>& lhs, const charT* rhs) { return lhs < mp_int<A,T>(rhs); }
-template<class A, class T>
+template<class A, class T, typename charT>
inline bool
-operator > (const mp_int<A,T>& lhs, const char* rhs) { return lhs > mp_int<A,T>(rhs); }
+operator > (const mp_int<A,T>& lhs, const charT* rhs) { return lhs > mp_int<A,T>(rhs); }
-template<class A, class T>
+template<class A, class T, typename charT>
inline bool
-operator <= (const mp_int<A,T>& lhs, const char* rhs) { return lhs <= mp_int<A,T>(rhs); }
+operator <= (const mp_int<A,T>& lhs, const charT* rhs) { return lhs <= mp_int<A,T>(rhs); }
-template<class A, class T>
+template<class A, class T, typename charT>
inline bool
-operator >= (const mp_int<A,T>& lhs, const char* rhs) { return lhs >= mp_int<A,T>(rhs); }
+operator >= (const mp_int<A,T>& lhs, const charT* rhs) { return lhs >= mp_int<A,T>(rhs); }
// compare const char* to mp_int
-template<class A, class T>
+template<class A, class T, typename charT>
inline bool
-operator == (const char* lhs, const mp_int<A,T>& rhs) { return mp_int<A,T>(lhs) == rhs; }
+operator == (const charT* lhs, const mp_int<A,T>& rhs) { return mp_int<A,T>(lhs) == rhs; }
-template<class A, class T>
+template<class A, class T, typename charT>
inline bool
-operator != (const char* lhs, const mp_int<A,T>& rhs) { return mp_int<A,T>(lhs) != rhs; }
+operator != (const charT* lhs, const mp_int<A,T>& rhs) { return mp_int<A,T>(lhs) != rhs; }
-template<class A, class T>
+template<class A, class T, typename charT>
inline bool
-operator < (const char* lhs, const mp_int<A,T>& rhs) { return mp_int<A,T>(lhs) < rhs; }
+operator < (const charT* lhs, const mp_int<A,T>& rhs) { return mp_int<A,T>(lhs) < rhs; }
-template<class A, class T>
+template<class A, class T, typename charT>
inline bool
-operator > (const char* lhs, const mp_int<A,T>& rhs) { return mp_int<A,T>(lhs) > rhs; }
+operator > (const charT* lhs, const mp_int<A,T>& rhs) { return mp_int<A,T>(lhs) > rhs; }
-template<class A, class T>
+template<class A, class T, typename charT>
inline bool
-operator <= (const char* lhs, const mp_int<A,T>& rhs) { return mp_int<A,T>(lhs) <= rhs; }
+operator <= (const charT* lhs, const mp_int<A,T>& rhs) { return mp_int<A,T>(lhs) <= rhs; }
-template<class A, class T>
+template<class A, class T, typename charT>
inline bool
-operator >= (const char* lhs, const mp_int<A,T>& rhs) { return mp_int<A,T>(lhs) >= rhs; }
-
-
-#ifndef BOOST_NO_CWCHAR
-// compare mp_int to const wchar_t*
-template<class A, class T>
-inline bool
-operator == (const mp_int<A,T>& lhs, const wchar_t* rhs) { return lhs == mp_int<A,T>(rhs); }
-
-template<class A, class T>
-inline bool
-operator != (const mp_int<A,T>& lhs, const wchar_t* rhs) { return lhs != mp_int<A,T>(rhs); }
-
-template<class A, class T>
-inline bool
-operator < (const mp_int<A,T>& lhs, const wchar_t* rhs) { return lhs < mp_int<A,T>(rhs); }
-
-template<class A, class T>
-inline bool
-operator > (const mp_int<A,T>& lhs, const wchar_t* rhs) { return lhs > mp_int<A,T>(rhs); }
-
-template<class A, class T>
-inline bool
-operator <= (const mp_int<A,T>& lhs, const wchar_t* rhs) { return lhs <= mp_int<A,T>(rhs); }
-
-template<class A, class T>
-inline bool
-operator >= (const mp_int<A,T>& lhs, const wchar_t* rhs) { return lhs >= mp_int<A,T>(rhs); }
-
-// compare const wchar_t* to mp_int
-template<class A, class T>
-inline bool
-operator == (const wchar_t* lhs, const mp_int<A,T>& rhs) { return mp_int<A,T>(lhs) == rhs; }
-
-template<class A, class T>
-inline bool
-operator != (const wchar_t* lhs, const mp_int<A,T>& rhs) { return mp_int<A,T>(lhs) != rhs; }
-
-template<class A, class T>
-inline bool
-operator < (const wchar_t* lhs, const mp_int<A,T>& rhs) { return mp_int<A,T>(lhs) < rhs; }
-
-template<class A, class T>
-inline bool
-operator > (const wchar_t* lhs, const mp_int<A,T>& rhs) { return mp_int<A,T>(lhs) > rhs; }
-
-template<class A, class T>
-inline bool
-operator <= (const wchar_t* lhs, const mp_int<A,T>& rhs) { return mp_int<A,T>(lhs) <= rhs; }
-
-template<class A, class T>
-inline bool
-operator >= (const wchar_t* lhs, const mp_int<A,T>& rhs) { return mp_int<A,T>(lhs) >= rhs; }
-#endif // BOOST_NO_CWCHAR
+operator >= (const charT* lhs, const mp_int<A,T>& rhs) { return mp_int<A,T>(lhs) >= rhs; }
// compare mp_int to basic_string
@@ -748,170 +695,94 @@
}
-// Arithmetic and bitwise operators involving const char*
-template<class A, class T>
-inline mp_int<A,T>& mp_int<A,T>::operator += (const char* s) { return *this += mp_int<A,T>(s); }
-template<class A, class T>
-inline mp_int<A,T>& mp_int<A,T>::operator -= (const char* s) { return *this -= mp_int<A,T>(s); }
-template<class A, class T>
-inline mp_int<A,T>& mp_int<A,T>::operator *= (const char* s) { return *this *= mp_int<A,T>(s); }
-template<class A, class T>
-inline mp_int<A,T>& mp_int<A,T>::operator /= (const char* s) { return *this /= mp_int<A,T>(s); }
-template<class A, class T>
-inline mp_int<A,T>& mp_int<A,T>::operator %= (const char* s) { return *this %= mp_int<A,T>(s); }
-template<class A, class T>
-inline mp_int<A,T>& mp_int<A,T>::operator |= (const char* s) { return *this |= mp_int<A,T>(s); }
-template<class A, class T>
-inline mp_int<A,T>& mp_int<A,T>::operator &= (const char* s) { return *this &= mp_int<A,T>(s); }
-template<class A, class T>
-inline mp_int<A,T>& mp_int<A,T>::operator ^= (const char* s) { return *this ^= mp_int<A,T>(s); }
-
-template<class A, class T>
-inline mp_int<A,T> operator + (const mp_int<A,T>& lhs, const char* rhs)
-{
- mp_int<A,T> nrv(lhs);
- nrv += mp_int<A,T>(rhs);
- return nrv;
-}
-
-template<class A, class T>
-inline mp_int<A,T> operator - (const mp_int<A,T>& lhs, const char* rhs)
-{
- mp_int<A,T> nrv(lhs);
- nrv -= mp_int<A,T>(rhs);
- return nrv;
-}
-
+// Arithmetic and bitwise operators involving character strings
template<class A, class T>
-inline mp_int<A,T> operator * (const mp_int<A,T>& lhs, const char* rhs)
-{
- mp_int<A,T> nrv(lhs);
- nrv *= mp_int<A,T>(rhs);
- return nrv;
-}
-
+template<typename charT>
+inline mp_int<A,T>& mp_int<A,T>::operator += (const charT* s) { return *this += mp_int<A,T>(s); }
template<class A, class T>
-inline mp_int<A,T> operator / (const mp_int<A,T>& lhs, const char* rhs)
-{
- mp_int<A,T> nrv(lhs);
- nrv /= mp_int<A,T>(rhs);
- return nrv;
-}
+template<typename charT>
+inline mp_int<A,T>& mp_int<A,T>::operator -= (const charT* s) { return *this -= mp_int<A,T>(s); }
template<class A, class T>
-inline mp_int<A,T> operator % (const mp_int<A,T>& lhs, const char* rhs)
-{
- mp_int<A,T> nrv(lhs);
- nrv %= mp_int<A,T>(rhs);
- return nrv;
-}
-
+template<typename charT>
+inline mp_int<A,T>& mp_int<A,T>::operator *= (const charT* s) { return *this *= mp_int<A,T>(s); }
template<class A, class T>
-inline mp_int<A,T> operator | (const mp_int<A,T>& lhs, const char* rhs)
-{
- mp_int<A,T> nrv(lhs);
- nrv |= mp_int<A,T>(rhs);
- return nrv;
-}
-
-template<class A, class T>
-inline mp_int<A,T> operator & (const mp_int<A,T>& lhs, const char* rhs)
-{
- mp_int<A,T> nrv(lhs);
- nrv &= mp_int<A,T>(rhs);
- return nrv;
-}
-
-template<class A, class T>
-inline mp_int<A,T> operator ^ (const mp_int<A,T>& lhs, const char* rhs)
-{
- mp_int<A,T> nrv(lhs);
- nrv ^= mp_int<A,T>(rhs);
- return nrv;
-}
-
-
-#ifndef BOOST_NO_CWCHAR
-// Arithmetic and bitwise operators involving const wchar_t*
-template<class A, class T>
-inline mp_int<A,T>& mp_int<A,T>::operator += (const wchar_t* s) { return *this += mp_int<A,T>(s); }
+template<typename charT>
+inline mp_int<A,T>& mp_int<A,T>::operator /= (const charT* s) { return *this /= mp_int<A,T>(s); }
template<class A, class T>
-inline mp_int<A,T>& mp_int<A,T>::operator -= (const wchar_t* s) { return *this -= mp_int<A,T>(s); }
+template<typename charT>
+inline mp_int<A,T>& mp_int<A,T>::operator %= (const charT* s) { return *this %= mp_int<A,T>(s); }
template<class A, class T>
-inline mp_int<A,T>& mp_int<A,T>::operator *= (const wchar_t* s) { return *this *= mp_int<A,T>(s); }
+template<typename charT>
+inline mp_int<A,T>& mp_int<A,T>::operator |= (const charT* s) { return *this |= mp_int<A,T>(s); }
template<class A, class T>
-inline mp_int<A,T>& mp_int<A,T>::operator /= (const wchar_t* s) { return *this /= mp_int<A,T>(s); }
+template<typename charT>
+inline mp_int<A,T>& mp_int<A,T>::operator &= (const charT* s) { return *this &= mp_int<A,T>(s); }
template<class A, class T>
-inline mp_int<A,T>& mp_int<A,T>::operator %= (const wchar_t* s) { return *this %= mp_int<A,T>(s); }
-template<class A, class T>
-inline mp_int<A,T>& mp_int<A,T>::operator |= (const wchar_t* s) { return *this |= mp_int<A,T>(s); }
-template<class A, class T>
-inline mp_int<A,T>& mp_int<A,T>::operator &= (const wchar_t* s) { return *this &= mp_int<A,T>(s); }
-template<class A, class T>
-inline mp_int<A,T>& mp_int<A,T>::operator ^= (const wchar_t* s) { return *this ^= mp_int<A,T>(s); }
+template<typename charT>
+inline mp_int<A,T>& mp_int<A,T>::operator ^= (const charT* s) { return *this ^= mp_int<A,T>(s); }
-template<class A, class T>
-inline mp_int<A,T> operator + (const mp_int<A,T>& lhs, const wchar_t* rhs)
+template<class A, class T, typename charT>
+inline mp_int<A,T> operator + (const mp_int<A,T>& lhs, const charT* rhs)
{
mp_int<A,T> nrv(lhs);
nrv += mp_int<A,T>(rhs);
return nrv;
}
-template<class A, class T>
-inline mp_int<A,T> operator - (const mp_int<A,T>& lhs, const wchar_t* rhs)
+template<class A, class T, typename charT>
+inline mp_int<A,T> operator - (const mp_int<A,T>& lhs, const charT* rhs)
{
mp_int<A,T> nrv(lhs);
nrv -= mp_int<A,T>(rhs);
return nrv;
}
-template<class A, class T>
-inline mp_int<A,T> operator * (const mp_int<A,T>& lhs, const wchar_t* rhs)
+template<class A, class T, typename charT>
+inline mp_int<A,T> operator * (const mp_int<A,T>& lhs, const charT* rhs)
{
mp_int<A,T> nrv(lhs);
nrv *= mp_int<A,T>(rhs);
return nrv;
}
-template<class A, class T>
-inline mp_int<A,T> operator / (const mp_int<A,T>& lhs, const wchar_t* rhs)
+template<class A, class T, typename charT>
+inline mp_int<A,T> operator / (const mp_int<A,T>& lhs, const charT* rhs)
{
mp_int<A,T> nrv(lhs);
nrv /= mp_int<A,T>(rhs);
return nrv;
}
-template<class A, class T>
-inline mp_int<A,T> operator % (const mp_int<A,T>& lhs, const wchar_t* rhs)
+template<class A, class T, typename charT>
+inline mp_int<A,T> operator % (const mp_int<A,T>& lhs, const charT* rhs)
{
mp_int<A,T> nrv(lhs);
nrv %= mp_int<A,T>(rhs);
return nrv;
}
-template<class A, class T>
-inline mp_int<A,T> operator | (const mp_int<A,T>& lhs, const wchar_t* rhs)
+template<class A, class T, typename charT>
+inline mp_int<A,T> operator | (const mp_int<A,T>& lhs, const charT* rhs)
{
mp_int<A,T> nrv(lhs);
nrv |= mp_int<A,T>(rhs);
return nrv;
}
-template<class A, class T>
-inline mp_int<A,T> operator & (const mp_int<A,T>& lhs, const wchar_t* rhs)
+template<class A, class T, typename charT>
+inline mp_int<A,T> operator & (const mp_int<A,T>& lhs, const charT* rhs)
{
mp_int<A,T> nrv(lhs);
nrv &= mp_int<A,T>(rhs);
return nrv;
}
-template<class A, class T>
-inline mp_int<A,T> operator ^ (const mp_int<A,T>& lhs, const wchar_t* rhs)
+template<class A, class T, typename charT>
+inline mp_int<A,T> operator ^ (const mp_int<A,T>& lhs, const charT* rhs)
{
mp_int<A,T> nrv(lhs);
nrv ^= mp_int<A,T>(rhs);
return nrv;
}
-#endif // BOOST_NO_CWCHAR
// Arithmetic and bitwise operators involving basic_string
Modified: sandbox/mp_math/boost/mp_math/mp_int/root.hpp
==============================================================================
--- sandbox/mp_math/boost/mp_math/mp_int/root.hpp (original)
+++ sandbox/mp_math/boost/mp_math/mp_int/root.hpp 2008-11-03 14:18:42 EST (Mon, 03 Nov 2008)
@@ -61,8 +61,6 @@
template<class A, class T>
mp_int<A,T> nth_root(const mp_int<A,T>& x, typename mp_int<A,T>::digit_type n)
{
- mp_int<A,T> t1, t2, t3;
-
if ((n & 1) == 0 && x.is_negative())
throw std::domain_error("nth_root: argument must be positive if n is even");
@@ -70,7 +68,8 @@
const int neg = x.sign();
const_cast<mp_int<A,T>*>(&x)->set_sign(1);
- // t2 = 2
+ mp_int<A,T> t1, t2, t3;
+
t2 = typename mp_int<A,T>::digit_type(2);
do
@@ -105,7 +104,70 @@
t2 = pow(t1, n);
if (t2 > x)
- t1.sub_digit(1);
+ --t1;
+ else
+ break;
+ }
+
+ // reset the sign of x first
+ const_cast<mp_int<A,T>*>(&x)->set_sign(neg);
+
+ // set the sign of the result
+ t1.set_sign(neg);
+
+ return t1;
+}
+
+template<class A, class T>
+mp_int<A,T> nth_root(const mp_int<A,T>& x, const mp_int<A,T>& n)
+{
+ if (n.is_odd() && x.is_negative())
+ throw std::domain_error("nth_root: argument must be positive if n is even");
+
+ if (n.size() == 1)
+ return nth_root(x, n[0]);
+
+ // if x is negative fudge the sign but keep track
+ const int neg = x.sign();
+ const_cast<mp_int<A,T>*>(&x)->set_sign(1);
+
+ mp_int<A,T> t1, t2, t3;
+
+ t2 = typename mp_int<A,T>::digit_type(2);
+
+ do
+ {
+ t1 = t2;
+
+ // t2 = t1 - ((t1**n - x) / (n * t1**(n-1)))
+
+ // t3 = t1**(n-1)
+ t3 = pow(t1, n-1);
+
+ // numerator
+ // t2 = t1**n
+ t2 = t3 * t1;
+
+ // t2 = t1**n - x
+ t2 -= x;
+
+ // denominator
+ // t3 = t1**(n-1) * n
+ t3 *= n;
+
+ // t3 = (t1**n - x)/(n * t1**(n-1))
+ t3 = t2 / t3;
+
+ t2 = t1 - t3;
+ } while (t1 != t2);
+
+ // result can be off by a few so check
+ for (;;)
+ {
+ t2 = pow(t1, n);
+
+ if (t2 > x)
+ --t1;
else
break;
}
Modified: sandbox/mp_math/libs/mp_math/test/integral_ops.cpp
==============================================================================
--- sandbox/mp_math/libs/mp_math/test/integral_ops.cpp (original)
+++ sandbox/mp_math/libs/mp_math/test/integral_ops.cpp 2008-11-03 14:18:42 EST (Mon, 03 Nov 2008)
@@ -6,6 +6,12 @@
#include <boost/test/unit_test.hpp>
#include "prerequisite.hpp"
+BOOST_AUTO_TEST_CASE_TEMPLATE(construct_from_zero, mp_int_type, mp_int_types)
+{
+ const mp_int_type x(0);
+ BOOST_CHECK_EQUAL(x.is_zero(), true);
+}
+
BOOST_AUTO_TEST_CASE_TEMPLATE(equal_signed_char_min, mp_int_type, mp_int_types)
{
const signed char x = std::numeric_limits<signed char>::min();
Modified: sandbox/mp_math/libs/mp_math/test/jamfile.v2
==============================================================================
--- sandbox/mp_math/libs/mp_math/test/jamfile.v2 (original)
+++ sandbox/mp_math/libs/mp_math/test/jamfile.v2 2008-11-03 14:18:42 EST (Mon, 03 Nov 2008)
@@ -13,7 +13,6 @@
: requirements
<include>../../..
<link>static
- <toolset>gcc:<cxxflags>-std=c++0x
<define>BOOST_TEST_DYN_LINK
<define>BOOST_TEST_MAIN
#<define>BOOST_MP_MATH_MP_INT_USE_ASM
Modified: sandbox/mp_math/libs/mp_math/tools/benchmark/benchmark.cpp
==============================================================================
--- sandbox/mp_math/libs/mp_math/tools/benchmark/benchmark.cpp (original)
+++ sandbox/mp_math/libs/mp_math/tools/benchmark/benchmark.cpp 2008-11-03 14:18:42 EST (Mon, 03 Nov 2008)
@@ -6,39 +6,6 @@
#include "benchmark.hpp"
#include <iostream>
#include <stdexcept>
-#include <boost/random.hpp>
-
-std::string create_random_hex_string(int size_in_bits)
-{
- std::string s;
- boost::mt19937 r;
- boost::uniform_smallint<char> u(0,15);
- boost::variate_generator<boost::mt19937&, boost::uniform_smallint<char> > vg(r, u);
- // one hex digit can occupy 4 bits
- for (int i = 0; i < size_in_bits/4; ++i)
- {
- char tmp = vg();
- if (tmp < 10)
- tmp = '0' + tmp;
- else
- tmp = 'a' + (tmp-10);
- s.push_back(tmp);
- }
- return s;
-}
-
-std::string create_random_dec_string(int size_in_digits)
-{
- std::string s;
- boost::mt19937 r;
- boost::uniform_smallint<char> u(0,9);
- boost::variate_generator<boost::mt19937&, boost::uniform_smallint<char> > vg(r, u);
-
- for (int i = 0; i < size_in_digits; ++i)
- s.push_back('0' + vg());
-
- return s;
-}
const char* to_string(op_type op)
Modified: sandbox/mp_math/libs/mp_math/tools/benchmark/benchmark.hpp
==============================================================================
--- sandbox/mp_math/libs/mp_math/tools/benchmark/benchmark.hpp (original)
+++ sandbox/mp_math/libs/mp_math/tools/benchmark/benchmark.hpp 2008-11-03 14:18:42 EST (Mon, 03 Nov 2008)
@@ -11,11 +11,6 @@
#include <boost/shared_ptr.hpp>
#include <boost/timer.hpp>
-
-std::string create_random_hex_string(int size_in_bits);
-std::string create_random_dec_string(int size_in_digits);
-
-
enum op_type
{
op_ctor_dec,
@@ -158,8 +153,8 @@
op_time.restart();
for (; op_time.elapsed() < sample_time; ++num_ops_executed)
f(i);
- // push the number of ops per millisecond
- r.ops.push_back(1.0/(op_time.elapsed() * 1000.0 / num_ops_executed));
+ // push the number of ops per sample_time
+ r.ops.push_back(num_ops_executed/op_time.elapsed());
}
r.total_time = total.elapsed();
// clear dst vector for next test
Modified: sandbox/mp_math/libs/mp_math/tools/benchmark/benchmark_runner.cpp
==============================================================================
--- sandbox/mp_math/libs/mp_math/tools/benchmark/benchmark_runner.cpp (original)
+++ sandbox/mp_math/libs/mp_math/tools/benchmark/benchmark_runner.cpp 2008-11-03 14:18:42 EST (Mon, 03 Nov 2008)
@@ -3,179 +3,40 @@
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#include <cmath>
-#include <fstream>
#include <iostream>
-#include <numeric> // accumulate
#include <stdexcept>
-#include <sstream>
#include "benchmark_runner.hpp"
void benchmark_runner::run(const std::vector<std::string>& ops,
- double sample_time)
+ double sample_time,
+ const std::vector<std::string>& vec1,
+ const std::vector<std::string>& vec2,
+ const std::vector<std::string>& hex_str_vec,
+ const std::vector<std::string>& dec_str_vec)
{
- init_libs();
+ if (vec1.size() != vec2.size())
+ throw std::runtime_error("input vectors must have same length");
- for (std::vector<std::string>::const_iterator op = ops.begin(); op != ops.end(); ++op)
- execute_bench_op(*op, sample_time);
-
- std::cout << "creating data files..." << std::endl;
- create_data_files();
-}
-
-unsigned long
-benchmark_runner::get_operand1_size(unsigned int sample_number) const
-{
- // linear growth
- const double m = static_cast<double>(end_ - beg_) /
- static_cast<double>(num_input_samples_);
- return (m * sample_number) + beg_;
-}
-
-unsigned long
-benchmark_runner::get_operand2_size(unsigned int sample_number) const
-{
- // modified sine curve
- const double pi = 3.141592654;
- const double sample_num_to_rad = num_input_samples_ / (4.5 * pi);
-
- // scale sample_number into the range [0...4.5*PI]
- const double x = sample_number / sample_num_to_rad;
-
- const double y_val = std::sin(x) + 1.0;
-
- const double y_top = get_operand1_size(sample_number);
- const double p0 = pi;
- double y_bottom;
- if (x <= p0)
- y_bottom = y_top / (x / p0 * 2.0 + 1.0) + 1.0;
- else
- y_bottom = y_top / 3.0;
-
- // we want to scale the curve at the point p1 to be above y_top at x = 2.5*pi
- const double p1 = 2.5 * pi;
-
- // here we use a function of the form y = -ax^2 + b to scale the curve at (and
- // around) p1
- const double a = 1.0/(p1 * p1);
- double adjust = -a * ((x-p1) * (x-p1)) + 1.0;
- // scale to be 10% above p1
- adjust *= 1.1;
- // stop scaling once we're past p1 and 'adjust' falls below 1.0
- if (x > p1 && adjust < 1.0)
- adjust = 1.0;
-
- return static_cast<unsigned long>(y_bottom * adjust * y_val + y_bottom);
-}
+ unsigned int stepsize = vec1.size() / 10;
-benchmark_runner::benchmark_runner(unsigned int num_input_samples,
- unsigned long operand_size_beg,
- unsigned long operand_size_end)
-:
- num_input_samples_(num_input_samples),
- beg_(operand_size_beg ? operand_size_beg : 1), // zero length not allowed
- end_(operand_size_end)
-{
-}
+ if (stepsize == 0)
+ stepsize = 1;
-void benchmark_runner::add_library(const boost::shared_ptr<benchmark_base>& b)
-{
- libs_.push_back(b);
-}
-
-void benchmark_runner::create_input_vectors(unsigned long min, unsigned long max)
-{
- std::ofstream iv_file("input_vecs.dat");
- if (!iv_file.is_open())
- throw std::runtime_error("couldn't open file input_vecs.dat");
-
- std::cout << "Creating " << num_input_samples_
- << " operand indices for numbers between "
- << min << " and " << max << " bits."
- << std::endl;
-
- const std::string rn = create_random_hex_string(max);
-
- std::cout << "creating input vectors";
- std::cout.flush();
-
- // create input vector where number size is determined by the sine function
- const unsigned int stepsize = num_input_samples_ / 10;
- for (unsigned int i = 0; i < num_input_samples_; ++i)
- {
- const unsigned long size1 = get_operand1_size(i);
- const unsigned long size2 = get_operand2_size(i);
-
- // divide by 4 because rn has max/4 hex digits
- string_vec1_.push_back(rn.substr(0, size1/4));
- string_vec2_.push_back(rn.substr(0, size2/4));
-
- // output the input sizes for a graph here
- iv_file << size1 << "\t" << size2 << "\n";
-
- if (((i+1) % stepsize) == 0)
- {
- std::cout << ".";
- std::cout.flush();
- }
- }
-
- std::cout << std::endl;
-
- iv_file.close();
-}
-
-void benchmark_runner::write_input_vector_plotfile(unsigned int x, unsigned int y) const
-{
- std::ofstream pf("input_vecs.plt");
- if (!pf.is_open())
- throw std::runtime_error("couldn't open plotfile");
- pf << "set term png size " << x << "," << y << "\n"
- "set output \"input_vecs.png\"\n"
- "set title \"input size of operands\"\n"
- "set key left\n"
- "set xlabel \"operand number\"\n"
- "set ylabel \"size in bits\"\n"
- "plot \"input_vecs.dat\" using 0:1 title \"operand 1 size\" with lines,\\\n"
- " \"input_vecs.dat\" using 0:2 title \"operand 2 size\" with lines";
-}
-
-void benchmark_runner::init_libs()
-{
- const unsigned long min_size =
- std::min(get_operand1_size(0),
- get_operand2_size(0));
-
- const unsigned long max_size =
- std::max(get_operand1_size(num_input_samples_),
- get_operand2_size(num_input_samples_));
-
- create_input_vectors(min_size, max_size);
-
- const unsigned int stepsize = num_input_samples_ / 10;
for (library_vec::iterator lib = libs_.begin(); lib != libs_.end(); ++lib)
{
- (*lib)->set_num_input_samples(num_input_samples_);
+ (*lib)->set_num_input_samples(vec1.size());
// init ctor strings
- std::string hex_s = create_random_hex_string(max_size);
- std::string dec_s = create_random_dec_string(max_size);
+ (*lib)->hex_str = hex_str_vec;
+ (*lib)->dec_str = dec_str_vec;
- for (unsigned int i = 0; i < num_input_samples_; ++i)
- {
- (*lib)->hex_str.push_back(hex_s.substr(0, get_operand1_size(i)/4));
- (*lib)->dec_str.push_back(dec_s.substr(0, get_operand1_size(i)));
- }
-
-
- std::cout << (*lib)->name() << "->"
- << "constructing operand 1 input vector";
+ std::cout << (*lib)->name() << "->constructing operand 1 input vector";
std::cout.flush();
- for (unsigned int i = 0; i < num_input_samples_; ++i)
+ for (unsigned int i = 0; i < vec1.size(); ++i)
{
- (*lib)->construct_operand_1(string_vec1_[i], i);
+ (*lib)->construct_operand_1(vec1[i], i);
if (((i+1) % stepsize) == 0)
{
std::cout << ".";
@@ -184,13 +45,12 @@
}
std::cout << std::endl;
- std::cout << (*lib)->name() << "->"
- << "constructing operand 2 input vector";
+ std::cout << (*lib)->name() << "->constructing operand 2 input vector";
std::cout.flush();
- for (unsigned int i = 0; i < num_input_samples_; ++i)
+ for (unsigned int i = 0; i < vec2.size(); ++i)
{
- (*lib)->construct_operand_2(string_vec2_[i], i);
+ (*lib)->construct_operand_2(vec2[i], i);
if (((i+1) % stepsize) == 0)
{
std::cout << ".";
@@ -199,6 +59,16 @@
}
std::cout << std::endl;
}
+
+ results_.clear();
+
+ for (std::vector<std::string>::const_iterator op = ops.begin(); op != ops.end(); ++op)
+ execute_bench_op(*op, sample_time);
+}
+
+void benchmark_runner::add_library(const boost::shared_ptr<benchmark_base>& b)
+{
+ libs_.push_back(b);
}
void benchmark_runner::execute_bench_op(const std::string& op, double sample_time)
@@ -217,134 +87,3 @@
}
}
-void benchmark_runner::create_data_files()
-{
- result_list::const_iterator r = results_.begin();
-
- // expects result list to be sorted by op name
- while (r != results_.end())
- {
- data_file d;
- result_list::const_iterator cur = r;
- while (r != results_.end() && r->op == cur->op)
- {
- data_file::column c;
-
- c.libname = r->libname;
- c.data = r->ops;
-
- // scale from ops per sample_time_ to ops per second
- /*const double scale = 1.0 / r->sample_time;
- for (std::vector<double>::iterator it = c.data.begin();
- it != c.data.end(); ++it)
- *it *= scale;*/
-
- c.total_ops = std::accumulate(r->ops.begin(), r->ops.end(), 0.);
- d.cols.push_back(c);
- ++r;
- }
-
- d.op = cur->op;
-
- d.cols.sort();
- dfiles_.push_back(d);
- }
-}
-
-void benchmark_runner::write_data_files() const
-{
- for (std::list<data_file>::const_iterator it = dfiles_.begin();
- it != dfiles_.end(); ++it)
- it->write();
-}
-
-void benchmark_runner::write_gnuplot_scripts(unsigned int x, unsigned int y) const
-{
- write_input_vector_plotfile(x, y);
- for (std::list<data_file>::const_iterator it = dfiles_.begin();
- it != dfiles_.end(); ++it)
- it->write_gnuplot_script(x, y);
-}
-
-void benchmark_runner::write_summary_file() const
-{
- std::ostringstream s;
- for (std::list<data_file>::const_iterator d = dfiles_.begin();
- d != dfiles_.end(); ++d)
- {
- s << d->op << "\n";
- for (std::list<data_file::column>::const_iterator c = d->cols.begin();
- c != d->cols.end(); ++ c)
- {
- s << c->libname << " total ops = " << c->total_ops << "\n";
- }
- }
-
- std::cout << s.str();
-
- std::ofstream file("summary.txt");
- if (!file.is_open())
- throw std::runtime_error("couldn't open summary.txt file");
- file << s.str();
-}
-
-void benchmark_runner::write_results(unsigned int x, unsigned int y) const
-{
- std::cout << "writing data files..." << std::endl;
- write_data_files();
- std::cout << "writing gnuplot scripts..." << std::endl;
- write_gnuplot_scripts(x, y);
- write_summary_file();
-}
-
-
-void data_file::write() const
-{
- const std::string filename(op + ".dat");
- std::ofstream file(filename.c_str());
- if (!file.is_open())
- throw std::runtime_error("couldn't open data file");
-
- const unsigned int col_len = cols.front().data.size();
- for (unsigned int i = 0; i < col_len; ++i)
- {
- std::list<column>::const_iterator it = cols.begin();
-
- while (it != cols.end())
- {
- file << it->data.at(i);
-
- if (++it != cols.end())
- file << "\t";
- }
- file << "\n";
- }
-}
-
-void data_file::write_gnuplot_script(unsigned int x, unsigned int y) const
-{
- const std::string filename(op + ".plt");
- std::ofstream file(filename.c_str());
- if (!file.is_open())
- throw std::runtime_error("couldn't open plot file");
-
- file << "set title \"" << op << "\"\n"
- "set xlabel " << "\"operand index\"\n"
- "set ylabel " << "\"ops/msec\"\n"
- "set autoscale\n"
- "set term png size " << x << "," << y << "\n"
- "set output \"" << op << ".png\"\n";
- file << "plot \\\n";
-
- std::list<column>::const_iterator it = cols.begin();
- int count = 1;
- while (it != cols.end())
- {
- file << '"' << op << ".dat\" using 0:" << count++ << " title \""
- << it->libname << "\" with lines";
- if (++it != cols.end())
- file << ",\\\n";
- }
- file << std::endl;
-}
-
Modified: sandbox/mp_math/libs/mp_math/tools/benchmark/benchmark_runner.hpp
==============================================================================
--- sandbox/mp_math/libs/mp_math/tools/benchmark/benchmark_runner.hpp (original)
+++ sandbox/mp_math/libs/mp_math/tools/benchmark/benchmark_runner.hpp 2008-11-03 14:18:42 EST (Mon, 03 Nov 2008)
@@ -10,69 +10,30 @@
#include "benchmark.hpp"
-struct data_file
-{
- struct column
- {
- std::string libname;
- std::vector<double> data;
- double total_ops;
- bool operator < (const column& rhs) const { return libname < rhs.libname; }
- };
-
- std::string op;
-
- std::list<column> cols;
-
- void write() const;
- void write_gnuplot_script(unsigned int x, unsigned int y) const;
-};
-
-
struct benchmark_runner
{
- benchmark_runner(unsigned int num_input_samples,
- unsigned long operand_size_beg,
- unsigned long operand_size_end);
-
// add a library
void add_library(const boost::shared_ptr<benchmark_base>& b);
// benches all operations given in ops
- void run(const std::vector<std::string>& ops, double sample_time);
-
- void write_data_files() const;
- void write_gnuplot_scripts(unsigned int x, unsigned int y) const;
- void write_summary_file() const;
-
- void write_results(unsigned int x, unsigned int y) const;
+ void run(const std::vector<std::string>& ops,
+ double sample_time,
+ const std::vector<std::string>& vec1,
+ const std::vector<std::string>& vec2,
+ const std::vector<std::string>& hex_str_vec,
+ const std::vector<std::string>& dec_str_vec);
void execute_bench_op(const std::string& op, double sample_time);
-private:
-
- void init_libs();
+ std::list<benchmark_result>& get_results() { return results_; }
- void create_data_files();
-
- void create_input_vectors(unsigned long min, unsigned long max);
- void write_input_vector_plotfile(unsigned int x, unsigned int y) const;
+private:
- unsigned long get_operand1_size(unsigned int) const;
- unsigned long get_operand2_size(unsigned int) const;
-
typedef std::vector<boost::shared_ptr<benchmark_base> > library_vec;
typedef std::list<benchmark_result> result_list;
- const unsigned int num_input_samples_;
- const unsigned long beg_;
- const unsigned long end_;
- std::vector<std::string> string_vec1_;
- std::vector<std::string> string_vec2_;
library_vec libs_;
result_list results_;
-
- std::list<data_file> dfiles_;
};
Modified: sandbox/mp_math/libs/mp_math/tools/benchmark/jamfile.v2
==============================================================================
--- sandbox/mp_math/libs/mp_math/tools/benchmark/jamfile.v2 (original)
+++ sandbox/mp_math/libs/mp_math/tools/benchmark/jamfile.v2 2008-11-03 14:18:42 EST (Mon, 03 Nov 2008)
@@ -12,13 +12,12 @@
<include>../../../..
<include>.
<link>static
- <toolset>gcc:<cxxflags>"-march=i686 -mtune=generic"
;
-# GMP (GNU Multiple Precision Arithmetic, http://gmplib.org/) library need to be
-# installed for the benchmark to work
+# GMP (GNU Multiple Precision Arithmetic, http://gmplib.org/) library needs to
+# be installed for the benchmark to work
# gmpxx is the library for the C++ bindings of gmp
lib gmpxx : : <name>gmpxx ;
lib gmp : : <name>gmp ;
@@ -33,13 +32,13 @@
benchmark_libtom.cpp
benchmark_gmp.cpp
main.cpp
+ modes.cpp
tommath
gmpxx gmp
boost_fs
boost_po
:
<variant>release
- <toolset>gcc:<cxxflags>-std=c++0x #-DBOOST_MP_MATH_MP_INT_USE_ASM"
;
Modified: sandbox/mp_math/libs/mp_math/tools/benchmark/main.cpp
==============================================================================
--- sandbox/mp_math/libs/mp_math/tools/benchmark/main.cpp (original)
+++ sandbox/mp_math/libs/mp_math/tools/benchmark/main.cpp 2008-11-03 14:18:42 EST (Mon, 03 Nov 2008)
@@ -15,18 +15,38 @@
#include "benchmark_libtom.hpp"
#include "benchmark_gmp.hpp"
+#include "modes.hpp"
-const char* version = "0.3";
+
+const char* version = "0.4";
struct config
{
- unsigned int graph_x, graph_y;
+ // mode can be 0, 1 or 2 which is:
+ // 0) run all modes
+ // 1) run with continuously sized operands, this benchmark takes long because
+ // it uses num_input_samples (default = 1000) operands, so it should be
+ // used for smaller numbers.
+ // 2) run benchmark with operands that are a power of two, this should be used
+ // to get a 'quick' look into how the functions perform for very large
+ // numbers.
+ unsigned int mode;
+
+ // mode 1 options
unsigned int num_input_samples;
double max_error;
double sample_time;
std::pair<unsigned int, unsigned int> range;
+ // mode 2 options
+ unsigned int pow_from;
+ unsigned int pow_to;
+ unsigned int pow_step;
+
+ // general options
+ unsigned int graph_x, graph_y;
+
typedef std::vector<std::string> string_list;
// we receive these two strings from the cmdline and need to tokenize them
std::string ops_string;
@@ -75,7 +95,18 @@
double config::estimated_run_time() const
{
- return sample_time * num_input_samples * ops.size() * libs.size();
+ const double mode1_time =
+ sample_time * num_input_samples * ops.size() * libs.size();
+
+ const double mode2_time = 0.05 * ops.size() * libs.size();
+
+ double sum = 0.0;
+ if (mode == 0 || mode == 1)
+ sum += mode1_time;
+ if (mode == 0 || mode == 2)
+ sum += mode2_time;
+
+ return sum;
}
@@ -86,7 +117,7 @@
double st = 0.01;
int verified = 0;
- while (true)
+ for (;;)
{
for (int k = 0; k < vec_length; ++k)
{
@@ -167,10 +198,39 @@
("version,v", "print version")
+ ("mode,m",
+ value(&c.mode)->default_value(1),
+ "0 = run all benchmarks\n"
+ "1 = run benchmark meant to test small numbers\n"
+ "2 = run benchmark meant to test large numbers")
+
+ ("ops",
+ value(&c.ops_string),
+ "the operations to benchmark")
+
+ ("libs",
+ value(&c.libs_string),
+ "the libraries to benchmark")
+
+ ("list-ops", "lists available operations")
+
+ ("list-libs", "lists available libraries")
+
+ ("x",
+ value(&c.graph_x)->default_value(1024),
+ "width of graphs created by gnuplot")
+ ("y",
+ value(&c.graph_y)->default_value(768),
+ "height of graphs created by gnuplot")
+ ;
+
+ options_description mode1_opts("Mode 1 options");
+
+ mode1_opts.add_options()
("num-input-samples,n",
value(&c.num_input_samples)->default_value(1000),
"number of input samples to create")
-
+
("max-error,e",
value(&c.max_error)->default_value(0.1, "0.1"),
"this value is used to calculate the sample time, you should not "
@@ -188,27 +248,28 @@
("range-end,b",
value(&c.range.second)->default_value(3072),
"range of numbers, measured in bits")
-
- ("ops",
- value(&c.ops_string),
- "the operations to benchmark")
-
- ("libs",
- value(&c.libs_string),
- "the libraries to benchmark")
-
- ("list-ops", "lists available operations")
-
- ("list-libs", "lists available libraries")
+ ;
- ("x",
- value(&c.graph_x)->default_value(1024),
- "width of graphs created by gnuplot")
- ("y",
- value(&c.graph_y)->default_value(768),
- "height of graphs created by gnuplot")
+ options_description mode2_opts("Mode 2 options");
+
+ mode2_opts.add_options()
+
+ ("pow-from,f",
+ value(&c.pow_from)->default_value(7),
+ "the first power of two to use")
+
+ ("pow-to,t",
+ value(&c.pow_to)->default_value(21),
+ "the last power of two to use")
+
+ ("pow-step,q",
+ value(&c.pow_step)->default_value(1),
+ "the stepsize used to iterate through the powers of two")
;
+ opts.add(mode1_opts);
+ opts.add(mode2_opts);
+
variables_map vm;
store(parse_command_line(argc, argv, opts), vm);
@@ -271,7 +332,7 @@
boost::filesystem::current_path(timestring);
- benchmark_runner b_runner(c.num_input_samples, c.range.first, c.range.second);
+ benchmark_runner b_runner;
std::cout << "Libraries that we are about to benchmark:\n";
for (string_list::const_iterator lib = c.libs.begin();
@@ -282,7 +343,7 @@
b_runner.add_library(p);
}
- if (!vm.count("sample-time"))
+ if (vm.count("sample-time") && c.sample_time == 0.0)
{
std::cout << "calibrating sample time..." << std::endl;
c.sample_time = calibrate_sample_time(c.max_error);
@@ -290,13 +351,33 @@
std::cout << "Sample time is: " << c.sample_time << " sec" << std::endl;
- const double runtime = c.estimated_run_time();
+ const unsigned long runtime =
+ static_cast<unsigned long>(c.estimated_run_time()/60.0);
std::cout << "Estimated run time of benchmark is at least "
- << (long)(runtime/60.0) << " minutes, but could be much longer for "
+ << runtime << " minute(s), but will be much longer for "
<< "very large numbers." << std::endl;
- b_runner.run(c.ops, c.sample_time);
- b_runner.write_results(c.graph_x, c.graph_y);
+ if (c.mode == 0 || c.mode == 1)
+ {
+ std::cout << "Entering mode 1..." << std::endl;
+ mode1 m1(c.num_input_samples, c.range.first, c.range.second);
+ b_runner.run(c.ops, c.sample_time,
+ m1.vec1, m1.vec2,
+ m1.hex_str_vec, m1.dec_str_vec);
+ m1.create_data_files(b_runner.get_results());
+ m1.write_results(c.graph_x, c.graph_y);
+ }
+
+ if (c.mode == 0 || c.mode == 2)
+ {
+ std::cout << "Entering mode 2..." << std::endl;
+ mode2 m2(c.pow_from, c.pow_to, c.pow_step);
+ b_runner.run(c.ops, 0.05,
+ m2.vec1, m2.vec2,
+ m2.hex_str_vec, m2.dec_str_vec);
+ m2.create_data_files(b_runner.get_results());
+ m2.write_results(c.graph_x, c.graph_y);
+ }
std::cout << "done with benchmarking!" << std::endl;
@@ -304,8 +385,8 @@
std::cout << "calling \'gnuplot *.plt\'" << std::endl;
const int ret = std::system("gnuplot *.plt");
if (ret)
- std::cout << "something went wrong, received the error code " << ret
- << std::endl;
+ std::cout << "something went wrong, gnuplot call exited with code " << ret
+ << std::endl;
else
std::cout << "done" << std::endl;
Added: sandbox/mp_math/libs/mp_math/tools/benchmark/modes.cpp
==============================================================================
--- (empty file)
+++ sandbox/mp_math/libs/mp_math/tools/benchmark/modes.cpp 2008-11-03 14:18:42 EST (Mon, 03 Nov 2008)
@@ -0,0 +1,426 @@
+// Copyright Kevin Sopp 2008.
+// 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)
+
+#include <cmath>
+#include <fstream>
+#include <iostream>
+#include <numeric> // accumulate
+#include <sstream>
+#include <stdexcept>
+#include <boost/random.hpp>
+#include <boost/mp_math/mp_int.hpp>
+
+#include "modes.hpp"
+
+std::string create_random_hex_string(unsigned size_in_bits)
+{
+ std::string s;
+ s.reserve(size_in_bits/4);
+
+ boost::mt19937 r;
+ boost::uniform_smallint<char> u(0,15);
+ boost::variate_generator<boost::mt19937&, boost::uniform_smallint<char> > vg(r, u);
+ // one hex digit occupies 4 bits
+ for (unsigned i = 0; i < (size_in_bits+3)/4; ++i)
+ {
+ char tmp = vg();
+ if (tmp < 10)
+ tmp = '0' + tmp;
+ else
+ tmp = 'a' + (tmp-10);
+ s.push_back(tmp);
+ }
+ return s;
+}
+
+std::string create_random_dec_string(unsigned size_in_digits)
+{
+ std::string s;
+ s.reserve(size_in_digits);
+
+ boost::mt19937 r;
+ boost::uniform_smallint<char> u(0,9);
+ boost::variate_generator<boost::mt19937&, boost::uniform_smallint<char> > vg(r, u);
+
+ for (unsigned i = 0; i < size_in_digits; ++i)
+ s.push_back('0' + vg());
+
+ return s;
+}
+
+
+void data_file::write(const std::string& prefix) const
+{
+ const std::string filename(prefix + op + ".dat");
+ std::ofstream file(filename.c_str());
+ if (!file.is_open())
+ throw std::runtime_error("couldn't open data file");
+
+ for (unsigned int i = 0; i < cols.front().data.size(); ++i)
+ {
+ file << x_values.at(i) << "\t";
+
+ std::list<column>::const_iterator it = cols.begin();
+
+ while (it != cols.end())
+ {
+ file << it->data.at(i);
+
+ if (++it != cols.end())
+ file << "\t";
+ }
+ file << "\n";
+ }
+}
+
+
+void write_gnuplot_scripts(unsigned int x, unsigned int y,
+ const std::string& modeprefix,
+ const std::string& xlabel,
+ const std::string& ylabel,
+ const std::list<data_file>& dfiles)
+{
+ for (std::list<data_file>::const_iterator df = dfiles.begin();
+ df != dfiles.end(); ++df)
+ {
+ const std::string filename(modeprefix + df->op + ".plt");
+ std::ofstream file(filename.c_str());
+ if (!file.is_open())
+ throw std::runtime_error("couldn't open plot file");
+
+ file << "set title \"" << df->op << "\"\n"
+ "set xlabel " << "\"" << xlabel << "\"\n"
+ "set ylabel " << "\"" << ylabel << "\"\n"
+ "set autoscale\n"
+ "set term png size " << x << "," << y << "\n"
+ "set output \"" << modeprefix << df->op << ".png\"\n";
+ file << "plot \\\n";
+
+ std::list<data_file::column>::const_iterator c = df->cols.begin();
+ int count = 2;
+ while (c != df->cols.end())
+ {
+ file << '"' << modeprefix << df->op << ".dat\" using 1:" << count++
+ << " title \"" << c->libname << "\" with lines";
+ if (++c != df->cols.end())
+ file << ",\\\n";
+ }
+ file << std::endl;
+ }
+}
+
+void write_data_files(const std::string& modeprefix,
+ const std::list<data_file>& dfiles)
+{
+ for (std::list<data_file>::const_iterator it = dfiles.begin();
+ it != dfiles.end(); ++it)
+ it->write(modeprefix);
+}
+
+
+mode1::mode1(unsigned int num_input_samples,
+ unsigned long operand_size_beg,
+ unsigned long operand_size_end)
+:
+ beg_(operand_size_beg ? operand_size_beg : 1), // zero length not allowed
+ end_(operand_size_end),
+ num_input_samples_(num_input_samples)
+{
+ std::ofstream iv_file("mode1_input_vecs.dat");
+ if (!iv_file.is_open())
+ throw std::runtime_error("couldn't open file mode1_input_vecs.dat");
+
+ const unsigned long min_size =
+ std::min(get_operand1_size(0),
+ get_operand2_size(0));
+
+ const unsigned long max_size =
+ std::max(get_operand1_size(num_input_samples_),
+ get_operand2_size(num_input_samples_));
+
+ std::cout << "Creating " << num_input_samples_
+ << " operand indices for numbers between "
+ << min_size << " and " << max_size << " bits."
+ << std::endl;
+
+ const std::string hex_s = create_random_hex_string(max_size);
+
+ std::cout << "creating input vectors";
+ std::cout.flush();
+
+ vec1.reserve(num_input_samples_);
+ vec2.reserve(num_input_samples_);
+ hex_str_vec.reserve(num_input_samples_);
+ dec_str_vec.reserve(num_input_samples_);
+
+ // create input vector where number size is determined by the sine function
+ const unsigned int stepsize = num_input_samples_ / 10;
+ for (unsigned int i = 0; i < num_input_samples_; ++i)
+ {
+ const unsigned long size1 = get_operand1_size(i);
+ const unsigned long size2 = get_operand2_size(i);
+
+ // divide by 4 because hex_s has max/4 hex digits
+ vec1.push_back(hex_s.substr(0, size1/4));
+ vec2.push_back(hex_s.substr(0, size2/4));
+
+ // output the input sizes for a graph here
+ iv_file << size1 << "\t" << size2 << "\n";
+
+ if (((i+1) % stepsize) == 0)
+ {
+ std::cout << ".";
+ std::cout.flush();
+ }
+ }
+
+ std::cout << std::endl;
+
+ iv_file.close();
+
+ // init ctor strings
+ for (unsigned int i = 0; i < num_input_samples_; ++i)
+ {
+ hex_str_vec.push_back(hex_s.substr(0, (get_operand1_size(i)+3)/4));
+ // use mp_int to ensure decimal string results in the same number of bits as
+ // the hex string
+ boost::mp_math::mp_int<> tmp(hex_str_vec.back(), std::ios::hex);
+ dec_str_vec.push_back(tmp.to_string<std::string>());
+ }
+}
+
+void mode1::create_data_files(std::list<benchmark_result>& results)
+{
+ std::list<benchmark_result>::const_iterator r = results.begin();
+
+ // expects result list to be sorted by op name
+ while (r != results.end())
+ {
+ data_file d;
+
+ for (unsigned i = 0; i < num_input_samples_; ++i)
+ d.x_values.push_back(i);
+
+ std::list<benchmark_result>::const_iterator cur = r;
+ while (r != results.end() && r->op == cur->op)
+ {
+ data_file::column c;
+
+ c.libname = r->libname;
+ c.data = r->ops;
+
+ // scale from ops per sample_time to ops per millisecond
+ for (std::vector<double>::iterator it = c.data.begin();
+ it != c.data.end(); ++it)
+ *it /= (r->sample_time * 1000.0);
+
+ c.sum = std::accumulate(r->ops.begin(), r->ops.end(), 0.);
+ d.cols.push_back(c);
+ ++r;
+ }
+
+ d.op = cur->op;
+
+ d.cols.sort();
+
+ dfiles_.push_back(d);
+ }
+}
+
+void mode1::write_input_vector_plotfile(unsigned int x, unsigned int y) const
+{
+ std::ofstream pf("mode1_input_vecs.plt");
+ if (!pf.is_open())
+ throw std::runtime_error("couldn't open plotfile");
+ pf << "set term png size " << x << "," << y << "\n"
+ "set output \"mode1_input_vecs.png\"\n"
+ "set title \"input size of operands\"\n"
+ "set key left\n"
+ "set xlabel \"operand number\"\n"
+ "set ylabel \"size in bits\"\n"
+ "plot \"mode1_input_vecs.dat\" using 0:1 title \"operand 1 size\" with lines,\\\n"
+ " \"mode1_input_vecs.dat\" using 0:2 title \"operand 2 size\" with lines";
+}
+
+void mode1::write_summary_file() const
+{
+ std::ostringstream s;
+ for (std::list<data_file>::const_iterator d = dfiles_.begin();
+ d != dfiles_.end(); ++d)
+ {
+ s << d->op << "------------------------------------\n";
+ for (std::list<data_file::column>::const_iterator c = d->cols.begin();
+ c != d->cols.end(); ++ c)
+ {
+ s << c->libname << " total ops = " << c->sum << "\n";
+ }
+ }
+
+ std::cout << s.str();
+
+ std::ofstream file("mode1_summary.txt");
+ if (!file.is_open())
+ throw std::runtime_error("couldn't open mode1_summary.txt file");
+ file << s.str();
+}
+
+void mode1::write_results(unsigned int x, unsigned int y) const
+{
+ write_input_vector_plotfile(x, y);
+
+ std::cout << "writing data files..." << std::endl;
+ write_data_files("mode1_", dfiles_);
+
+ std::cout << "writing gnuplot scripts..." << std::endl;
+ write_gnuplot_scripts(x, y, "mode1_", "operand index", "ops/msec", dfiles_);
+
+ write_summary_file();
+}
+
+
+unsigned long mode1::get_operand1_size(unsigned int sample_number) const
+{
+ // linear growth
+ const double m = static_cast<double>(end_ - beg_) /
+ static_cast<double>(num_input_samples_);
+ return (m * sample_number) + beg_;
+}
+
+unsigned long mode1::get_operand2_size(unsigned int sample_number) const
+{
+ // modified sine curve
+ const double pi = 3.141592654;
+ const double sample_num_to_rad = num_input_samples_ / (4.5 * pi);
+
+ // scale sample_number into the range [0...4.5*PI]
+ const double x = sample_number / sample_num_to_rad;
+
+ const double y_val = std::sin(x) + 1.0;
+
+ const double y_top = get_operand1_size(sample_number);
+ const double p0 = pi;
+ double y_bottom;
+ if (x <= p0)
+ y_bottom = y_top / (x / p0 * 2.0 + 1.0) + 1.0;
+ else
+ y_bottom = y_top / 3.0;
+
+ // we want to scale the curve at the point p1 to be above y_top at x = 2.5*pi
+ const double p1 = 2.5 * pi;
+
+ // here we use a function of the form y = -ax^2 + b to scale the curve at (and
+ // around) p1
+ const double a = 1.0/(p1 * p1);
+ double adjust = -a * ((x-p1) * (x-p1)) + 1.0;
+ // scale to be 10% above p1
+ adjust *= 1.1;
+ // stop scaling once we're past p1 and 'adjust' falls below 1.0
+ if (x > p1 && adjust < 1.0)
+ adjust = 1.0;
+
+ return static_cast<unsigned long>(y_bottom * adjust * y_val + y_bottom);
+}
+
+
+mode2::mode2(unsigned int pow_from, unsigned int pow_to, unsigned int stepsize)
+:
+ pow_from_(pow_from),
+ pow_to_(pow_to),
+ pow_step_(stepsize)
+{
+ const unsigned long max_size = 1UL << pow_to;
+
+ const std::string hex_s = create_random_hex_string((max_size+3)/4);
+
+ for (; pow_from < pow_to; pow_from += stepsize)
+ {
+ const unsigned long size = 1UL << pow_from;
+
+ vec1.push_back(hex_s.substr(0, size/4));
+
+ hex_str_vec.push_back(hex_s.substr(0, (size+3)/4));
+
+ boost::mp_math::mp_int<> tmp(hex_str_vec.back(), std::ios::hex);
+ dec_str_vec.push_back(tmp.to_string<std::string>());
+ }
+
+ vec2 = vec1;
+}
+
+
+void mode2::create_data_files(std::list<benchmark_result>& results)
+{
+ std::list<benchmark_result>::const_iterator r = results.begin();
+
+ // expects result list to be sorted by op name
+ while (r != results.end())
+ {
+ data_file d;
+
+ for (unsigned i = pow_from_; i < pow_to_; i += pow_step_)
+ d.x_values.push_back(i);
+
+ std::list<benchmark_result>::const_iterator cur = r;
+ while (r != results.end() && r->op == cur->op)
+ {
+ data_file::column c;
+
+ c.libname = r->libname;
+ c.data = r->ops;
+
+ // scale from ops per sample_time to seconds per op
+ for (std::vector<double>::iterator it = c.data.begin();
+ it != c.data.end(); ++it)
+ {
+ *it /= r->sample_time;
+ *it = 1.0 / *it;
+ }
+
+ c.sum = std::accumulate(r->ops.begin(), r->ops.end(), 0.);
+ d.cols.push_back(c);
+ ++r;
+ }
+
+ d.op = cur->op;
+
+ d.cols.sort();
+ dfiles_.push_back(d);
+ }
+}
+
+void mode2::write_summary_file() const
+{
+ std::ostringstream s;
+ for (std::list<data_file>::const_iterator d = dfiles_.begin();
+ d != dfiles_.end(); ++d)
+ {
+ s << d->op << "------------------------------------\n";
+ for (std::list<data_file::column>::const_iterator c = d->cols.begin();
+ c != d->cols.end(); ++ c)
+ {
+ s << c->libname << " total seconds = " << c->sum << "\n";
+ }
+ }
+
+ std::cout << s.str();
+
+ std::ofstream file("mode2_summary.txt");
+ if (!file.is_open())
+ throw std::runtime_error("couldn't open mode2_summary.txt file");
+ file << s.str();
+}
+
+void mode2::write_results(unsigned int x, unsigned int y) const
+{
+ std::cout << "writing data files..." << std::endl;
+ write_data_files("mode2_", dfiles_);
+
+ std::cout << "writing gnuplot scripts..." << std::endl;
+ write_gnuplot_scripts(x, y, "mode2_", "operand size (2^x)", "seconds/op",
+ dfiles_);
+
+ write_summary_file();
+}
+
Added: sandbox/mp_math/libs/mp_math/tools/benchmark/modes.hpp
==============================================================================
--- (empty file)
+++ sandbox/mp_math/libs/mp_math/tools/benchmark/modes.hpp 2008-11-03 14:18:42 EST (Mon, 03 Nov 2008)
@@ -0,0 +1,99 @@
+// Copyright Kevin Sopp 2008.
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_MP_MATH_TOOLS_MODES_HPP
+#define BOOST_MP_MATH_TOOLS_MODES_HPP
+
+#include <list>
+#include <string>
+#include <vector>
+
+#include "benchmark.hpp"
+
+
+std::string create_random_hex_string(unsigned size_in_bits);
+std::string create_random_dec_string(unsigned size_in_digits);
+
+
+struct data_file
+{
+ struct column
+ {
+ std::string libname;
+ std::vector<double> data;
+ double sum;
+ bool operator < (const column& rhs) const { return libname < rhs.libname; }
+ };
+
+ std::string op;
+
+ std::vector<unsigned> x_values;
+ std::list<column> cols; // the y-values
+
+ void write(const std::string& prefix) const;
+};
+
+
+void write_gnuplot_scripts(unsigned int x, unsigned int y,
+ const std::string& modeprefix,
+ const std::string& xlabel,
+ const std::string& ylabel,
+ const std::list<data_file>& dfiles);
+
+void write_data_files(const std::string& modeprefix,
+ const std::list<data_file>& dfiles);
+
+
+struct mode1
+{
+ mode1(unsigned int num_input_samples,
+ unsigned long operand_size_beg,
+ unsigned long operand_size_end);
+
+ void create_data_files(std::list<benchmark_result>&);
+ void write_input_vector_plotfile(unsigned int x, unsigned int y) const;
+ void write_summary_file() const;
+
+ void write_results(unsigned int x, unsigned int y) const;
+
+ std::vector<std::string> hex_str_vec; // hex ctor strings
+ std::vector<std::string> dec_str_vec; // dec ctor strings
+ std::vector<std::string> vec1;
+ std::vector<std::string> vec2;
+
+private:
+
+ unsigned long get_operand1_size(unsigned int sample_numer) const;
+ unsigned long get_operand2_size(unsigned int sample_numer) const;
+
+ unsigned long beg_, end_;
+ unsigned int num_input_samples_;
+ std::list<data_file> dfiles_;
+};
+
+
+struct mode2
+{
+ mode2(unsigned int pow_from, unsigned int pow_to, unsigned int stepsize);
+
+ void create_data_files(std::list<benchmark_result>&);
+ void write_summary_file() const;
+
+ void write_results(unsigned int x, unsigned int y) const;
+
+ std::vector<std::string> hex_str_vec; // hex ctor strings
+ std::vector<std::string> dec_str_vec; // dec ctor strings
+ std::vector<std::string> vec1;
+ std::vector<std::string> vec2;
+
+private:
+
+ unsigned int pow_from_, pow_to_, pow_step_;
+ std::list<data_file> dfiles_;
+};
+
+
+#endif
+