Reddit

The fastest double-to-string algorithm you’ve never heard of

Żmij, 변환 핵심을 Schubfach에서 yy로 교체

Żmij 개발자 Victor Zverovich는 변환 핵심을 yy 알고리즘으로 바꾸고, 한 번의 곱셈으로 가장 짧은 왕복 가능 십진수를 찾는 원리를 설명했습니다. E4M3 값 192에서는 표 값 절삭에 따른 1 LSB 보정으로 `2e2`를 출력합니다. 연결된 M5 Max 벤치마크에서는 yy보다 Żmij의 측정 시간이 짧았습니다.

본문

Żmij 개발자 Victor Zverovich는 2026년 8월 10일 게시물에서 Żmij의 변환 핵심을 yyjson의 yy_double.c에 구현된 yy 알고리즘으로 바꿨다고 설명했습니다. 글은 yy가 이진 부동소수점 값을 다시 읽어도 원래 값이 복원되는 가장 짧은 십진수로 바꾸는 원리와 경계 사례를 소개합니다.

부동소수점 수를 십진 문자열로 바꾸는 dtoa 알고리즘은 원래 값으로 되돌아오는 표현을 찾습니다. yy는 입력값을 사전 계산한 10의 거듭제곱 값으로 십진 스케일에 맞춘 뒤, 같은 표 값을 비트 이동해 반 ULP 폭을 구합니다. 이 방식은 고정 폭 정수 연산을 쓰며 표 값과 곱하는 횟수를 한 번으로 줄입니다. 글에서 비교한 classic Schubfach는 이 과정에서 두세 번 곱합니다.

스케일을 맞춘 값 주변에서 yy는 정수 후보 두 개와 10의 배수 후보 두 개를 만듭니다. 10의 배수 후보는 끝의 0을 십진 지수로 옮겨 한 자리 짧게 쓸 수 있습니다. yy는 세 가지 비교로 이 짧은 후보가 입력값의 반올림 구간에 드는지 먼저 검사하고, 조건에 맞지 않으면 정수 후보를 씁니다. 정확히 중간에 놓이는 경우에는 가수의 하위 비트를 살펴 짝수 쪽으로 반올림합니다.

게시물은 8비트 E4M3 형식의 값 192로 경계 처리를 보여줍니다. 짧은 후보 200은 192와 다음 표현값 208 사이의 중간점에 놓입니다. 192의 가수가 짝수이므로 200을 다시 읽으면 192로 돌아옵니다. 따라서 yy는 긴 표현 19e1 대신 짧은 2e2를 출력합니다.

이 사례에서는 표에 저장한 10의 거듭제곱 값이 잘리면서 Q4.4 고정소수점 계산의 경계가 10보다 1 LSB 낮은 9.9375로 나타납니다. yy는 같은 오차를 보정하도록 비교 임계값도 1 LSB 낮춥니다. 두 값이 같아져 짧은 후보를 선택합니다. 보정이 없는 비교에서는 긴 표현 19e1이 선택됩니다. 이 계산은 E4M3의 Q4.4 사례에 해당하며, 다른 형식의 내부 정밀도와 표 절삭 조건을 설명하지 않습니다.

게시물은 yy를 빠른 dtoa 구현 중 하나로 소개합니다. 연결된 Apple M5 Max·macOS Clang 21.0 벤치마크에서 yy는 더블당 16.61ns, Żmij는 3.93ns를 기록했습니다. 이는 해당 장비와 컴파일러 구성에서 나온 측정값입니다.

자료: vitaut.net / 정리·해설: Trawling

참고 자료

원문 보기 ↗토론 보기 ↗