アルゴリズム
Posted: 2007年10月07日(日) 00:37
#include <stdio.h>
#define MAX 5001 /* 配列の大きさ */
#define DIGIT 7500 /* n の最大値 */
void print_box(int [/url]); /* 配列の中身を表示する */
void copy_box(int [/url], int [/url]); /* 配列をコピーする */
void addition(int [/url], int [/url], int [/url]); /* 足し算 */
void subtraction(int [/url], int [/url], int [/url]); /* 引き算 */
void division(int [/url], int, int [/url]); /* 配列 ÷ 整数 */
void division_int(int, int, int [/url]); /* 整数 ÷ 整数 */
int pi[MAX], ans1[MAX], ans2[MAX];
int tmp[MAX], a[MAX], b[MAX], c[MAX];
int main()
{
int i, n;
/*-----------*/
/* 5 */
/*-----------*/
division_int(16, 5, ans1);
copy_box(ans1, tmp);
for( i=1, n=0 ; n+2 <= DIGIT ; i++ ){
n = 2 * i + 1;
division(tmp, 5*5, a);
copy_box(a, tmp); /* ○ ÷ 5^2 の値を退避 */
division(a, n, b); /* ○ ÷ n */
if( i % 2 == 0 ) /* i: 偶数なら */
addition(ans1, b, c); /* + */
else /* i: 奇数なら */
subtraction(ans1, b, c); /* - */
copy_box(c, ans1);
}
/*-----------*/
/* 239 */
/*-----------*/
division_int(4, 239, ans2);
copy_box(ans2, tmp);
for( i=1, n=0 ; n+2 <= DIGIT ; i++ ){
n = 2 * i + 1;
division(tmp, 239*239, a);
copy_box(a, tmp);
division(a, n, b);
if( i % 2 == 0 )
addition(ans2, b, c);
else
subtraction(ans2, b, c);
copy_box(c, ans2);
}
/*----------*/
/* π */
/*----------*/
subtraction(ans1, ans2, pi);
print_box(pi);
return 0;
}
void print_box(int box[/url])
{
int i;
printf("%5d.", box[0]);
for( i=1 ; i < MAX ; i++ )
printf("%d", box);
printf("\n");
}
void copy_box(int from[/url], int to[/url]){
int i;
for( i=0 ; i < MAX ; i++ )
to = from;
}
void addition(int x[/url], int y[/url], int answer[/url])
{
int i, carry=0;
for( i=MAX-1 ; i > 0 ; i-- ){
answer = (x + y + carry) % 10;
carry = (x + y + carry) / 10;
}
answer[0] = x[0] + y[0] + carry;
}
void subtraction(int x[/url], int y[/url], int answer[/url])
{
int i;
for( i=MAX-1 ; i > 0 ; i-- ){
if( x >= y ){
answer[i] = x[i] - y[i];
}else{
x[i-1] = x[i-1] - 1;
answer[i] = x[i] + 10 - y[i];
}
}
answer[0] = x[0] - y[0];
}
void division(int x[/url], int y, int box[/url])
{
int i, surplus=0;
for( i=0 ; i < MAX ; i++ ){
box[i] = (surplus * 10 + x[i]) / y;
surplus = (surplus * 10 + x[i]) % y;
}
}
void division_int(int x, int y, int box[/url])
{
int i, surplus;
box[0] = x / y;
surplus = x % y;
for( i=1 ; i < MAX ; i++ ){
box[i] = surplus * 10 / y;
surplus = surplus * 10 % y;
}
}
上のプログラムの簡単なアルゴリズムを教えていただけないでしょうか?
ちなみに、「πをマーチンの公式を使って7500桁(この場合)求める」プログラムです