# 2^51 진법 트릭 (2017) > Clean Markdown view of GeekNews topic #21199. Use the original source for factual precision when an external source URL is present. ## Metadata - GeekNews HTML: [https://news.hada.io/topic?id=21199](https://news.hada.io/topic?id=21199) - GeekNews Markdown: [https://news.hada.io/topic/21199.md](https://news.hada.io/topic/21199.md) - Type: GN+ - Author: [neo](https://news.hada.io/@neo) - Published: 2025-05-31T09:47:41+09:00 - Updated: 2025-05-31T09:47:41+09:00 - Original source: [chosenplaintext.ca](https://www.chosenplaintext.ca/articles/radix-2-51-trick.html) - Points: 1 - Comments: 1 ## Topic Body - **큰 정수 연산**에서 발생하는 carry(자리 올림) 문제는 연산 병렬화를 어렵게 만드는 주요 원인임 - **x86 아키텍처**에서는 carry 처리를 위한 `adc` 명령이 일반 `add` 명령보다 느리고, 연속 carry 처리는 병렬 실행을 제한함 - **Radix 2^51 표현법**을 사용하면 carry 전파를 지연시켜 더 많은 덧셈을 빠르게 수행할 수 있음 - 각 limb(부분 값)에 51 또는 52 비트만 할당하여, 나머지 상위 비트 공간을 carry 임시 저장소로 사용함 - 이 테크닉은 **추가적인 레지스터 사용과 변환 비용에도 불구하고**, 실제로 2^64 진법보다 더 나은 성능을 제공함 --- ### 빠른 덧셈과 뺄셈: carry 문제 - **큰 정수 덧셈**에서는 인간이 손으로 자리수 단위로 carry를 처리하는 것처럼, 컴퓨터도 carry 때문에 덧셈 알고리듬을 병렬화하기 어려움 - 기본적으로 우리는 오른쪽(하위 자리)부터 하나씩 더하면서, 각 자리에서 발생하는 carry를 왼쪽(상위 자리)으로 올려줌 - 만약 왼쪽부터 덧셈을 시작하면 이전 carry가 다음 자리 연산에 영향을 주기 때문에, 연산 순서를 병렬화할 수 없음 ### 컴퓨터에서의 carry 처리 - 컴퓨터는 **64비트 정수** 단위로 덧셈을 처리함 - 256비트 정수를 64비트 limb 4개로 쪼개서 덧셈을 병렬로 처리할 수 있을 것처럼 보이나, 실제로는 overflow(carry)를 처리해야 올바른 결과가 만들어짐 - x86에는 carry 처리를 자동으로 해주는 `adc`(add with carry) 명령어가 있음 ### 성능 저하의 원인 - `adc` 명령은 carry flag라는 추가 입력값을 필요로 해, 단순한 `add`에 비해 **성능이 떨어짐** - Haswell 아키텍처 기준으로, `add`는 여러 포트에서 병렬 실행 가능한 반면 `adc`는 **직렬(순차) 실행**이 불가피함 - 특히 SIMD 명령(`vpaddq` 등)을 사용할 때 carry 없는 병렬 덧셈이 훨씬 빠름 ### carry를 지연시키는 아이디어 (종이 위 예시) - carry를 줄이기 위해, 자릿수 범위를 확장해 (예: 0-9에서 0-9, A-Z, *까지 총 37자리) 임시로 carry 없이 여러 수를 더할 수 있음 - 이렇게 하면 carry 전파 없이 여러 덧셈을 진행하고, 마지막에 한 번에 carry를 정리(normalization)할 수 있음 - 이 개념은 carry 누적과 전파를 분리해 **최종 단계에서만 carry 처리를 하도록 함** - 실제 연산에서는 자릿수 기준 값 이상의 값이 나왔다면, 오른쪽부터 차례로 carry를 누적 반영함 ### carry 지연의 컴퓨터 적용 (Radix 2^51 트릭) - 컴퓨터에서 carry 전파를 줄이기 위해 **radix 2^51 표현** 사용 - 256비트를 64비트 4개 limb가 아니라, 51~52비트씩 5개 limb로 분할 - 각 limb의 상위 12~13비트는 carry 임시 저장소로 기능 - 이 방식에서는 limb마다 2^64 값 범위를 유지한 채, 실제 연산 시 carry가 쉽게 발생하지 않아서, 여러 연산을 carry 없이 병렬적으로 수행 가능 - 약 2^13개의 연속 연산 후 한 번에 normalization(정규화) 필요 - Haswell CPU 기준, radix 2^51 적용 후 carry 없는 단순 덧셈만 여러 번 수행하여 **일반 radix 2^64보다 성능이 크게 향상됨** - normalization을 위한 carry propagation은 마지막에 한 번만 수행 ### 코드 예시 - 5개 레지스터에 값을 나눠 담아, carry 없는 덧셈 가능 - normalization은 각 limb의 상위 비트를 추출해 옆 limb에 더하고, 자신의 carry 값을 0으로 만드는 방식 반복 ### 뺄셈에의 확장 - 뺄셈도 비슷한 방식으로 적용 가능 - 이때 carry는 음수도 되므로, limb를 **signed integer**로 취급 - limb의 가장 높은 비트가 부호 비트로 할당되어, 덧셈에 비해 한 번에 처리 가능한 연산 횟수가 소폭 줄어듦 ### 결론 - carry 저항(지연) 테크닉은 limb 개수 증가와 변환 작업 추가에도 불구하고 **전체 연산 성능을 실제로 크게 향상시킴** - Radix 2^51 트릭은 대규모 정수 연산, 암호학 등 높은 성능을 요구하는 분야에서 널리 활용됨 - 이 테크닉은 실제 하드웨어/알고리듬 성능을 최적화하는 중요한 아이디어임 ## Comments ### Comment 39567 - Author: neo - Created: 2025-05-31T09:47:42+09:00 - Points: 1 ###### [Hacker News 의견](https://news.ycombinator.com/item?id=44132673) * 2^51이라는 숫자를 보고 처음엔 double 타입에 정수 저장 관련 얘기인 줄 알았지만, 실제로 Integer를 double로 정확히 담을 수 있는 값은 2^53-1임을 깨달음 * AVX512(그리고 AVX2도 어느 정도)에서 256비트 추가 연산을 상당히 효율적으로 구현할 수 있는 환경 제공, 더 많은 숫자를 레지스터에 담을 수 있다는 장점도 있음 직접적인 예시는 아래 코드처럼 동작 ```c __m256i s = _mm256_add_epi64(a, b); const __m256i all_ones = _mm256_set1_epi64x(~0); int g = _mm256_cmpgt_epu64_mask(a, s); int p = _mm256_cmpeq_epu64_mask(s, all_ones); int carries = ((g << 1) + p) ^ p; __m256i ret = _mm256_mask_sub_epi64(s, carries, s, all_ones); ``` 처리량까지도 개선되는 모습을 보여서 실제 코드 예시는 [godbolt.org](https://godbolt.org/z/e7zETe8xY)에서 볼 수 있음 이 논리를 512비트 덧셈까지 확장하는 것도 매우 단순함 * 특히 특정 인텔 CPU 아키텍처에서는 AVX512 명령어 사용만으로도 전체 프로세서 클럭이 다운되어 일관되지 않거나 오히려 느린 전체 성능으로 이어질 수도 있다는 점 지적 관련 참고는 [stackoverflow 링크](https://stackoverflow.com/questions/56852812/simd-instructions-lowering-cpu-frequency/56861355#56861355)에서 확인할 수 있음 * “13비트 말고 12비트를 쓰면 안되나?”라는 의문에 대해, 여기서는 가장 상위 비트(림)의 캐리 처리를 무시해서 오버플로우 시 wraparound 형식으로 동작하게끔 함 그 결과 가장 상위 림에는 52비트를 할당함으로써, 다른 림보다 더 빨리 공간이 모자라지는 단점이 있지만, C 언어에서 무부호 정수 합산과 비슷하게 작동함 그렇다면 최상위 림엔 64비트, 나머지 네 림엔 48비트씩 할당하는 방식은 어떤지 제안 이러면 정규화 전 더 많은 연산 누적이 가능하고, 워드 정렬 등의 이점이 있음 오버플로우 처리 특성도 동일함 * 최상위 림만 64비트 할당할 경우, 두 숫자의 림을 더하면 너무 빨리 오버플로우가 발생 예를 들어 둘 다 2^63값이면 바로 오버플로우 wraparound 산술 연산에서야 상관없지만 일반적인 경우엔 무리임 * 이런 구조라면 OP에서처럼 5개가 아닌 6개의 워드가 필요 명령어도 더 많이 필요하게 됨 * 목표가 256비트 수학을 5개의 64비트 레지스터로 해결하는 것에 있음 즉, 각 워드마다 256/5 = 51.2비트 분배가 이상적 이게 256비트 한정이라면 괜찮지만 범용 big-int 라이브러리엔 최적은 아님 예전엔 캐리 하나에 정확히 1바이트를 쓰려고 했던 배경이 있었고, 바렐 쉬프터가 없었던 시절이면 정렬을 위해 64 중 56비트만 활용하는 걸 선호 RISC-V에서는 하드웨어적으로 플래그가 없기 때문에 이런 논의가 더욱 중요 * 현대 x86 CPU(예: Intel Broadwell, AMD Ryzen)에서는 [Intel ADX](https://en.wikipedia.org/wiki/Intel_ADX) 명령어를 활용해 2^51 radix 표현이 전통적으로 강세였던 상황(예: Curve25519)에서도 더 빠를 수 있음 * 관련 논의 자료로 - [The radix 2^51 trick (2022년 11월)](https://news.ycombinator.com/item?id=33706153) - [The radix 2^51 trick (2017년)](https://news.ycombinator.com/item?id=23351007) * 핵심 교훈은, 연산들이 상호 독립적일 경우 연산을 더 많이 병렬로 실행시키는 쪽이 오히려 더 빠를 수 있음 반면, 의존성으로 인해 순차적으로 실행해야만 한다면 오히려 연산이 적어도 느릴 수 있음 이 아이디어는 긴 정수 연산뿐 아니라 다양한 영역에 적용 가능 * 64비트 청크로 분할해 캐리 여부에 따라 두 가지 경우를 미리 병렬 실행하고, 이후 실제 캐리 결과에 따라 옳은 연산을 선택하는 방식 제안 이 방식은 덧셈 횟수가 두 배가 되지만 전파 속도가 log(bits) 수준으로(선형이 아닌) 빨라짐 * 이 기법을 잘 이해 못했던 부분은, 이 방법이 본질적으로 ripple carry가 N값을 더할 때 N-1번 실행되는 걸 한 번만 실행하도록 한 점 캐리 처리 자체는 복잡해지지만 덧셈은 병렬화 가능 단, 입력 숫자를 5개 레지스터 단위로 나누는 작업 자체도 병렬화되어야 전체 효율이 의미 있음 * 이 규칙은 노드 수 만 단위를 가지는 슈퍼컴퓨터나 클라우드 레벨까지 확장 가능 많은 코어를 쓸 수 있으면 오버헤드는 무시할 만한 수준 * 이 아이디어는 NVidia도 관심을 갖고 있고 여러 영역에서 좋은 결과를 내고 있음 * 제목에 의견을 추가하면 안 된다는 HN 가이드라인은 있지만, 너무 과장된 클릭 유도형 제목들을 선호하지 않음 “일부 x86 아키텍처에서 carry 의존성 없이 64비트 정수 병렬 덧셈이 가능한 radix 2^51 트릭” 정도로 제한하는 게 더 정확하다고 생각 * 이 글을 몇 달만 일찍 읽었어도 도움이 됐을 거라는 아쉬움 버퍼를 임의의 진수로 인코드/디코드하는 과정에서 캐리가 버퍼 전체로 파급되어 알고리즘이 크게 느려지는 경험을 했음 최종적으로는 '여유 공간'을 남겨 chunk로 분할해 캐리를 처리했는데, 이 트릭과 유사점이 있는 듯 실제론 일부 비트를 낭비하는 대신 연산량이나 네트워크 대역폭을 절약하는 방법 선택 이와 같은 캐리 처리 역시 후처리로 묶을 수 있을지 궁금함 사실상 모든 이점을 가져갈 수 있는 구조가 되는지 희망사항임 * x86_64 환경만 쓰던 경험을 통해서, RISC-V에서 carry flag가 없어도 꼭 잘못된 접근은 아니라는 점을 명확히 보여줌 * 이 방식 외에도 64비트 림을 유지하면서 모두 uint64_t 변수로 carry-safe 덧셈을 하는 방법 설명 아래와 같은 흐름 ```c s0 += a0; s1 += a1; s2 += a2; s3 += a3; c0 = s0 < a0; // RISC-V sltu c1 = s1 < a1; c2 = s2 < a2; if (s1 == -1) goto propagate0; check_s2: if (s2 == -1) goto propagate1; add_carries: s1 += c0; s2 += c1; s3 += c2; goto done; propagate0: c1 = c0; goto check_s2; propagate1: c2 = c1; goto add_carries; done: ``` 관건은, 덧셈 결과(림)이 모두 1이 아닐 때, 해당 림의 캐리 아웃은 캐리 인에 의존하지 않고 단순히 원래 값을 더한 결과에만 의존함 반면 값이 모두 1이면 캐리 아웃=캐리 인 예측이 거의 불필요한 분기 구조라면 완벽히 병렬 실행 가능 확률적으로 2^64분의 1에만 느려지지만, 4-와이드 머신 등에선 큰 이득 없음 8-와이드 머신 또는 8-림 구조에서는 의미 있는 성능향상 x86_64엔 안 맞지만 Apple M* 시리즈처럼 8-와이드 머신이면 활용 가능성 Tenstorrent의 8-와이드 RISC-V Ascalon 프로세서, Ventana, Rivos, XiangShan 등에서 미래가 기대 SIMD 구조, 빠른 1-lane shift(slideup) 명령 있는 구조에선 효과 극대화 * 캐리-세이브 덧셈이 항상 add-with-carry보다 뛰어난 게 아님 두 종류의 multi-word addition 알고리즘은 상호 대체 불가, 각자 장단점이 있음 그러므로 ADC/SBB 명령은 ISA에 기본 포함, 레지스터 기반 플래그 저장도 가능 RISC-V에서 더 심각한 단점은 integer overflow flag가 없다는 점 오버플로 감지를 위한 SW 우회가 필요할 때 성능 하락이 carry 비트 우회보다 훨씬 큼 * RISC-V에서 carry flag가 없는 건 C 언어가 바이너리 carry flag를 무시한 것에서 파생 실제로는 carry flag 활용 빈도가 많이 낮음 * 나만 “carry flag가 어차피 느리면 risc5 gmp 논란은 왜 있었나?”라는 생각한 게 아니었음 * 'Radix trick'은 데이터 구조에도 적용 가능 Okasaki의 'Purely Functional Data Structures' 책에도 흥미로운 예시 존재