BLUEnLIVE

구라제거기의 고향입니다

 
 

“원주율(\(\pi\))을 부동소수점 없이 정수만으로 어디까지 정밀하게 표현할 수 있을까?”라는 고민을 해보게 되었다.
데스크톱 환경에서는 double이 워낙 잘 되어 있어 큰 의미가 없을지 모른다.
하지만, MCU1나 FPGA, 정수 SIMD 연산을 극한으로 최적화해야 하는 환경 등에선 이야기가 달라진다.

\(\pi\)를 정수 범위에서 다루는 접근방식 두 가지를 고민해봤다.

1. 왜 정수 원주율인가?

FPU2가 없는 저사양 MCU, 전력을 극단적으로 아껴야 하는 임베디드 환경에서 실수 연산은 사치이다.
엄밀함을 양보하고 속도를 잡아야 할 때, \(\pi\)를 정수의 영역으로 끌어와야 한다.

2. 접근 #1: 최적의 정수비(\(n/d\)) 찾기

\(\pi\)를 \(n/d\) 형태의 분수로 표현하는 방식이다.
단순히 자릿수가 큰 수를 쓰는 게 아니라, “분모의 크기 대비 가장 오차가 적은” 효율적인 비를 찾는 것이 핵심.

사실 이 범위에서는 이미 종착역에 해당하는 답이 잘 알려져 있다.

  • 32비트 환경의 종착역: \(355 / 113\)
    • 중국 수학자 조충지가 발견한 이 비율은 놀랍다. 분모가 겨우 113인데 소수점 6자리(\(3.141592...\))까지 정확하다.
    • 효용성: \(x \times 355 / 113\) 연산 시, \(x\)가 약 \(1.2 \times 10^7\) 이하일 때 32비트 오버플로 없이 연산이 가능하다.
  • 64비트 환경: \(104348 / 33215\) 또는 더 나아가 \(3126535 / 995207\)
    • 소수점 9~12자리까지 확보할 수 있다. 64비트 레지스터를 쓰면 훨씬 정밀한 제어가 가능하다.

알려진 값들을 뒤로 하고, 직접 한번 뽑아보기로 했다.

min_diff = 1;
for i in range(1, 10000000000):
    p_i = np.pi * i

    p0 = int(np.floor(p_i))
    p1 = int(np.ceil(p_i))

    p0_ = p0 / i
    p1_ = p1 / i

    diff0 = np.abs(p0_ - np.pi)
    diff1 = np.abs(p1_ - np.pi)

    if diff0 < diff1:
        if diff0 < min_diff:
            accuracy_up_by = (min_diff - diff0) / min_diff

            min_diff = diff0
            print(f"{p0} [~=2^{int(np.ceil(np.log(p0) / np.log(2)))}] / {i} = {p0_}, diff = {diff0}")
    else:
        if diff1 < min_diff:
            accuracy_up_by = (min_diff - diff1) / min_diff

            min_diff = diff1
            print(f"{p1} [~=2^{int(np.ceil(np.log(p1) / np.log(2)))}] / {i} = {p1_}, diff = {diff1}")

    if accuracy_up_by == 1.0:
        break

이렇게 뽑은 결과는 다음과 같다.

3 [~=2^2] / 1 = 3.0, diff = 0.14159265358979312
13 [~=2^4] / 4 = 3.25, diff = 0.10840734641020688
16 [~=2^4] / 5 = 3.2, diff = 0.05840734641020706
19 [~=2^5] / 6 = 3.1666666666666665, diff = 0.025074013076873403
22 [~=2^5] / 7 = 3.142857142857143, diff = 0.0012644892673496777
179 [~=2^8] / 57 = 3.1403508771929824, diff = 0.0012417763968106676
201 [~=2^8] / 64 = 3.140625, diff = 0.000967653589793116
223 [~=2^8] / 71 = 3.140845070422535, diff = 0.0007475831672580924
245 [~=2^8] / 78 = 3.141025641025641, diff = 0.0005670125641521473
267 [~=2^9] / 85 = 3.1411764705882352, diff = 0.00041618300155787935
289 [~=2^9] / 92 = 3.141304347826087, diff = 0.0002883057637061981
311 [~=2^9] / 99 = 3.1414141414141414, diff = 0.00017851217565167943
333 [~=2^9] / 106 = 3.141509433962264, diff = 8.32196275291075e-05
355 [~=2^9] / 113 = 3.1415929203539825, diff = 2.667641894049666e-07
(중략)
64588 [~=2^16] / 20559 = 3.141592489907097, diff = 1.6368269628586063e-07
64943 [~=2^16] / 20672 = 3.1415924922600618, diff = 1.613297313518558e-07
65298 [~=2^16] / 20785 = 3.1415924945874427, diff = 1.5900235039723043e-07
(중략)
103283 [~=2^17] / 32876 = 3.1415926511741086, diff = 2.415684541290375e-09
103638 [~=2^17] / 32989 = 3.1415926520961532, diff = 1.493639878447084e-09
103993 [~=2^17] / 33102 = 3.1415926530119025, diff = 5.778906242426274e-10
104348 [~=2^17] / 33215 = 3.141592653921421, diff = 3.3162805834763276e-10
208341 [~=2^18] / 66317 = 3.1415926534674368, diff = 1.2235634727630895e-10
312689 [~=2^19] / 99532 = 3.1415926536189365, diff = 2.914335439641036e-11
833719 [~=2^20] / 265381 = 3.141592653581078, diff = 8.715250743307479e-12
1146408 [~=2^21] / 364913 = 3.141592653591404, diff = 1.6107115641261771e-12
3126535 [~=2^22] / 995207 = 3.1415926535886505, diff = 1.1426415369442111e-12
4272943 [~=2^23] / 1360120 = 3.141592653589389, diff = 4.04121180963557e-13
5419351 [~=2^23] / 1725033 = 3.1415926535898153, diff = 2.220446049250313e-14
42208400 [~=2^26] / 13435351 = 3.1415926535897722, diff = 2.0872192862952943e-14
47627751 [~=2^26] / 15160384 = 3.141592653589777, diff = 1.5987211554602254e-14
53047102 [~=2^26] / 16885417 = 3.141592653589781, diff = 1.199040866595169e-14
58466453 [~=2^26] / 18610450 = 3.1415926535897842, diff = 8.881784197001252e-15
63885804 [~=2^26] / 20335483 = 3.141592653589787, diff = 6.217248937900877e-15
69305155 [~=2^27] / 22060516 = 3.141592653589789, diff = 3.9968028886505635e-15
74724506 [~=2^27] / 23785549 = 3.141592653589791, diff = 2.220446049250313e-15
80143857 [~=2^27] / 25510582 = 3.1415926535897927, diff = 4.440892098500626e-16
245850922 [~=2^28] / 78256779 = 3.141592653589793, diff = 0.0

동작 환경을 감안하면 역시 \(355 / 113\)가 종착역이라 봐도 무방할 수준이다.

3. 접근 #2: \(2^n\) 스케일링

정수비 방식의 치명적인 단점은 나눗셈이 포함된다는 것이다.
애초에 컴퓨팅 파워가 빵빵한 PC가 아닌, MCU나 임베디드 환경에서 나눗셈은 곱셈보다 수십 배 느린 연산이다.
이를 해결하기 위해 분모를 \(2^n\)으로 고정하는 방식을 생각해볼 수 있다.

  • 원리: \(\text{Scaled_Pi} = \text{round}(\pi \times 2^n)\)
  • 장점: 나눗셈 대신 비트 시프트(Shift)를 사용한다. 현대 CPU와 MCU에서 가장 빠른 연산.
비트수 (\(n\)) 근사치 (\(\pi \times 2^n\)) 정확도 비고
16-bit 205887 소수점 4자리 32비트 연산 환경에 적합
32-bit 13493037704 소수점 9자리 64비트 연산/SIMD 최적화에 탁월

역시 익히 알려진 값들을 뒤로 하고, 직접 한번 뽑아본다.

min_diff = 1;
max_range = int(np.ceil(np.log(10000000000) / np.log(2)))

for i in range(1, max_range):
    p_i = np.pi * (2 ** i)

    p0 = int(np.floor(p_i))
    p1 = int(np.ceil(p_i))

    p0_ = p0 / (2 ** i)
    p1_ = p1 / (2 ** i)

    diff0 = np.abs(p0_ - np.pi)
    diff1 = np.abs(p1_ - np.pi)

    if diff0 < diff1:
        if diff0 < min_diff:
            min_diff = diff0
            print(f"{p0} / {2 ** i} [=2^{i}] = {p0_}, diff = {diff0}")
    else:
        if diff1 < min_diff:
            min_diff = diff1
            print(f"{p1} / {2 ** i} [=2^{i}] = {p1_}, diff = {diff1}")

결과는 다음과 같다.

6 / 2 [=2^1] = 3.0, diff = 0.14159265358979312
13 / 4 [=2^2] = 3.25, diff = 0.10840734641020688
25 / 8 [=2^3] = 3.125, diff = 0.016592653589793116
101 / 32 [=2^5] = 3.15625, diff = 0.014657346410206884
201 / 64 [=2^6] = 3.140625, diff = 0.000967653589793116
3217 / 1024 [=2^10] = 3.1416015625, diff = 8.908910206884002e-06
205887 / 65536 [=2^16] = 3.1415863037109375, diff = 6.349878855615998e-06
411775 / 131072 [=2^17] = 3.1415939331054688, diff = 1.279515675634002e-06
1647099 / 524288 [=2^19] = 3.141592025756836, diff = 6.27832957178498e-07
3294199 / 1048576 [=2^20] = 3.1415929794311523, diff = 3.2584135922775204e-07
6588397 / 2097152 [=2^21] = 3.141592502593994, diff = 1.5099579897537296e-07
13176795 / 4194304 [=2^22] = 3.1415927410125732, diff = 8.742278012618954e-08
26353589 / 8388608 [=2^23] = 3.1415926218032837, diff = 3.1786509424591713e-08
52707179 / 16777216 [=2^24] = 3.1415926814079285, diff = 2.781813535079891e-08
105414357 / 33554432 [=2^25] = 3.141592651605606, diff = 1.984187036896401e-09
843314857 / 268435456 [=2^28] = 3.1415926553308964, diff = 1.741103261565513e-09
1686629713 / 536870912 [=2^29] = 3.1415926534682512, diff = 1.2154188766544394e-10
13493037705 / 4294967296 [=2^32] = 3.141592653701082, diff = 1.1128875598842569e-10
26986075409 / 8589934592 [=2^33] = 3.1415926535846666, diff = 5.126565838509123e-12

floating point의 저장 원리를 생각해보면 이 방식은 정수 뿐만 아니라 실수 연산에서도 활용할 여지가 있다.
지수부(Exponent) 비트에서 자릿수를 빼는 트릭을 쓸 수 있다.

결론: 자릿수의 욕심을 버릴 때 보이는 효율

물론 원주율을 무한히 정밀하게 뽑는 것은 수학적인 즐거움이 크다.
하지만, 공학적으로는 시스템의 레지스터 크기(32/64bit)와 중간 연산의 안정성 사이에서 타협점을 찾아야 한다.

  • 가장 간결한 비율을 원한다면 \(355/113\).
  • 가장 빠른 속도를 원한다면 \(2^n\) 스케일링.

덧1. NASA의 제트추진연구소(JPL)는 공식적으로 3.141592653589793(\(\pi\)의 소수점 15자리)를 사용한다고 얘기했었다.
덧2. 우주 전체를 수소 원자 단위의 오차로 계산하는 데도 \(\pi\)는 40자리면 충분하다고 한다.

  1. MCU: Micro Controller Unit ↩

  2. FPU: Floating Point Unit, 부동소수점 연산 장치 ↩

카테고리:

업데이트:

참고

구라제거기(키보드 보안 프로그램 삭제) 7.56 업데이트

PC 뱅킹의 주적은 PC 뱅킹 프로그램이다. PC 뱅킹을 하고 나면 컴퓨터가 미친 듯이 느려지기 때문이다.키보드 보안 프로그램을 필두로 컴퓨터를 느려지게 만드는 악의 무리들이 너무나 많다.전통의 명가(?) nProte∗∗ 부터 컴퓨터 발목잡기의 거목 안∗ 온라인 시큐∗∗, 그 외에...

Notepad4 26.03 r6100 한국어화 공개

오류를 수정하고 다양한 성능 개선이 반영된 버전을 공개한다. 개요 아래 링크에서 다운받을 수 있으며, 언제나 그렇듯 x86/x64/AVX2/AVX-512/ARM64 버전이 함께 들어있다. Download Notepad4-r6100.zi...

구라제거기, 세계 최고 권위 보안 논문(USENIX Security)에 등장

아주 기분 좋은 소식을 접했다. 최근 보안 업계의 이슈를 다룬 유튜브 영상을 하나 보게 되었다.영상에서 우리나라 금융 보안 프로그램들이 오히려 시스템 보안에 어떤 위협이 되는지를 심도 있게 다룬 보안 연구 논문을 소개하는 내용이 나왔다. 영상을 보다 보니, 문득 논문의 원문 내용이...

배포 프로그램 라이선스 체계 정비 및 업데이트

그동안 본 블로그를 통해 다양한 프로그램들을 배포해 왔다.도구의 기능뿐만 아니라 제품으로서의 완성도도 중요하다는 생각이 들어 대대적인 내부 정비 작업을 진행했다. 오픈소스 라이선스 고지를 명확히 하고, 배포 패키지 구성을 전면 수정했다. 1. 배포 정책 및 라이브러리 변경 사항이번...