원주율 구하는 알고리즘 - wonjuyul guhaneun algolijeum

원주율을 간단한 코딩을 통해 구해 보자.


C언어를 이용해 계산을 할 경우에, 원주율의 수치가 필요한 경우가 가끔 있다. 이럴 때 가장 간편한 방법은 define 을 이용해 파이의 변수와 값을 저장해 주는 것이다. 하지만 파이의 정의(수식을 이용한 원주율의 값)를 이용하여 원주율을 구할 수 있다.

원주율은 우리가 일상 생활에서는 파이 라고 간단히 쓰지만, 사실 무리수다. 즉, 정확한 값을 나타낼 수는 없고, 근삿값으로 계산할 수 밖에 없다. 주로 쓰는 원주율은 3.14라고 쓰기에도 충분하지만, 정확한 값을 요구하는 계산에선 더 정확한 값의 원주율을 요구할 수도 있다. 선대의 수학자들은 원주율을 무한급수 형태의 계산식을 통해 원주율을 구했다. 이 계산식을 이용해 원주율을 구해보자.

일단 여기서는 3가지 식을 다룰 것이다. 첫 번째는 라이프니츠의 공식, 두 번째는 월리스 공식, 세 번째는 오일러 곱셈 공식 이다. 1번부터 알아보자.

1. 라이프니츠의 공식


원주율 구하는 알고리즘 - wonjuyul guhaneun algolijeum

라이프니츠의 공식은 1/1-1/3+1/5.... 를 더한 것에 4를 곱한 것이다.

정확성을 위해서 100만번 정도 식을 반복해 주자.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

#include <stdio.h> //라이프니츠의 공식  

int main()

{

double pi=0,temp=1,p=-1,num=1;

while(num<10000000)

{

p*=-1;

pi+=p*1.0/temp;

temp+=2;

num++;

}

printf("%.10f",4*pi);

}

cs

2. 윌리스 공식


분자는 짝수가 계속 따라오고, 분모에는 홀수가 계속 따라온다. 둘은 서로 어긋난 상태로 반복이 된다.

이것도 마찬가지로 100만번 반복하자.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

#include <stdio.h> //월리스 공식 

int main()

{

double pi=1,even=2.0,odd=1.0;

int num=1;

while(num<10000000)

{

pi*=even/odd;

if(num%2==1) odd+=2;

else even+=2;

num++;

}

printf("%.10f",2.0*pi);

}

cs

3. 오일러의 곱셈 공식


유명한 공식이다. 1부터 1씩 커지는 수의 역수를 더한 것은 원주율 제곱 나누기 6이 된다.

즉, 무한급수를 한 것에 6을 곱한다음, 그 수에 루트를 더하면 원주율이 나온다.

역시 100만번 반복하자.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

#include <stdio.h> //오일러 곱셈 공식 

#include <math.h>

int main()

{

double pi=0.0,num=1.0;

while(num<1000000)

{

pi+=1.0/pow(num,2.0);

num+=1.0;

}

printf("%.10f",sqrt(6*pi));

cs

이번 포스트에선 원주율의 정의를 이용해 원주율의 값을 계산해 보았다. 배열을 이용하는 방법도 있으나, 간단히 double 형태의 수를 이용해 구해보았다.

double 의 정밀도가 원주율의 값을 계산해 보이기엔 분명히 한계가 존재한다. 하지만, 계산식을 이용해 원주율을 구하는 데 의의를 두면 좋을 것 같다고 생각한다.

사진 출저 : https://ko.wikipedia.org/wiki/%EC%9B%90%EC%A3%BC%EC%9C%A8

ź��Ʈ �Լ�(tan x)�� ���� ���Լ��� ��ũź��Ʈ �Լ�(arctan x)�̴�.
���� ��� tan x = y ( -pi/2 < x < pi/2, x�� ����(radian) ���� )�� ���谡 ���� �� arctan(y) = x �� �ȴ�.
Maclaurin �޼��� ���� arctan ���� ������ ����(������ �����Ѵ�).

원주율 구하는 알고리즘 - wonjuyul guhaneun algolijeum
(��. 1)
�� �� x���� 0�� ������� �� �� �Ŀ� ���� �ſ� ���� �������� �� �� �ִ�.
�� �츮�� pi/4 = arctan(1) ���� �˰� �ִ�. ���� �Ʒ���
원주율 구하는 알고리즘 - wonjuyul guhaneun algolijeum
(��. 2)
���ε� pi�� ����� �� ������ �� �� �ִ�. ������ �� ���� ���ż��� �ſ� ����. �Ʒ��� ���� �� �İ��� �񱳵� �� �� ������ ������ �� �� �ִ�.
원주율 구하는 알고리즘 - wonjuyul guhaneun algolijeum
(��. 3)
arctan(1) = arctan(1/2) + arctan(1/3) ���� ���� ������ �� ������ ���⼱ �����Ѵ�. �ᱹ pi = 4 arctan(1) = 4 arctan(1/2) + 4 arctan(1/3) �� ���� ������ ���� �� ������, m arctan(1/n) �� ����ϴ� �Լ��� ������� ��, n�� ���� Ŭ �� ���� �����Ѵ�. ���ڰ� ���� ����ߴ� ���� ������ ����.
원주율 구하는 알고리즘 - wonjuyul guhaneun algolijeum
(��. 4)
�� �Ŀ� ���� ������ ���������� ���⼱ �����ϸ� �� ���� ������ ���̴� �ٸ� �ĵ� ���� ������ ���⼱ �����Ѵ�.

4. �˰����� ����

�����ڸ� ���� ǥ��

�ǹ� ���� - 100�ڸ��� ������ ��Ÿ������? 100�ڸ��� ������ �����̳� ������ ��� �ұ�? �Ҽ� 100�ڸ����� ��Ȯ�ϰ� ���� ��Ÿ������? ����� ������ �ذ��ϱ� ���ؼ��� �׳� integer, double ���� ���� �����δ� ��ȿ�ڸ����� �Ѱ踦 ������. �̸� �ذ��ϱ� ���ؼ� � ����� ������?

��� �Ұ�- 100�ڸ��� ���� ǥ���ϴ� ��츦 ���� �� ��, �迭(Ȥ�� ������ ��)�� ������ ���� ���� �ִ� ����� ������ ����. a(0) = 1(10�� 0����)�� �ڸ��� ��, a(1) = 10�� �ڸ��� ��, a(2) = 100�� �ڸ��� ��, ..., a(99) = 10�� 99������ �ڸ��� ��. �̿� ���� �ϸ� 100�ڸ��� ���� ���� �����̳� ������ ���� ����ϰ� ǥ���� �� �ִ�. ����� �� ������ �ϱ� ���ؼ��� �迭 a()�� �� ���ڸ� ��(Ȥ�� �� �̻� ����ϴ� ��������)�� �ִ� ����� ������ �� �ִ�. ���⼱ �⺻������ ���ڸ� ���� �ִ� ������ �����Ϸ� �Ѵ�. ���α׷��� �ÿ��� �ʿ信 ���� ����ϴ� �������� Ȯ���ų �� ������ ����.

���ѼҼ��� �����ڸ� ǥ��

��1) 1 / 2 = 0.5 = 0.50000 ... 0 (���ѼҼ�)
��2) 28 / 3 = 9.11111 ... = 9.11111 ... 1 (��ȯ���� �� �ڸ��� ���ѼҼ�)
��3) 1 / 97 = 0.01030 ... = 0.01030 ... ? (��ȯ���� 96 �ڸ��� ���ѼҼ�)

'��1'�� ���� ���ѼҼ��� ���� ���� �迭�� ������� �ʰ��� ������ ���� �� �ִ�. ������ ���� �ڸ����� �����ϴ� ���ѼҼ��� ��� ��ǻ�Ͱ� ����ϴ� ������ ����� ��Ȯ�ϰ� ��Ÿ�� �� ���� ���̴�. '��2'�� '��3'����ó�� ���ѼҼ��� ������ �迭�� �־� �� �ʿ並 ���� ���̴�. ���� ��ȯ���� �� ��� �迭�� �ִ� ���� ����� ������ �� ���� ���̴�.

��·�� ���ѼҼ��� �Ҽ� �� �ڸ����� ��Ÿ���ٴ� ���� �ᱹ�� �ٻ簪�� ��Ÿ���� ���� �Ǹ� �� �� �� �����ڸ��� �ݿø�, �ø�, ������ �� ���� �� �� ������ ������ �� �ִ�. �� ��, ������ �Ѱ踦 �� �� ������, �˷� ��� ��Ȯ���� �� �� �ִ�. ���� ��� �Ҽ� 100�ڸ����� ǥ���� ��� ������ �Ҽ�100�ڸ��� �� 1���� ���� ���̸�, �׷��� �� 10���� ������ ��� ������ 100�ڸ��� �� 1�� 10�躸�� ���� ���̴�.

������ ������ ����� ���� ���� �Լ��� ���� ������ �����κп��� ũ�� ������ ���� �ʴ´�. ���� � ���� �Ҽ� n�ڸ����� ��Ÿ���� �迭(a �迭�� ���� ����)�� ������ ���� ���� ǥ���ϱ�� ����.

��) 348.2378948789773492 �� �Ҽ� 10�ڸ����� a �迭�� �ִ´�.
a(0) = 348, a(1) = 2, a(2) = 3, ... , a(9) = 8, a(10) = 9.
�Ҽ� 11�ڸ����ʹ� ������ �Ѵ�.
�� �� ����(���⼭ �� ������ �� �ۿ��� ������ ������ ���밪�� ����.)�� 10^-10 (10�� -10 �ŵ�����. '^'�� �����ε� �ŵ������� �ǹ���.)���� �۴�.

� ���� �����κ��� a(0)�� �ְ�, �Ҽ� k��° ���� a(k)�� ������ � ����
a(0).a(1)a(2) ... a(k) ... a(n) �� ���� ���°� �ȴ�. a(0)�� ���� �ڸ����� �� �� ������(���� ������(���� ��� integer ���� 32767)�� �Ѿ�� �ʴ� ��쿡 ���Ͽ�), a(1)���� a(n)������ 0~9 ������ �� �ڸ��� ���� �ȴ�.

�����δ� �̷��� ǥ���Ǵ� ���� ���� ������ �ٷ� ���̸� �� a(0).a(1)a(2) ... a(k) ... a(n) �� �׳� a()��� ǥ���� ���̴�. �׷��ϱ� ���� �迭�� ��Ÿ���ٰ� �����ϸ� �ȴ�.

�����ڸ� �Ҽ��� ����, ����, ������

a�� b�� ������ �ϴ� ��츦 ������ ����. �� ���� ����� a�� b�� �����ų ���� �ְ�, �� �ٸ� �� c�� ������ ���� �ִ�. ���� ������� ���� �� ������ ȣ���ϴ� ����� ���� �ᱹ ���� ����� ���� �� �����Ƿ� ���⼭�� ���ǻ� a+b=c�� ������ �����Ѵ�(������ ���߿� ������ m arctan (1/n) �˰������ �������� ���� ���̴�).

���ϱ� �˰�����

  • �Է°� - a(), b() : ��� ����̴�.
  • ����� - c() : c() = a() + b() �� ��� ����̴�.
  • x()�� x(0).x(1)x(2)....x(n-1)x(n) ������ ���ѼҼ��� ��Ÿ�� �ٻ簪.
  • �ӽú��� - k : ������ ���� ���� ���ȴ�.
  1. c()�� 0���� �ʱ�ȭ��Ų��.
  2. c(n)�� a(n)�� b(n)�� ���� �ִ´�(�̰��� c(n)=a(n)+b(n)�� ǥ������).
  3. c(n)�� 9���� ũ�� c(n-1)=1, c(n)=c(n)-10�� ���Ѵ�.
  4. k = n-1 (k�� n-1�� �ִ´�.)
  5. c(k) = c(k) + a(k) + b(k)
  6. c(k)�� ���� 9���� ũ�� c(k-1)=1, c(k)=c(k)-10�� ���Ѵ�.
  7. k���� n-2, n-3, ..., 2, 1 �� ���� ���� 5���� 6���� �ݺ��Ѵ�.
  8. c(0) = c(0) + a(0) + b(0)
������ �����ϴ�. ���ڸ����� �� �ڸ��� ���� �����µ� ���� ���� 9�� ���� ���� ���ڸ��� 1�� �÷� �ְ� ���ڸ��� ���� ������ 10�� ���� ���̴�. �̷� ������ ���, ����� �� carry(�÷��� ���� ������ 1, ������ 0)�� ���� �ش�. c(0)�� �����κ��̹Ƿ� ���ڸ��� ���� �ƴ� ���� ������ c(1)���� c(n)������ ��� 0���� 9������ ���ڸ����̴�.
�̷��� �ϸ� a()�� b()�� ���� c()�� ����ȴ�. ���⼭ �����ؾ��� ���� c(0)�� ���� �Ѱ谪�� ���� �ʾƾ� �Ѵ�.
���� a()�� b()�� ���� �ٻ簪�̾��� ��� c()�� ������ �Ѱ�� 2*10^-n(10�� (-n) �ŵ������� �� ��)�̴�.

���� �˰�����

  • �Է°� - a(), b() : ��� ����̸� a�� b���� ������ �� �ȴ�.
  • ����� - c() : c() = a() - b() �� ��� ����̴�.
  • �ӽú��� - k : ������ ���� ���� ���ȴ�.
  1. c()�� 0���� �ʱ�ȭ��Ų��.
  2. c(n) = a(n) - b(n)
  3. c(n)�� 0���� ������ c(n-1)=-1, c(n)=c(n)+10 �� �Ѵ�.
  4. k = n-1
  5. c(k) = c(k) + a(k) - b(k)
  6. c(k)�� ���� 0���� ������ c(k-1)=-1, c(k)=c(k)+10�� �Ѵ�.
  7. k���� n-2, n-3, ..., 2, 1 �� ���� ���� 5���� 6���� �ݺ��Ѵ�.
  8. c(0) = c(0) + a(0) - b(0)
������ �����ϴ�. ���ڸ����� �� �ڸ��� �� �����µ� �� ���� ������ ���� ���ڸ��� 1 ���� �ְ� ���ڸ��� �� ������ 10�� ���Ѵ�. �̷� ������ ���, ����� �� carry(������ ���� ������ -1, ������ 0)�� ���� �ش�. c(0)�� �����κ��̹Ƿ� ���ڸ��� ���� �ƴ� ���� ������ c(1)���� c(n)������ ��� 0���� 9������ ���ڸ����̴�.
�̷��� �ϸ� a()���� b()�� �� ���� c()�� ����ȴ�. ������ �Ѱ�� 2*10^-n�̴�(������ �̺��� �� �۰� ���� ���� ������ ���ǻ� �̷��� ��´�).

������ �˰�����

  • �Է°� - a(), p : ��� ����̴�. p�� �迭�� �ƴ� ���� �ڿ����̴�.
  • ����� - c() : c() = a() / p �� ��� ����̴�.
  • �ӽú��� - tmp : ������ ��� ���� ���� ���ȴ�.
  • �ӽú��� - k : ������ ���� ���� ���ȴ�.
  1. c(0) = a(0)/p�� �����κ�
  2. tmp = a(0) - p * c(0) ; ������ = ������ - ���� * ��
  3. k=1
  4. tmp = 10 * tmp + a(k)
  5. c(k) = tmp/p�� �����κ�
  6. tmp = tmp - p * c(k)
  7. k = 2, 3, ..., n-2, n-1 �� ���ؼ��� 4��,5��,6���� �ݺ��Ѵ�.
  8. tmp = 10 * tmp + a(n)
  9. c(n) = tmp/p�� �����κ�
������ �����ϴ�. '������ = �� * ���� + ������'�� �ݺ��ϴµ�, ó���� �������� a(0)�� �Ǹ�, ������ �� �������� 10���� ���� a(1)�� ���� ��, �̷��� ��������� ������� ���ϴ� ���̴�. ���⼭ 1,5,9���� ���� �������� �����κ��� ���ϴ� ���� �����Լ��� ����� ���� �ְ�, ���ο� �Լ��� ����� ����� ���� �ִ�. �� 2,6�� ���� ������ ���ϴ� �Լ��� ����ص� �Ǹ� �̸� �̿��Ͽ� 1���� 2��, 5���� 6�� ���� ������ �ٲ� ���������� ���� �� �����κ��� ������ ���ϵ��� �� ���� �ִ�. ������ �Ѱ�� 10^-n���� ����. ������� ������ �������� �ص� ������ �Ѱ�� ������ 10^-n���� ���� �� �ִ�.
���⼭ �����ؾ� �� ���� �ִ�. ���� p�� ���� ��ȿ ������ 10���� 1���� Ŭ ��� p�� tmp�� ���� ���� ��� ���װ� ���� �� �ִ�. ���� ��� p�� integer ������ ���� ��, integer ���� ����Ѱ谡 32767�� ��, p ���� 3276���� Ŀ���� �� �ȴ�. tmp = 10 * tmp + a(k) �� �ϴ� �������� over flow�� �Ǿ� �߸��� ����� ���� �� �ֱ� �����̴�. �׷��� ������ ���� �� �ֱ� ������ �Լ�(���ν���)���� p�� �Ѱ谪�� �Ѿ ��� ����ó���� �ϱ⸦ ���Ѵ�.

m arctan(1/n) �˰�����

���� �� �˰�������� �̿��� m arctan(1/n) �� ����ϴ� ����� ������ ����. ���⼭ arctan �޼����� �ٽ� �� �� ���� ���� ������ ����.

원주율 구하는 알고리즘 - wonjuyul guhaneun algolijeum
(��. 5)
m�� n�� ���⼭ ���� �����̴�. �� ������ ����� �� ���� ���̴�. for ���� ���� �̿��� ����Ѵ�. ����� �����ϰ� �ϱ� ���ؼ� ������ ���� �� ������ ��(a, b, s �� �迭)�� �̿��� �� �ִ�. �׷�, �� ����� �Ұ��Ѵ�.

ó�� ����(i=1)

  • a() = m / n
  • b() = a()
  • s() = b()
�� ����(i=2)
  • a() = a() / (n*n)
  • b() = a() / 3
  • s() = s() - b()
����° ����(i=3)
  • a() = a() / (n*n)
  • b() = a() / 5
  • s() = s() + b()
... ( �� �� ) ...

k��° ����(i=k)

  • a() = a() / (n*n) : �ᱹ a() = m / n^(2k-1) �� ����.
  • b() = a() / (2k-1) : �ᱹ b() = m / {(2k-1) * n^(2k-1)} �� ����.
  • s() = s() - (-1)^k * b() : �ᱹ ���ϰ��� �ϴ� ���� s()��.
���� �� ����

�̷� ������ a, b, s�� ���� ����Ű�� �ᱹ m arctan 1/n �� ��� ����� s()�� ���� ���� �ȴ�. �� �� b()=0.00000...0 �� �Ǵ� ����, s() = m arctan 1/n �� �����Ѵ�. �� ��° �������� ������ �������� b�� ���� �����κ��� ���� �� �ִ�. �� �� ������ �� �� ���� ���� ������ �Ѱ踦 ������ �ڸ� 1�� ���� �� �ִ�. �׷��Ƿ� k��° �������� ������ ��� ������ �Ѱ�� {(k+1)/2 �� ������ * ������ �ڸ�}�� ���� �� ������, ������ '�ٻ簪 - ������ �Ѱ�' ~ '�ٻ簪 + ������ �Ѱ�'�� �ȴ�.
���� - ���� ���� i�� �Ѱ谪(���� ��� max_int)�� �Ѿ�� �ʵ��� �ؾ� �Ѵ�. �̰��� �Ҽ� ���° �ڸ����� ���� ������, �׷��� ���° �������� ������ ������ ���� �����ؼ� ó���ϵ��� �ؾ� �� ���̴�.

�̻����� �����ڸ��� �Ҽ������� ������ ����, �����ڸ��� �Ҽ��� �ڿ����� ������ ��, �̸� �̿��� m arctan 1/n �� ����ϴ� ���� �˾� ���Ҵ�. �� �̿� ���� ������ �Ѱ踦 �����ν� �������� ������ ��Ȯ�� ��ġ�ϴ��� �� �� �ִ�. �� ���� ���� m arctan 1/n �� ���� ������ ������ �� �� ������ �̿� ���� ������ �Ѱ�� ������ �������ν� ���� �� �ִ�. ���� ���� pi�� ���ϴ� �ĵ鿡 ���� �˾� ����.

5. ������ ��� ��

������� ������ ������ ���� �Ʒ��� �Ұ��Ǵ� ������ pi�� ����� �� �������� �����ȴ�(���� ���α׷��� ������ �ִ� ���̶��). �Ʒ��� �ĵ鿡 ���� ������ ���� �� ���� �ٶ���.

pi/4 = arctan(1) ����,
pi = 4 arctan(1/1)

�� ���� ���ż��� �ſ� ����. ���ϰ� ���� ���� ���̴�. �Ҽ� �ټ� �ڸ����� ����ϴ� ���� ��û�� ������ ������ �� ���̴�. �����δ� pi/4 �� ���� �ĸ� �Ұ��Ѵ�. pi ���� �� ���� �纯�� 4���Ͽ� ������ �� �ִ�.

pi/4 = arctan(1/2) + arctan(1/3)

���� �ӵ��� ó�� �İ��� ���� �� ���� ������ ���Ǿ���. ������ �� ���� ���� �䱸�ȴ�.

pi/4 = 2 arctan(1/3) + arctan(1/7)

pi/4 = 4 arctan(1/5) - arctan(1/239)

pi/4 = 8 arctan(1/10) - arctan(1/239) - 4 arctan(1/515)

�̻����� �� ���� ���� �Ұ��ߴ�. �̷��� ���� �󸶵��� ���� �� �ִ�. �����е� �ٸ� ���� ���� ���� �� ���� �����ϵ��� ����� �� ��ſ��� ���� ���̴�. �̻����� ª�� ��(?)�� ��ĥ�� �Ѵ�.

6. ���α׷���

�ϴ�, �Ʒ� ��ũ�� ���� �ٶ���. Ǯ�̴� ���߿� �ð��� �Ǹ�...

������ ��� java �ҽ� : http://mathman.kr/bbs/read.php?category=6&num=1
������ �Ҽ� 1���ڸ����� ����� ��� : http://mathman.kr/bbs/read.php?category=6&page=1&num=4


���� �ۼ��� : 1998.3.