"if문 거슬려서 전수조사 돌림"… 컴퓨터가 직접 찾아낸 기적의 최적화 코드

요약 부동소수점 연산 라이브러리를 개발하던 한 개발자가 if 분기문 없이 부동소수점의 최하위 비트(lowest set bit)를 추출하는 최적의 수식을 찾기 위해 모든 경우의 수를 무차별 대입(brute-force)해 탐색한 과정을 공유했습니다. 개발자는 주어진 부동소수점 수에서 최하위 비트 값을 구하는 함수를 구현하던 중, 일반적인 비트 연산 방식이 2의 거듭제곱 수치에서 오동작하여 조건문(if)을 추가해야 하는 문제에 부딪혔습니다. 하지만 조건문은 분기 예측 실패 시 속도 저하를 일으키기 때문에, 분기문 없이 단일 수식으로 동작하는 더 최적화된 방식을 찾고자 했습니다. 최신 대규모 언어 모델(LLM) 대신 전통적인 전수 조사 방식을 택한 개발자는 연산 횟수를 5개 이하로 제한하고, 정수 덧셈·뺄셈, 비트 AND/OR/XOR 연산, 부동소수점 뺄셈 등 유용한 연산자 6종과 64개의 비트 상수 후보군을 설정했습니다. 탐색 공간은 방대했으나, 동일한 결과값을 내는 중복 수식을 제거하는 귀납적 탐색 알고리즘을 설계해 단 4분 만에 모든 조합에 대한 탐색을 마쳤습니다. 그 결과 연산 5개로 동작하는 여러 수식을 발견했고, 나아가 중간 계산 결과를 재사용하면 단 4개의 연산만으로 구현 가능한 놀라운 수식을 찾아냈습니다. 이 수식은 가수부 비트가 제거된 값을 재활용해 음수화 연산과 결합하는 기발한 트릭을 내포하고 있었으며, 개발자는 별도의 인공지능 모델 없이 컴퓨터 전수 조사만으로도 인간이 생각하기 힘든 영리한 최적화 공식을 찾아낼 수 있었다며 만족감을 표했습니다. 현재 이 최적화 코드는 개발 중인 FPU 에뮬레이터에 성공적으로 반영되었습니다.