부동소수점이 기하학적 결정론에서 실패하는 이유: 정수 연산의 사례

컴퓨팅 기하학 세계에서는 단 한 비트의 차이가 성공적인 연산과 치명적인 실패 사이를 가를 수 있습니다. 많은 개발자들은 동일한 코드와 동일한 입력이 실행되는 머신에 관계없이 동일한 결과를 산출한다는 가정을 합니다. 그러나 exact-poly의 제작자가 발견했듯이, 부동소수점 숫자가 관여될 때는 이것이 항상 참이 아닙니다.

다각형 겹침 테스트를 디버깅하던 중, 저자는 정점이 볼록인지 오목인지를 판단하는 함수가 로컬에서는 정상 작동했지만 서버에서는 실패한다는 것을 발견했습니다. 문제는 논리 버그가 아니라 서로 다른 아키텍처가 부동소수점 연산을 처리하는 방식이었습니다. x86에서는 컴파일러가 라운딩 단계를 줄이기 위해 Fused Multiply-Add (FMA)를 사용했지만, WASM에서는 사용하지 않았습니다. 이 작은 라운딩 차이 때문에 거의 0에 가까운 정점의 부호가 바뀌었고, 이는 도미노 효과를 일으켜 다각형 분해 전체를 완전히 바꾸어 놓았습니다.

IEEE 754 재현성에 대한 착각

많은 개발자들은 IEEE 754 호환성이 일관된 동작을 보장한다고 믿습니다. 실제로 이 표준은 주로 부동소수점이 어떻게 저장되는지를 정의할 뿐이며, 다양한 실행 환경에서 어떻게 동작하는지는 정의하지 않습니다. 재현성을 흐릴 수 있는 여러 메커니즘이 존재합니다:

Intermediate Registers: x87 FPU는 종종 값을 80비트 정밀도로 유지하고 메모리로 spill할 때만 라운딩하지만, ARM이나 WASM은 그렇지 않을 수 있습니다.
Fused Multiply-Add (FMA): fma(a, b, c)는 곱셈과 덧셈을 단일 라운딩 단계로 수행하여 별도로 연산할 때보다 더 정확하지만 다른 결과를 만들어냅니다.
Reassociation: -ffast-math와 같은 플래그를 사용하는 컴파일러는 (a + b) + c를 a + (b + c)로 재작성할 수 있으며, 이는 라운딩 순서를 바꿉니다.
Denormals: "flush-to-zero" 플래그가 프로세스마다 조용히 전환될 수 있어 서브노멀 숫자의 처리 방식을 바꿀 수 있습니다.

한 댓글 작성자가 지적했듯이, JVM(strictfp 또는 StrictMath를 통해)과 같은 일부 환경은 엄격한 재현성을 보장하려고 시도하지만, 부동소수점 연산의 근본적인 특성은 여전히 근사치에 불과합니다. 락스텝 게임 시뮬레이션이나 ZK 증인 생성과 같이 절대적인 결정론이 요구되는 애플리케이션에서는 이러한 근사치가 충분하지 않습니다.

볼록 분해에서의 "한 비트" 문제

기하학에서 cross_sign(A, B, C) 함수는 의사결정의 주요 신호입니다. 이는 회전이 왼쪽, 오른쪽, 혹은 공선인지 판단합니다. 세 점이 거의 공선에 가까울 때, 한 머신은 +1e-12를 반환하고 다른 머신은 -2e-13을 반환할 수 있습니다.

이 부호 전환은 볼록 분해가 이산적인 과정이기 때문에 중요합니다. 정점은 오목이거나 그렇지 않거나 둘 중 하나입니다. 부호가 바뀌면 다른 정점이 오목으로 식별되어 시작 절단이 달라지고 완전히 다른 분해 그래프가 생성됩니다. epsilon(예: "비교하기 전에 마이크로미터 단위로 반올림")을 사용하는 것은 해결책이 되지 못합니다. 어떤 epsilon 영역도 결국 실제 다각형을 포함하게 되어 동작이 갈라지게 됩니다.

해결책: 정확한 정수 연산

x86, ARM, WASM 전역에서 비트 단위로 동일한 결과를 얻기 위해 exact-poly는 부동소수점을 완전히 포기하고 정수를 사용합니다. 좌표를 고정 스케일(예: 지리학에서는 1 단위 = 1 마이크로미터)로 매핑함으로써, 라이브러리는 교차곱의 부호가 근사가 아니라 비트 논리에 의해 결정되도록 보장합니다.

정수 예산 관리

정수 연산은 스케일을 신중히 선택해야 합니다. i64::MAX(대략 $9.2 \times 10^{18}$)를 사용할 때, 개발자는 측정 단위와 최대 좌표 크기 사이의 균형을 맞춰야 합니다. 지리학에서는 $10^6$ 스케일이 마이크로미터 정밀도를 제공하면서도 행성 전체 둘레를 충분히 커버합니다.

`i128`로 오버플로 방지

교차곱 공식—$(bx - ax)(cy - ay) - (by - ay)(cx - ax)$—은 i64 한계를 쉽게 초과할 수 있습니다. 이를 방지하기 위해 exact-poly는 엄격한 규칙을 적용합니다: 좌표는 i64로 저장하지만 모든 곱셈은 i128로 수행합니다.

핵심은 라이브러리가 뺄셈 전에 값을 확장한다는 점입니다: (bx as i128) - (ax as i128). 먼저 i64에서 뺄셈을 하면 오버플로가 발생해 i128 컨테이너에 저장하더라도 쓰레기 데이터가 될 수 있습니다.

견고한 분해 캐스케이드 구현

단일 볼록 분해 알고리즘이 모든 입력에 완벽하지 않기 때문에 exact-poly는 알고리즘의 "캐스케이드"를 사용합니다. 첫 번째가 실패하면 다음 알고리즘이 이어서 실행됩니다:

ExactPartition: 오목 정점을 우선시하는 탐욕적 파티셔너.
Bayazit: 스테이너 점(중간 정점)을 삽입할 수 있는 재귀적 접근법.
EarClip + Hertel-Mehlhorn: 삼각분할 후 병합 단계로 파트 수를 줄이는 방법.

세 알고리즘 모두 실패하면 라이브러리는 링을 회전시켜(시작 정점을 바꾸어) 다시 시도합니다. 이 휴리스틱은 병리적 경우가 종종 특정 정점 순회 순서와 연결되어 있기 때문에 효과적입니다.

이산 수학의 경계 사례 처리

정수로 전환하면 연속 부동소수점 수학에서는 존재하지 않던 새로운 도전 과제가 생깁니다:

Midpoint Precision: 단순 정수 나눗셈 (a + b) / 2는 낮은 비트를 버립니다. 라이브러리는 round_div2를 사용해 점이 떠다니는 것을 방지합니다.
Steiner Point Snapping: 중간점이 기존 정점에 너무 가깝게 위치하면 우연한 공선을 방지하기 위해 살짝 이동시켜야 합니다.
Bookkeeping: 합성 정점은 최종 출력 정점 수가 입력과 일치하도록 태그를 달아야 하며, 이는 이후 검증 실패를 방지합니다.

결론: 정밀도보다 일치성

부동소수점 숫자는 정밀도를 위해 설계되었지만, 정수 연산은 일치성을 위해 설계되었습니다. 두 개의 서로 다른 프로세스가 정확히 동일한 답을 도출해야 할 때, 라운딩 방향이 다르면 부동소수점의 정밀도는 무의미합니다. 중간 계산에 i128을 활용하고 부동소수점을 완전히 배제함으로써 exact-poly는 64비트 정수를 지원하는 모든 아키텍처에서 동일함이 보장된 기하학 연산을 위한 결정론적 기반을 제공합니다.