Knuth의 장제법 알고리즘에서 40년 묵은 버그를 찾아내다
A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)
저자가 Knuth의 『The Art of Computer Programming』에 나오는 Algorithm D를 구현하던 중, 수십 년간 발견되지 않았던 버그를 찾아냈습니다. 알고리즘의 정확성을 보장하는 Theorem B의 증명에 의문을 품고 직접 증명을 시도하다가 실패했고, 그 과정에서 반례를 발견했습니다. 이 반례는 알고리즘의 오류를 드러냈고, 저자의 이름을 딴 정리가 교정본에 추가되었습니다. 이 글은 긴 나눗셈의 기초부터 멀티프리시전 정수 연산, 알고리즘의 정규화 과정, 버그가 발생한 원인과 오랫동안 발견되지 않은 이유, 그리고 LLVM 구현에서 발견한 또 다른 버그까지 상세히 다룹니다.
실패는 수십 년간 올바르다고 여겨져 온 Algorithm D에 대한 반례를 제시했고, 그와 함께 제 이름이 붙은 알고리즘의 정확성에 관한 정리를 얻게 되었습니다.
HN 토론
50- nk_kolja
나는 Knuth의 "컴퓨터 프로그래밍의 예술"에 나오는 장제법 알고리즘인 Algorithm D에서 버그를 발견했습니다. 이 버그는 Hacker News에서 몇 번 논의되었고(https://news.ycombinator.com/item?id=26562819), 다른 웹사이트에서도 논의되었습니다. Knuth에게 편지를 보냈고, 수표와 주석이 달린 답장을 받았습니다. 1969년 이후로 변경되지 않았던 업데이트된 정리 B는 이제 2026년 날짜로 표시됩니다. 취약한 구현을 찾는 과정에서 llvm에서도 "버그"를 발견했기 때문에, 그것에 대해서도 조금 더 자세히 설명했습니다.
- WalterBright
1980년대, DIV 명령어가 있기 전에 저는 정수 나눗셈을 구현했습니다. 저는 3학년 때 배운 것과 같은 장제법 알고리즘을 사용했지만, 10진법 대신 2진법으로, 시프트와 빼기를 사용했습니다. 그것은 또한 x87 칩이 없는 사람들을 위한 FDIV(부동 소수점 나눗셈) 구현의 기초이기도 했습니다. 아무도 그 버그를 보고한 적이 없습니다.
- enriquto
이것은 HN 역사상 가장 장대한 게시물일 것입니다.
편집: 저는 알고리즘 D를 따뜻하게 회상합니다... 90년대 제 첫 프로그래밍 경험 중 하나는 8086 어셈블리어로 덧셈, 뺄셈 등의 Knuth의 산술 알고리즘을 구현하려는 것이었습니다. 긴 곱셈까지는 제대로 구현했습니다(그것은 엄청난 노력이었습니다). 알고리즘 D는 감히 시도조차 하기에는 너무 어려웠습니다. 2026년에 사람들이 이러한 알고리즘을 면밀히 살펴보는 것을 보니 매우 기쁩니다.
- nickdrozd
축하합니다! 보상 체계가 중요도에 기반하지 않는다는 것이 재미있네요. 오류에 대해 0x$1.00, 제안에 대해 0x$0.20으로 정해져 있죠, 아무리 중요해도요. 개인적으로 저는 은행에 0x$4.40이 있는데, 이는 저자의 0x$1.00보다 많지만, 제 네 개의 오류와 두 개의 제안 중 어느 것도 이번 것만큼 중요하지 않았습니다. 그래도 책에 이름이 오르는 것은 꽤 멋진 일입니다! 이 버그는 알고리즘의 영어 설명에만 있는 것 맞죠? MIX 또는 MMIX 구현에는 버그가 없나요?
- vjerancrnjak
훌륭한 발견과 글입니다. 제 기억이 맞다면 올해 40명 이상이 수표를 받았고, 약 1000명이 은행에 계좌를 가지고 있습니다. 저도 올해 수표를 받았습니다. 2012년부터 몇 년마다 새로운 프로그래밍 언어나 접근법을 배우기 위해 다시 방문하는 연습 문제가 있었는데, 최신 업데이트로 인해 off-by-one 오류가 두 개 생겼습니다. 올해는 시간이 더 있어서 챕터의 처음으로 돌아가 미해결 문제를 시도했는데, 예비 단계에서 또 다른 off-by-two 오류가 있었습니다. 꽤 놀랐습니다. 오류를 찾는 것이 얼마나 어려운 일인지 깨닫게 해주었습니다. 마치 오류가 저를 위해 계획된 것처럼 느껴집니다. 저자가 암호학을 공부한 후 기술을 연마하기 위해 연습 문제를 풀기로 한 것처럼, 수표를 향한 가능성 없는 여정이었습니다.