Schönhage-Strassen 알고리즘 이해 (거대한 정수 곱셈)

Question

파이썬에서 가능한 한 효율적으로 1000 숫자의 긴 정수를 곱해야합니다. 숫자는 파일에서 읽습니다.

나는 그것을 구현하려고 노력하고있다 Schönhage-Strassen 정수 곱셈을위한 알고리즘이지만, 그 뒤에있는 정의와 수학, 특히 빠른 푸리에 변환을 이해하는 데 갇혀 있습니다.

실용적인 예 또는 일부 의사 코드와 같이이 알고리즘을 이해하는 데 도움이 될 것입니다.

Answer 1

Knuth 's의 4.3.3 장 taocp 이를 설명하고 다른 장에서는 FFT 의사 코드가 있습니다.

Answer 2

Schönhage-Strassen은 실제로 사용할 가치가있는 1000 자리가 "작은"입니다. 당신은 툰 쿡 곱셈. gmpy 이러한 기능을 제공하는 GMP에 대한 파이썬 래퍼입니다.

Answer 3

바퀴를 재발 명하지 마십시오. GMP는이 알고리즘의 훌륭한 고성능 구현을 가지고 있으며, Python은 해석 된 언어이기 때문에 순수한 파이썬으로 작성된 모든 알고리즘은 100 배 이상 느리게됩니다. 사용 gmpy 파이썬 응용 프로그램에서 GMP에 호출합니다. 또한 많은 수의 곱셈이 필요한 응용 프로그램도 궁금합니다. 문제를 처리하는 더 간단한 방법이있을 수 있습니다.

또한 다른 답변에 의해 언급 된 바와 같이, "수 다 1000 자리 길이"는 Schönhage-Strassen을 정당화하기에 충분히 길지 않습니다 (아마도 최소 10000 자리 숫자가 있어야합니다). Toom-3과 같은 Toom-Cook의 일부 변형은 일반적 으로이 범위에서 사용됩니다. 다시 말하지만, 이것을 파이썬에 직접 쓰지 마십시오 -GMP의 구현은 매우 신중하게 최적화되었습니다.