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 구현에서 발견한 또 다른 버그까지 상세히 다룹니다.