부동 소수점 숫자를 정확하게 문자열로 변환하는 방법: Burger-Dybvig 알고리즘
IEEE 754 부동 소수점 숫자를 텍스트로 변환 시, 서로 다른 시스템 간의 데이터 불일치 문제 발생
RFC 8785는 바이트 단위의 결정적(Byte-Deterministic) JSON 출력을 요구하며, 가장 어려운 부분은 숫자 형식 지정임
저자는 ECMA-262 표준을 준수하는 Burger-Dybvig 알고리즘을 Go 언어로 구현, 286,362개의 테스트 벡터로 검증
정확한 경계 계산을 위해 다중 정밀도 산술(Multiprecision Arithmetic)을 사용하고, 짝수 자릿수 묶기(Even-Digit Tie-Breaking)를 통해 정확성 확보
IEEE 754 부동 소수점 구조 및 문제점
IEEE 754 표준은 부동 소수점 숫자를 표현하기 위한 64비트 구조를 정의하며, 부호(Sign), 지수(Exponent), 가수(Mantissa)로 구성된다. 이 구조는 0.1 + 0.2 != 0.3과 같은 정밀도 문제(Precision Issues)를 야기하며, 서로 다른 시스템 간의 숫자 표현 불일치를 초래한다. 이러한 문제는 데이터 무결성(Data Integrity)을 해치고, 재현 가능한 빌드(Reproducible Builds)를 어렵게 만든다.
Burger-Dybvig 알고리즘의 핵심 원리
Burger-Dybvig 알고리즘은 주어진 부동 소수점 숫자 `f`에 대해 `parse(d) == f`를 만족하는 가장 짧은 십진수 문자열 `d`를 찾는 것을 목표로 한다. 이를 위해 정확한 경계 계산(Exact Boundary Calculation)이 필수적이며, 알고리즘은 다중 정밀도 정수(Big Integer)를 사용하여 값을 표현한다. 특히, 짝수 자릿수 묶기(Even-Digit Tie-Breaking)는 두 표현이 동일하게 짧을 때 일관성을 보장하는 핵심 메커니즘이다.
ECMA-262 표준 준수 및 구현 세부 사항
저자는 ECMA-262 표준을 준수하기 위해 Burger-Dybvig 알고리즘을 Go 언어로 구현했다. 구현 과정에서 지수 추정(Exponent Estimation), 10의 거듭제곱 스케일링(Power-of-10 Scaling), 그리고 자릿수 추출(Digit Extraction)과 같은 여러 단계를 거친다. 특히, FormatFloat 함수가 아닌, ECMA-262의 특정 요구 사항을 충족하는 자체 구현을 통해 표준 준수(Standard Compliance)를 달성했다.
테스트 및 검증 전략
구현의 정확성을 검증하기 위해 저자는 다양한 테스트 전략을 사용했다. 여기에는 286,362개의 테스트 벡터를 사용한 오라클 테스트(Oracle Testing), 라운드 트립 테스트(Round-Trip Testing), 그리고 퍼즈 테스트(Fuzz Testing)가 포함된다. 이러한 테스트는 알고리즘의 의미론적 정확성(Semantic Correctness), 기수성(Cardinality), 그리고 무결성(Integrity)을 보장하며, 특히 SHA-256 해시(SHA-256 Hash)를 사용하여 테스트 데이터의 변조를 방지한다.
재현 가능한 데이터 처리를 위한 중요성
RFC 8785는 바이트 단위의 결정적 출력(Byte-Deterministic Output)을 요구하며, 이는 콘텐츠 주소 지정 스토리지(Content-Addressed Storage), 암호화 서명(Cryptographic Signatures), 그리고 캐시 키 생성(Cache Key Generation)과 같은 분야에서 매우 중요하다. 만약 숫자 표현이 일관되지 않으면, 동일한 값을 가진 데이터라도 서로 다른 바이트 시퀀스를 생성하여 시스템 간의 데이터 불일치(Data Divergence)를 야기할 수 있다. 따라서, 정확한 숫자 형식 지정은 데이터 신뢰성(Data Reliability)을 확보하는 데 필수적이다.
