/* struct Place : 求 N 有多少位数字
*/
template <long long N>
struct Place;
template <long long N>
struct Place
{
static const int value = Place<N / 10>::value + 1;
static const int place = value;
};
template <>
struct Place<0>
{
static const int value = 0;
static const int place = 1;
};
/* struct Sqrt : 开平方，结果为 value
*/
template <long long N>
struct Sqrt;
/* struct Exp10 : 10 的 N 次方幂，也就是 1 后加 N 个零
*/
template <int N>
struct Exp10
{
static const long long value = Exp10<N-1>::value * 10;
};
template <>
struct Exp10<0>
{
static const long long value = 1;
};
/* struct SqrtTwoPlace : 求两位数以下的整数的平方根
*/
template <long long N>
struct SqrtTwoPlace
{
static const long long value = SqrtTwoPlace<N-1>::value;
};
#define SqrtTwoPlaceDef(NN, N) template <> struct SqrtTwoPlace<NN> { static const long long value = N; }
SqrtTwoPlaceDef (0, 0);
SqrtTwoPlaceDef (1, 1);
SqrtTwoPlaceDef (4, 2);
SqrtTwoPlaceDef (9, 3);
SqrtTwoPlaceDef (16, 4);
SqrtTwoPlaceDef (25, 5);
SqrtTwoPlaceDef (36, 6);
SqrtTwoPlaceDef (49, 7);
SqrtTwoPlaceDef (64, 8);
SqrtTwoPlaceDef (81, 9);
/* struct SqrtDiv : 求 N 开平方的结果
*/
template <bool finish, long long N, long long x>
struct SqrtDiv;
template <long long N, long long x0>
struct SqrtDiv<false, N, x0>
{
private:
static const long long x = (N / x0 + x0) / 2;
static const bool finish = (x*x <= N) && ((x+1)*(x+1) > N);
public:
static const long long value = SqrtDiv<finish, N, x>::value;
};
template <long long N, long long x>
struct SqrtDiv<true, N, x>
{
static const long long value = x;
};
/* struct Sqrt : 开平方
*/
template <long long N>
struct Sqrt
{
private:
static const int place = Place<N>::value;
static const int zero = (place % 2 == 1) ? place - 1 : place - 2;
static const long long head = N / Exp10<zero>::value;
static const long long x0 = SqrtTwoPlace<head>::value
* Exp10<zero / 2>::value;
public:
static const long long value = SqrtDiv<false, N, x0>::value;
};
template <>
struct Sqrt<0>
{
static const long long value = 0;
};
/* struct Fraction : 分数，first 为分子，second 为分母。value 为 double 值
*/
template <long long M, long long N>
struct Fraction;
template <long long M, long long N>
struct Fraction
{
static const long long first = M;
static const long long second = N;
static const double value = static_cast<double>(first) / second;
};
/* struct FractionSqrt : 开平方。分子、分母同时开方
*/
template <typename FractionType>
struct FractionSqrt
{
private:
static const long long first1 = FractionType::first;
static const long long second1 = FractionType::second;
static const long long first = Sqrt<first1>::value;
static const long long second = Sqrt<second1>::value;
public:
typedef Fraction<first, second> ValueType;
};
/* struct FractionSqrt2 : 开平方，但保持分母不变
*/
template <typename FractionType>
struct FractionSqrt2
{
private:
static const long long first1 = FractionType::first;
static const long long second = FractionType::second;
static const long long first = Sqrt<first1 * second>::value;
public:
typedef Fraction<first, second> ValueType;
};
/* struct FractionAdd : 加法，结果为 ValueType
*/
template <typename FractionType1, typename FractionType2>
struct FractionAdd
{
private:
static const long long first1 = FractionType1::first;
static const long long second1 = FractionType1::second;
static const long long first2 = FractionType2::first;
static const long long second2 = FractionType2::second;
static const long long first = first1 * second2 + first2 * second1;
static const long long second = second1 * second2;
public:
typedef Fraction<first, second> ValueType;
};
template <long long First1, long long First2, long long Second>
struct FractionAdd<Fraction<First1, Second>, Fraction<First2, Second> >
{
private:
static const long long first = First1 + First2;
static const long long second = Second;
public:
typedef Fraction<first, second> ValueType;
};
/* struct FractionSub : 减法，结果为 ValueType
*/
template <typename FractionType1, typename FractionType2>
struct FractionSub
{
private:
static const long long first1 = FractionType1::first;
static const long long second1 = FractionType1::second;
static const long long first2 = FractionType2::first;
static const long long second2 = FractionType2::second;
static const long long first = first1 * second2 - first2 * second1;
static const long long second = second1 * second2;
public:
typedef Fraction<first, second> ValueType;
};
template <long long First1, long long First2, long long Second>
struct FractionSub<Fraction<First1, Second>, Fraction<First2, Second> >
{
private:
static const long long first = First1 - First2;
static const long long second = Second;
public:
typedef Fraction<first, second> ValueType;
};
/* struct FractionMul : 乘法，结果在 ValueType
*/
template <typename FractionType1, typename FractionType2>
struct FractionMul
{
private:
static const long long first1 = FractionType1::first;
static const long long second1 = FractionType1::second;
static const long long first2 = FractionType2::first;
static const long long second2 = FractionType2::second;
static const long long first = first1 * first2;
static const long long second = second1 * second2;
public:
typedef Fraction<first, second> ValueType;
};
template <long long First1, long long First2, long long Second1>
struct FractionMul<Fraction<First1, Second1>, Fraction<First2, First1> >
{
private:
static const long long first = First2;
static const long long second = Second1;
public:
typedef Fraction<first, second> ValueType;
};
template <long long First1, long long First2, long long Second1>
struct FractionMul<Fraction<First2, First1>, Fraction<First1, Second1> >
{
private:
static const long long first = First2;
static const long long second = Second1;
public:
typedef Fraction<first, second> ValueType;
};
template <long long First, long long Second>
struct FractionMul<Fraction<First, Second>, Fraction<Second, First> >
{
private:
static const long long first = 1;
static const long long second = 1;
public:
typedef Fraction<first, second> ValueType;
};
/* struct FractionDiv : 除法，结果为 ValueType
*/
template <typename FractionType1, typename FractionType2>
struct FractionDiv
{
private:
static const long long first1 = FractionType1::first;
static const long long second1 = FractionType1::second;
static const long long first2 = FractionType2::first;
static const long long second2 = FractionType2::second;
static const long long first = first1 * second2;
static const long long second = first2 * second1;
public:
typedef Fraction<first, second> ValueType;
};
template <long long First1, long long First2, long long Second>
struct FractionDiv<Fraction<First1, Second>, Fraction<First2, Second> >
{
private:
static const long long first = First1;
static const long long second = First2;
public:
typedef Fraction<first, second> ValueType;
};
template <long long First, long long Second1, long long Second2>
struct FractionDiv<Fraction<First, Second1>, Fraction<First, Second2> >
{
private:
static const long long first = Second2;
static const long long second = Second1;
public:
typedef Fraction<first, second> ValueType;
};
template <long long First, long long Second>
struct FractionDiv<Fraction<First, Second>, Fraction<First, Second> >
{
private:
static const long long first = 1;
static const long long second = 1;
public:
typedef Fraction<first, second> ValueType;
};
/* struct FractionAdjust : 调整分母，使分母的大小为 SECOND
*/
template <typename FractionType, long long SECOND = 100000000LL>
struct FractionAdjust
{
private:
static const long long first1 = FractionType::first;
static const long long second1 = FractionType::second;
static const long long first2 = ((second1 < SECOND)
? SECOND * first1 : first1);
static const long long second2 = ((second1 < SECOND)
? SECOND * second1 : second1);
static const long long div = second2 / SECOND;
static const long long first = first2 / div;
static const long long second = second2 / div;
public:
typedef Fraction<first, second> ValueType;
};
/* struct PI : 是一个 Fraction，
*/
struct PI;
static const long long BASE = 100000000LL;
typedef Fraction<2, 1> Two; // 常量 2
/* struct PIItem : 是 Pi 的一项
*/
template <int N>
struct PIItem
{
private:
typedef typename PIItem<N-1>::ValueType Value1;
typedef typename PIItem<N-1>::ItemType Item1;
typedef typename FractionAdd<Item1, Two>::ValueType ItemAddTwo;
public:
typedef typename FractionSqrt2<ItemAddTwo>::ValueType ItemType;
private:
typedef typename FractionDiv<Two, ItemType>::ValueType TwoDivItem;
typedef typename FractionMul<Value1, TwoDivItem>::ValueType ValueResult;
public:
typedef typename FractionAdjust<ValueResult, BASE>::ValueType ValueType;
};
template <>
struct PIItem<0>
{
typedef Two ValueType;
typedef Fraction<0, BASE> ItemType;
};
struct PI : public PIItem<50>::ValueType
{
};
#include <iostream>
#include <cstdlib>
using namespace std;
int
main ()
{
cout.precision (10);
cout << PIItem<0>::ItemType::value << endl;
cout.precision (10);
cout << PIItem<1>::ItemType::value << endl;
cout.precision (10);
cout << PIItem<2>::ItemType::value << endl;
cout.precision (10);
cout << PIItem<4>::ItemType::value << endl;
cout.precision (10);
cout << PIItem<8>::ItemType::value << endl;
cout.precision (10);
cout << PIItem<16>::ItemType::value << endl;
cout.precision (10);
cout << PIItem<32>::ItemType::value << endl;
cout.precision (10);
cout << PIItem<64>::ItemType::value << endl;
cout.precision (10);
cout << PIItem<128>::ItemType::value << endl;
cout.precision (10);
cout << PI::value << endl;
system ("Pause");
return 0;
}
