이 질문은 이진수의 곱셈과 다항식 곱셈 mod 2의 관계에 관한 것입니다. 질문을 구체적으로 만들기 위해 Knuth vol의 질문에 대한 더 나은 해결책이 있는지 이상적으로 알고 싶습니다. 2 권 3 호
계수가 컴퓨터 단어로 묶여 있으면 이진 컴퓨터에서 일반적인 산술 연산을 사용하여 다항식 모듈로 2의 곱셈을 촉진 할 수 있습니까?”
Knuth는 입력의 비트 수를 최악의 경우 로그 곱셈 계수로 확장하는 상당히 간단한 감소를 제공합니다. 이 로그 계수를 줄일 수 있습니까?
답변
물론, 당신은 그것을 1의 요소로 줄일 수 있지만 아마도 시간 비용이들 것입니다. 그러나 문제 뒤에있는 질문에 대답하기 위해 : 다항식의 곱셈 mod 2는 하드웨어 관점에서 (캐리지 비트를 전파 할 필요가 없음) 쉽지만, 정수의 곱셈은 사람들이 필수적이라고 생각하는 연산이므로 ALU 및 프로그래밍 언어.
