////////////////////////////////////////////////////////////////////////////////
// pi 2.26 Dec 14 1999
// author: elephant <elephant AT linux DOT net DOT cn>

#include <iostream.h>
#include <math.h>
#include <sys/times.h>

void outputvalue(long long *value,long number)
{
	long a,i,j;
	cout<<value[0]<<".\n";
	cout.fill('0');
	for (i=1;i<=number/12;i++)
	{
		cout.width(12);
		cout<<value[i];
		if (!(i%8)) cout<<"\n";
	}
	cout.width(1);
	for (j=1;j<=number%12;j++)
	{
		long long last=value[i];
		for (a=0;a<12-j;a++) last=last/10;
		cout<<last%10;
	}
	cout<<"\n";
}

int main(int argc,char **argv)
{
	long number;
	cout<<"digits of pi you are expecting: ";
	cin>>number;
	if ((number>1000000)||(number<100))
	{
		cout<<"sorry, but I expect it between 100 and 1000000.\n";
		return(-1);
	}
	clock_t runtime=times(0);
	
	long a,i,j;
	long array=number/12+3;
	long long *base=new long long[array+1];
	long long *calc=new long long[array+1];
	long long *total=new long long[array+1];
	for (long i=0;i<=array;i++) total[i]=0;
	for (long step=0;step<2;step++)
	{
		long long remain;
		long head;
		long devide=(!step)?5:239;
		long devidedouble=devide*devide;
		remain=1;
		for (i=0;i<=array;i++)
		{
			base[i]=remain/devide;
//			remain=(remain%devide)*1000000000000LL;
/**/		remain=(remain-base[i]*devide)*1000000000000LL;
		}
		long loop=long(number*log(10)/log(devide)+1);
		double ratio=log(devide)/log(10)/12;
		long start;
		for (i=0;i<=array;i++) calc[i]=0;
		for (j=1;j<=loop;j++,j++)
		{
			start=long(j*ratio);
			remain=0;
			if (!(j&2))
				for (i=start;i<=array;)
				{
					a=i;
//					calc[i]+=remain/j;
//					remain=(remain%j)*1000000000000LL+base[++i];
/**/				long long q=remain/j;
/**/				calc[i]+=q;
/**/				remain-=q*j;
/**/				remain=remain*1000000000000LL+base[++i];
					while (calc[a]>=1000000000000LL)
					{
						calc[a]-=1000000000000LL;
						calc[--a]++;
					}
				}
			else
				for (i=start;i<=array;)
				{
					a=i;
//					calc[i]-=remain/j;
//					remain=(remain%j)*1000000000000LL+base[++i];
/**/				long long q=remain/j;
/**/				calc[i]-=q;
/**/				remain-=q*j;
/**/				remain=remain*1000000000000LL+base[++i];
					while (calc[a]<0)
					{
						calc[a]+=1000000000000LL;
						calc[--a]--;
					}
				}
			remain=0;
			if (!step)
			{
				head=j/12+2;
				for (i=start;(i<=array)&&(i<=head);)
				{
					base[i]=remain/devidedouble;
//					remain=(remain%devidedouble)*1000000000000LL+base[++i];
/**/				remain-=base[i]*devidedouble;
/**/				remain=remain*1000000000000LL+base[++i];
				}
			}
			else
				for (i=start;i<=array;)
				{
					base[i]=remain/devidedouble;
//					remain=(remain%devidedouble)*1000000000000LL+base[++i];
/**/				remain-=base[i]*devidedouble;
/**/				remain=remain*1000000000000LL+base[++i];
				}
		}
		if (!step)
		{
			total[array]+=calc[array]*16;
			for (i=array-1;i>=0;i--)
			{
				total[i]+=total[i+1]/1000000000000LL+calc[i]*16;
				total[i+1]%=1000000000000LL;
			}
		}
		else
		{
			long long tail;
			total[array]-=calc[array]*4;
			for (i=array-1;i>=0;i--)
			{
				tail=total[i+1]%1000000000000LL;
				total[i]+=total[i+1]/1000000000000LL-((tail<0)?1:0)-calc[i]*4;
				total[i+1]=tail+((tail<0)?1000000000000LL:0);
			}
		}
	}

	runtime=times(0)-runtime;
	cout<<"I'm glad to tell you that pi is ";
	outputvalue(total,number);
	cout<<"after calculated for "<<(float)runtime/100<<" seconds.\n";
	return(0);
}