어째 이런 이상한 내용의 글들을 보고 있으면 교육적 지도(?)를 해주고 싶어서 계속 쓰게 되는군요..

상식적으로 알고가면 좋은 내용들을 쓰고 갑니다. 최근 퍼렁동네에 물이 얼마나 나빠졌는지 알 수 있습니다.

1. 슈퍼파이에 쓰인 연산식은 수많은 AGM 식들 중에 한 종류입니다. 저 내용은 잘못됐습니다.

먼저 AGM이라는 것에 대해서 설명하자면 Arithmetic-Geometric Mean이라 하여 한국어로 굳이 번역한다면 산술-기하 평균입니다.

근데 왜 -를 붙였을까요. 이건 필히 뭔 이유가 있어서 그렇습니다.

산술평균과 기하평균에 대해서 특정값을 선택해 무한히 반복을 하면 어떠한 값으로 수렴하는 현상을

먼치킨 수학자인 가우스가 발견하였고, 이것을 AGM이라는 이름으로 부릅니다. 실제 평균의 의미에선 벗어난 개념입니다.

자세한 링크는 여기에..

http://en.wikipedia.org/wiki/Arithmetic%E2%80%93geometric_mean

슈퍼파이에 쓰인 연산식은 정확히 말하자면 Brent-Salamin의 알고리즘으로, 가우스와 르장드르의 수학적 발견을 활용했기 때문에 Gauss-Legendre 알고리즘이라 불리기도 합니다. 이 식은 타원적분과 르장드르의 항등식을 가지고 Brent와 Salamin 두 수학자가 거의 비슷한 시기에 유도해낸 원주율 계산 방법 중 하나입니다.

http://en.wikipedia.org/wiki/Gauss%E2%80%93Legendre_algorithm

좀 더 자세한 정보는 3년전에 제가 쓴 글이 있으므로 그것으로 대체합니다.

http://gigglehd.com/zbxe/3479698

그리고 Brent-Salamin 알고리즘의 경우엔, 멀티쓰레드로 만들기가 쉽지 않습니다. 공식 자체는 flow-dependency를 갖고 있어서 제가 얼핏 보기엔 연산쓰레드를 2개까진 쉽게 나눠볼 수 있을 듯 한데.. 그 이후는 잘 모르겠네요.. 외국쪽에서도 제대로 멀티쓰레드 버전으로 만들어낸 사례를 본적이 없고.. 어차피 제일 좋은 공식도 아니라서 요즘은 잘 안쓰긴 합니다. 요즘은 주로 Chudnovsky 알고리즘을 씁니다.

2. FFT는 어디에 쓰나요.

FFT라는 것은 Fast Fourier Transform, 흔히 고속 푸리에 변환이라고 부르는 겁니다. 근데 이 변환은 주로 신호해석쪽에서 많이 쓰기 때문에 왜 갑자기 뜬금없이 나왔냐고 의문을 가질 수 있습니다. FFT는 의외로, 곱셈 연산을 할 때 아주 강력한 힘을 발휘하기도 합니다.

흔히 얘기하는 알고리즘 점근 표기법으로 basecase 방식(학교에서 배우는)의 곱셈은 곱셈 횟수로 따질 때에 O(n^2)의 시간 복잡도를 가지는 반면, FFT를 이용한 곱셈의 경우엔 O(n*logn*log(logn))의 복잡도를 가지기에, 비교적 작은 자리수에서는 basecase 곱셈이나 Toom-Cook같은 기존의 곱셈을 divide-and-conquer 방식으로 처리하는 알고리즘을 사용하고, 큰 자릿수에 경우엔 FFT로 대체할 경우 성능이 매우 좋아집니다.

뭐 이렇게 곱셈을 머리 아프게 하냐고 물으신다면, 곱셈은 컴퓨터의 instruction 속도에서 비교해볼때 덧셈에 비해서 15배~수십배 이상은 느립니다. 그렇기에 곱셈 연산횟수를 최소한으로 줄여야 성능이 좋아지겠죠..

3. 그렇다면 모바일 칩들이 PC 성능에 근접한것일까?

슈퍼파이에서 x86의 성능이 떨어지는 것 처럼 보이는건 그 이유가 매우 단순합니다. 프로그램이 너무 오래됐기 때문에 순수 FPU 명령과 범용 명령으로만 프로그램이 구성되어 있습니다. 만약 같은 알고리즘이라 한들 SSE나 AVX같은 기술을 적극 활용한다면 상황은 완전히 달라집니다. FFT는 SIMD 명령으로 득을 꽤 볼 수 있는 알고리즘이기 때문입니다. 당연히 최근에 나온 안드로이드용 파이의 경우 성능을 최대한 끌어올리기 위해 NEON같은 SIMD 명령을 안썼을리가 없죠.

저런 글에 혹해서 마치 요즘 나온 SoC들이 꽤 좋은 x86 프로세서들 성능에 근접하는 것 아닌가 하는 오해는 갖지 않으시기 바랍니다.. 아직 SoC의 실 성능은 아톰급 밖에 안됩니다... 비유를 하자면, 프리저는 풀파워를 써서 덤비는 반면에 손오공은 아직 초사이어인 변신도 안한 상황으로 생각하셔도 좋습니다. 그런데도 손오공이 이기는 원작 뺨치는 상황. 믿기지 않으신다면 제가 프로그램을 짜서 증명 해야겠지요..

만약 진짜 최신 기술들을 활용해서 파이를 계산하는 프로그램을 찾으신다면 y-cruncher를 추천합니다. Alexander J. Yee라는 대학원생이 만든 원주율 계산 프로그램으로 64비트 및 병렬처리, SSE, AVX등 최신 기술을 적절히 활용하는 매우 므시므시한 프로그램입니다. 실제 일본에서 원주율 세계 신기록을 갈아치울 때 이 프로그램을 이용한 것으로 알려져 있습니다.

http://www.numberworld.org/y-cruncher/#Download