/******************************************************************************\* ** Advanced Problem 2 - "The Most Amazing Mathematical Formula" ** ** flamingspinach ** ** Started: 2006-10-06 ** Finished: 2006-10-06 ** ** NOTE: Made use of Euler's Formula to eliminate the need for complex<>. ** coprime() makes use of the Euclidean algorithm. ** *\******************************************************************************/#include <iostream>#include <iomanip>#include <ctime>#include <cmath>#define _PI 3.14159265358979using namespace std;bool coprime (int a, int b) { if (!b) return !(a-1); return coprime(b, a % b);}int P_recursive (int n, int k) { if (!n) return 1; if (k < 1 || n < 0) return 0; return P_recursive(n-k, k) + P_recursive(n, k-1);}int P_recursive (int n) { return P_recursive(n,n); }int P_Rademacher (int n) { double a, b, c, d, h, k, r, x; for (k = 1; k*k <= n; ++k) { a = sqrt(k)*pow(n-1/24.,-3/2.); b = sqrt(2/3.*_PI*_PI/k/k*(n-1/24.)); b = b * cosh(b) - sinh(b); for (c = 0, h = 1; h <= k; ++h) if (coprime(h,k)) { for (d = 0, r = 1; r <= k-1; ++r) d += r/k*(h*r/k - (int)(h*r/k) - 1/2.); c += cos(_PI*(d - 2.*h*n/k)); } x += a * b * c; } x *= 1/(_PI*sqrt(8)); return round(x);}int main () { double timer; int x; cout << setprecision(10); cout << "The first 50 values of p(n), by recursion: " << endl; for (int i = 0; i <= 50; ++i) { timer = -clock(); x = P_recursive(i); timer += clock(); cout << "p(" << setw(3) << i << ") = " << setw(15) << x << " Time: " << setw(10) << timer/CLK_TCK << endl; } cout << endl; cout << "The first 100 values of p(n), by Rademacher series: " << endl; for (int i = 0; i <= 100; ++i) { timer = -clock(); x = P_Rademacher(i); timer += clock(); cout << "p(" << setw(3) << i << ") = " << setw(15) << x << " Time: " << setw(10) << timer/CLK_TCK << endl; } system("pause"); return 0;}