r69:914ffb9b3798
Thu, 07 Feb 2008 23:33:38
[Not Reviewed]
0 comments (0 inline)
0
2
1
| 1 |
/* -*- C++ -*- |
|
| 2 |
* |
|
| 3 |
* This file is a part of LEMON, a generic C++ optimization library |
|
| 4 |
* |
|
| 5 |
* Copyright (C) 2003-2008 |
|
| 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
| 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
| 8 |
* |
|
| 9 |
* Permission to use, modify and distribute this software is granted |
|
| 10 |
* provided that this copyright notice appears in all copies. For |
|
| 11 |
* precise terms see the accompanying LICENSE file. |
|
| 12 |
* |
|
| 13 |
* This software is provided "AS IS" with no warranty of any kind, |
|
| 14 |
* express or implied, and with no claim as to its suitability for any |
|
| 15 |
* purpose. |
|
| 16 |
* |
|
| 17 |
*/ |
|
| 18 |
|
|
| 19 |
#ifndef LEMON_MATH_H |
|
| 20 |
#define LEMON_MATH_H |
|
| 21 |
|
|
| 22 |
///\ingroup misc |
|
| 23 |
///\file |
|
| 24 |
///\brief Some extensions to the standard \c cmath library. |
|
| 25 |
/// |
|
| 26 |
///Some extensions to the standard \c cmath library. |
|
| 27 |
/// |
|
| 28 |
///This file includes the standard math library (cmath). |
|
| 29 |
|
|
| 30 |
#include<cmath> |
|
| 31 |
|
|
| 32 |
namespace lemon {
|
|
| 33 |
|
|
| 34 |
/// \addtogroup misc |
|
| 35 |
/// @{
|
|
| 36 |
|
|
| 37 |
/// The Euler constant |
|
| 38 |
const long double E = 2.7182818284590452353602874713526625L; |
|
| 39 |
/// log_2(e) |
|
| 40 |
const long double LOG2E = 1.4426950408889634073599246810018921L; |
|
| 41 |
/// log_10(e) |
|
| 42 |
const long double LOG10E = 0.4342944819032518276511289189166051L; |
|
| 43 |
/// ln(2) |
|
| 44 |
const long double LN2 = 0.6931471805599453094172321214581766L; |
|
| 45 |
/// ln(10) |
|
| 46 |
const long double LN10 = 2.3025850929940456840179914546843642L; |
|
| 47 |
/// pi |
|
| 48 |
const long double PI = 3.1415926535897932384626433832795029L; |
|
| 49 |
/// pi/2 |
|
| 50 |
const long double PI_2 = 1.5707963267948966192313216916397514L; |
|
| 51 |
/// pi/4 |
|
| 52 |
const long double PI_4 = 0.7853981633974483096156608458198757L; |
|
| 53 |
/// sqrt(2) |
|
| 54 |
const long double SQRT2 = 1.4142135623730950488016887242096981L; |
|
| 55 |
/// 1/sqrt(2) |
|
| 56 |
const long double SQRT1_2 = 0.7071067811865475244008443621048490L; |
|
| 57 |
|
|
| 58 |
|
|
| 59 |
/// @} |
|
| 60 |
|
|
| 61 |
} //namespace lemon |
|
| 62 |
|
|
| 63 |
#endif //LEMON_TOLERANCE_H |
| 1 | 1 |
EXTRA_DIST += \ |
| 2 | 2 |
lemon/Makefile \ |
| 3 | 3 |
lemon/lemon.pc.in |
| 4 | 4 |
|
| 5 | 5 |
pkgconfig_DATA += lemon/lemon.pc |
| 6 | 6 |
|
| 7 | 7 |
lib_LTLIBRARIES += lemon/libemon.la |
| 8 | 8 |
|
| 9 | 9 |
lemon_libemon_la_SOURCES = \ |
| 10 | 10 |
lemon/base.cc \ |
| 11 | 11 |
lemon/random.cc |
| 12 | 12 |
|
| 13 | 13 |
|
| 14 | 14 |
lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) |
| 15 | 15 |
lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS) |
| 16 | 16 |
|
| 17 | 17 |
lemon_HEADERS += \ |
| 18 | 18 |
lemon/concept_check.h \ |
| 19 | 19 |
lemon/dim2.h \ |
| 20 | 20 |
lemon/error.h \ |
| 21 | 21 |
lemon/list_graph.h \ |
| 22 | 22 |
lemon/maps.h \ |
| 23 |
lemon/math.h \ |
|
| 23 | 24 |
lemon/random.h \ |
| 24 | 25 |
lemon/tolerance.h |
| 25 | 26 |
|
| 26 | 27 |
bits_HEADERS += \ |
| 27 | 28 |
lemon/bits/alteration_notifier.h \ |
| 28 | 29 |
lemon/bits/array_map.h \ |
| 29 | 30 |
lemon/bits/base_extender.h \ |
| 30 | 31 |
lemon/bits/default_map.h \ |
| 31 | 32 |
lemon/bits/graph_extender.h \ |
| 32 | 33 |
lemon/bits/invalid.h \ |
| 33 | 34 |
lemon/bits/map_extender.h \ |
| 34 | 35 |
lemon/bits/traits.h \ |
| 35 | 36 |
lemon/bits/utility.h \ |
| 36 | 37 |
lemon/bits/vector_map.h |
| 37 | 38 |
|
| 38 | 39 |
concept_HEADERS += \ |
| 39 | 40 |
lemon/concept_check.h \ |
| 40 | 41 |
lemon/concepts/digraph.h \ |
| 41 | 42 |
lemon/concepts/graph.h \ |
| 42 | 43 |
lemon/concepts/maps.h \ |
| 43 | 44 |
lemon/concepts/graph_components.h |
| ... | ... |
@@ -46,51 +46,52 @@ |
| 46 | 46 |
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE |
| 47 | 47 |
* COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, |
| 48 | 48 |
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES |
| 49 | 49 |
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR |
| 50 | 50 |
* SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
| 51 | 51 |
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
| 52 | 52 |
* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| 53 | 53 |
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED |
| 54 | 54 |
* OF THE POSSIBILITY OF SUCH DAMAGE. |
| 55 | 55 |
* |
| 56 | 56 |
* |
| 57 | 57 |
* Any feedback is very welcome. |
| 58 | 58 |
* http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html |
| 59 | 59 |
* email: m-mat @ math.sci.hiroshima-u.ac.jp (remove space) |
| 60 | 60 |
*/ |
| 61 | 61 |
|
| 62 | 62 |
#ifndef LEMON_RANDOM_H |
| 63 | 63 |
#define LEMON_RANDOM_H |
| 64 | 64 |
|
| 65 | 65 |
#include <algorithm> |
| 66 | 66 |
#include <iterator> |
| 67 | 67 |
#include <vector> |
| 68 | 68 |
|
| 69 | 69 |
#include <ctime> |
| 70 |
#include <cmath> |
|
| 71 | 70 |
|
| 71 |
#include <lemon/math.h> |
|
| 72 | 72 |
#include <lemon/dim2.h> |
| 73 |
|
|
| 73 | 74 |
///\ingroup misc |
| 74 | 75 |
///\file |
| 75 | 76 |
///\brief Mersenne Twister random number generator |
| 76 | 77 |
|
| 77 | 78 |
namespace lemon {
|
| 78 | 79 |
|
| 79 | 80 |
namespace _random_bits {
|
| 80 | 81 |
|
| 81 | 82 |
template <typename _Word, int _bits = std::numeric_limits<_Word>::digits> |
| 82 | 83 |
struct RandomTraits {};
|
| 83 | 84 |
|
| 84 | 85 |
template <typename _Word> |
| 85 | 86 |
struct RandomTraits<_Word, 32> {
|
| 86 | 87 |
|
| 87 | 88 |
typedef _Word Word; |
| 88 | 89 |
static const int bits = 32; |
| 89 | 90 |
|
| 90 | 91 |
static const int length = 624; |
| 91 | 92 |
static const int shift = 397; |
| 92 | 93 |
|
| 93 | 94 |
static const Word mul = 0x6c078965u; |
| 94 | 95 |
static const Word arrayInit = 0x012BD6AAu; |
| 95 | 96 |
static const Word arrayMul1 = 0x0019660Du; |
| 96 | 97 |
static const Word arrayMul2 = 0x5D588B65u; |
| ... | ... |
@@ -738,49 +739,49 @@ |
| 738 | 739 |
|
| 739 | 740 |
/// Gamma distribution with given integer shape |
| 740 | 741 |
|
| 741 | 742 |
/// This function generates a gamma distribution random number. |
| 742 | 743 |
/// |
| 743 | 744 |
///\param k shape parameter (<tt>k>0</tt> integer) |
| 744 | 745 |
double gamma(int k) |
| 745 | 746 |
{
|
| 746 | 747 |
double s = 0; |
| 747 | 748 |
for(int i=0;i<k;i++) s-=std::log(1.0-real<double>()); |
| 748 | 749 |
return s; |
| 749 | 750 |
} |
| 750 | 751 |
|
| 751 | 752 |
/// Gamma distribution with given shape and scale parameter |
| 752 | 753 |
|
| 753 | 754 |
/// This function generates a gamma distribution random number. |
| 754 | 755 |
/// |
| 755 | 756 |
///\param k shape parameter (<tt>k>0</tt>) |
| 756 | 757 |
///\param theta scale parameter |
| 757 | 758 |
/// |
| 758 | 759 |
double gamma(double k,double theta=1.0) |
| 759 | 760 |
{
|
| 760 | 761 |
double xi,nu; |
| 761 | 762 |
const double delta = k-std::floor(k); |
| 762 |
const double v0= |
|
| 763 |
const double v0=E/(E-delta); |
|
| 763 | 764 |
do {
|
| 764 | 765 |
double V0=1.0-real<double>(); |
| 765 | 766 |
double V1=1.0-real<double>(); |
| 766 | 767 |
double V2=1.0-real<double>(); |
| 767 | 768 |
if(V2<=v0) |
| 768 | 769 |
{
|
| 769 | 770 |
xi=std::pow(V1,1.0/delta); |
| 770 | 771 |
nu=V0*std::pow(xi,delta-1.0); |
| 771 | 772 |
} |
| 772 | 773 |
else |
| 773 | 774 |
{
|
| 774 | 775 |
xi=1.0-std::log(V1); |
| 775 | 776 |
nu=V0*std::exp(-xi); |
| 776 | 777 |
} |
| 777 | 778 |
} while(nu>std::pow(xi,delta-1.0)*std::exp(-xi)); |
| 778 | 779 |
return theta*(xi-gamma(int(std::floor(k)))); |
| 779 | 780 |
} |
| 780 | 781 |
|
| 781 | 782 |
/// Weibull distribution |
| 782 | 783 |
|
| 783 | 784 |
/// This function generates a Weibull distribution random number. |
| 784 | 785 |
/// |
| 785 | 786 |
///\param k shape parameter (<tt>k>0</tt>) |
| 786 | 787 |
///\param lambda scale parameter (<tt>lambda>0</tt>) |
0 comments (0 inline)