jscaux
/
ABACUS
2
0
Çatalla 0
Kod Konular 1 Değişiklik İstekleri Sürüm Wiki Aktivite
ABACUS/include/ABACUS_Utils.h

500 satır
12 KiB
C++
Ham Kalıcı Bağlantı Suçlama Geçmiş

/**********************************************************
This software is part of J.-S. Caux's ABACUS library.
Copyright (c) J.-S. Caux.
-----------------------------------------------------------
File: ABACUS_util.h
Purpose: Defines basic math functions.
***********************************************************/
#ifndef ABACUS_UTIL_H
#define ABACUS_UTIL_H
#include "ABACUS.h"
typedef double DP;
// Global constants
const double PI = 3.141592653589793238462643;
const double sqrtPI = sqrt(PI);
const double twoPI = 2.0*PI;
const double logtwoPI = log(twoPI);
const double Euler_Mascheroni = 0.577215664901532860606;
const double Gamma_min_0p5 = -2.0 * sqrt(PI);
const std::complex<double> II(0.0,1.0); // Shorthand for i
const DP MACHINE_EPS = std::numeric_limits<DP>::epsilon();
const DP MACHINE_EPS_SQ = pow(MACHINE_EPS, 2.0);
// Now for some basic math utilities:
namespace ABACUS {
// Inexplicably missing string functions in standard library:
inline std::string DP_to_string (DP value) {
std::stringstream s;
s << std::setprecision(16) << value;
return s.str();
}
inline std::string replace(const std::string& str,
const std::string& from,
const std::string& to) {
std::string repl = str;
size_t start_pos = repl.find(from);
if(start_pos < std::string::npos)
repl.replace(start_pos, from.length(), to);
return repl;
}
inline std::string replace_all(const std::string& str,
const std::string& from,
const std::string& to) {
std::string repl = str;
if(from.empty())
return repl;
size_t start_pos = 0;
while((start_pos = repl.find(from, start_pos)) != std::string::npos) {
repl.replace(start_pos, from.length(), to);
start_pos += to.length();
}
return repl;
}
// File checks:
inline unsigned int count_lines(std::string filename)
{
std::ifstream infile(filename);
return(std::count(std::istreambuf_iterator<char>(infile),
std::istreambuf_iterator<char>(), '\n'));
}
inline bool file_exists (const char* filename)
{
std::fstream file;
file.open(filename);
bool exists = !file.fail();
file.close();
return(exists);
}
// Error handler:
inline void ABACUSerror (const std::string error_text)
// my error handler
{
std::cerr << "Run-time error... " << std::endl;
std::cerr << error_text << std::endl;
std::cerr << "Exiting to system..." << std::endl;
exit(1);
}
struct Divide_by_zero {};
// Basics: min, max, fabs
template<class T>
inline const T max (const T& a, const T& b) { return a > b ? (a) : (b); }
template<class T>
inline const T min (const T& a, const T& b) { return a > b ? (b) : (a); }
template<class T>
inline const T fabs (const T& a) { return a >= 0 ? (a) : (-a); }
inline long long int pow_lli (const long long int& base, const int& exp)
{
long long int answer = base;
if (exp == 0) answer = 1LL;
else for (int i = 1; i < exp; ++i) answer *= base;
return(answer);
}
inline unsigned long long int pow_ulli (const unsigned long long int& base, const int& exp)
{
unsigned long long int answer = base;
if (exp == 0) answer = 1ULL;
for (int i = 1; i < exp; ++i) answer *= base;
return(answer);
}
inline int fact (const int& N)
{
int ans = 0;
if (N < 0) {
std::cerr << "Error: factorial of negative number. Exited."
<< std::endl;
exit(1);
}
else if ( N == 1 || N == 0) ans = 1;
else ans = N * fact(N-1);
return(ans);
}
inline DP ln_fact (const int& N)
{
DP ans = 0.0;
if (N < 0) {
std::cerr << "Error: factorial of negative number. Exited."
<< std::endl;
exit(1);
}
else if ( N == 1 || N == 0) ans = 0.0;
else ans = log(DP(N)) + ln_fact(N-1);
return(ans);
}
inline long long int fact_lli (const int& N)
{
long long int ans = 0;
if (N < 0) {
std::cerr << "Error: factorial of negative number. Exited."
<< std::endl;
exit(1);
}
else if ( N == 1 || N == 0) ans = 1;
else ans = fact_lli(N-1) * N;
return(ans);
}
inline long long int fact_ulli (const int& N)
{
unsigned long long int ans = 0;
if (N < 0) {
std::cerr << "Error: factorial of negative number. Exited."
<< std::endl;
exit(1);
}
else if ( N == 1 || N == 0) ans = 1;
else ans = fact_ulli(N-1) * N;
return(ans);
}
inline int choose (const int& N1, const int& N2)
{
// returns N1 choose N2
int ans = 0;
if (N1 < N2) {
std::cout << "Error: N1 smaller than N2 in choose. Exited."
<< std::endl;
exit(1);
}
else if (N1 == N2) ans = 1;
else if (N1 < 12) ans = fact(N1)/(fact(N2) * fact(N1 - N2));
else {
ans = 1;
int mult = N1;
while (mult > max(N2, N1 - N2)) ans *= mult--;
ans /= fact(min(N2, N1 - N2));
}
return(ans);
}
inline DP ln_choose (const int& N1, const int& N2)
{
// returns the log of N1 choose N2
DP ans = 0.0;
if (N1 < N2) {
std::cout << "Error: N1 smaller than N2 in choose. Exited."
<< std::endl;
exit(1);
}
else if (N1 == N2) ans = 0.0;
else ans = ln_fact(N1) - ln_fact(N2) - ln_fact(N1 - N2);
return(ans);
}
inline long long int choose_lli (const int& N1, const int& N2)
{
// returns N1 choose N2
long long int ans = 0;
if (N1 < N2) {
std::cout << "Error: N1 smaller than N2 in choose. Exited."
<< std::endl;
exit(1);
}
else if (N1 == N2) ans = 1;
else if (N1 < 12) ans = fact_lli(N1)/(fact_lli(N2) * fact_lli(N1 - N2));
else {
// Make sure that N2 is less than or equal to N1/2; if not, just switch
int N2_min = min(N2, N1 - N2);
ans = 1;
for (int i = 0; i < N2_min; ++i) {
ans *= (N1 - i);
ans /= i + 1;
}
}
return(ans);
}
inline unsigned long long int choose_ulli (const int& N1, const int& N2)
{
// returns N1 choose N2
unsigned long long int ans = 0;
if (N1 < N2) {
std::cout << "Error: N1 smaller than N2 in choose. Exited."
<< std::endl;
exit(1);
}
else if (N1 == N2) ans = 1;
else if (N1 < 12) ans = fact_ulli(N1)/(fact_ulli(N2) * fact_ulli(N1 - N2));
else {
// Make sure that N2 is less than or equal to N1/2; if not, just switch
int N2_min = min(N2, N1 - N2);
ans = 1;
for (int i = 0; i < N2_min; ++i) {
ans *= (N1 - i);
ans /= i + 1;
}
}
return(ans);
}
inline DP SIGN (const DP &a, const DP &b)
{
return b >= 0 ? (a >= 0 ? a : -a) : (a >= 0 ? -a : a);
}
inline DP sign_of (const DP& a)
{
return (a >= 0.0 ? 1.0 : -1.0);
}
inline int sgn_int (const int& a)
{
return (a >= 0) ? 1 : -1;
}
inline int sgn_DP (const DP& a)
{
return (a >= 0) ? 1 : -1;
}
template<class T>
inline void SWAP (T& a, T& b) {T dum = a; a = b; b = dum;}
inline int kronecker (int a, int b)
{
return a == b ? 1 : 0;
}
template<class T>
inline bool is_nan (const T& a)
{
return(!((a < T(0.0)) || (a >= T(0.0))));
}
inline std::complex<DP> atan_cx(const std::complex<DP>& x)
{
return(-0.5 * II * log((1.0 + II* x)/(1.0 - II* x)));
}
/**************** Gamma function *******************/
inline std::complex<double> ln_Gamma (std::complex<double> z)
{
// Implementation of Lanczos method with g = 9.
// Coefficients from Godfrey 2001.
if (real(z) < 0.5) return(log(PI/(sin(PI*z))) - ln_Gamma(1.0 - z));
else {
std::complex<double> series = 1.000000000000000174663
+ 5716.400188274341379136/z
- 14815.30426768413909044/(z + 1.0)
+ 14291.49277657478554025/(z + 2.0)
- 6348.160217641458813289/(z + 3.0)
+ 1301.608286058321874105/(z + 4.0)
- 108.1767053514369634679/(z + 5.0)
+ 2.605696505611755827729/(z + 6.0)
- 0.7423452510201416151527e-2 / (z + 7.0)
+ 0.5384136432509564062961e-7 / (z + 8.0)
- 0.4023533141268236372067e-8 / (z + 9.0);
return(0.5 * logtwoPI + (z - 0.5) * log(z + 8.5)
- (z + 8.5) + log(series));
}
return(log(0.0)); // never called
}
inline std::complex<double> ln_Gamma_old (std::complex<double> z)
{
// Implementation of Lanczos method with g = 9.
// Coefficients from Godfrey 2001.
if (real(z) < 0.5) return(log(PI/(sin(PI*z))) - ln_Gamma(1.0 - z));
else {
int g = 9;
double p[11] = { 1.000000000000000174663,
5716.400188274341379136,
-14815.30426768413909044,
14291.49277657478554025,
-6348.160217641458813289,
1301.608286058321874105,
-108.1767053514369634679,
2.605696505611755827729,
-0.7423452510201416151527e-2,
0.5384136432509564062961e-7,
-0.4023533141268236372067e-8 };
std::complex<double> z_min_1 = z - 1.0;
std::complex<double> series = p[0];
for (int i = 1; i < g+2; ++i)
series += p[i]/(z_min_1 + std::complex<double>(i));
return(0.5 * logtwoPI
+ (z_min_1 + 0.5) * log(z_min_1 + std::complex<double>(g) + 0.5)
- (z_min_1 + std::complex<double>(g) + 0.5) + log(series));
}
return(log(0.0)); // never called
}
inline std::complex<double> ln_Gamma_2 (std::complex<double> z)
{
// Implementation of Lanczos method with g = 7.
if (real(z) < 0.5) return(log(PI/(sin(PI*z)) - ln_Gamma(1.0 - z)));
else {
int g = 7;
double p[9] = {
0.99999999999980993,
676.5203681218851,
-1259.1392167224028,
771.32342877765313,
-176.61502916214059,
12.507343278686905,
-0.13857109526572012,
9.9843695780195716e-6,
1.5056327351493116e-7
};
std::complex<double> z_min_1 = z - 1.0;
std::complex<double> series = p[0];
for (int i = 1; i < g+2; ++i)
series += p[i]/(z_min_1 + std::complex<double>(i));
return(0.5 * logtwoPI
+ (z_min_1 + 0.5) * log(z_min_1 + std::complex<double>(g) + 0.5)
- (z_min_1 + std::complex<double>(g) + 0.5) + log(series));
}
return(log(0.0)); // never called
}
/********** Partition numbers **********/
inline long long int Partition_Function (int n)
{
// Returns the value of the partition function p(n),
// giving the number of partitions of n into integers.
if (n < 0) ABACUSerror("Calling Partition_Function for n < 0.");
else if (n == 0 || n == 1) return(1LL);
else if (n == 2) return(2LL);
else if (n == 3) return(3LL);
else { // do recursion using pentagonal numbers
long long int pn = 0LL;
int pentnrplus, pentnrmin; // pentagonal numbers
for (int i = 1; true; ++i) {
pentnrplus = (i * (3*i - 1))/2;
pentnrmin = (i * (3*i + 1))/2;
if (n - pentnrplus >= 0) pn += (i % 2 ? 1LL : -1LL) * Partition_Function (n - pentnrplus);
if (n - pentnrmin >= 0) pn += (i % 2 ? 1LL : -1LL) * Partition_Function (n - pentnrmin);
else break;
}
return(pn);
}
return(-1LL); // never called
}
/********** Sorting **********/
template <class T>
void QuickSort (T* V, int l, int r)
{
int i = l, j = r;
T pivot = V[l + (r-l)/2];
while (i <= j) {
while (V[i] < pivot) i++;
while (V[j] > pivot) j--;
if (i <= j) {
std::swap(V[i],V[j]);
i++;
j--;
}
};
if (l < j) QuickSort(V, l, j);
if (i < r) QuickSort(V, i, r);
}
template <class T>
void QuickSort (T* V, int* index, int l, int r)
{
int i = l, j = r;
T pivot = V[l + (r-l)/2];
while (i <= j) {
while (V[i] < pivot) i++;
while (V[j] > pivot) j--;
if (i <= j) {
std::swap(V[i],V[j]);
std::swap(index[i],index[j]);
i++;
j--;
}
};
if (l < j) QuickSort(V, index, l, j);
if (i < r) QuickSort(V, index, i, r);
}
} // namespace ABACUS
#endif
Yeni konuda referans Git Suç Görüntüle Kalıcı Bağlantıyı Kopyala