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

파이썬에서 가능한 한 효율적으로 1000s 자리 정수를 곱해야합니다. 번호는 파일에서 읽습니다.Schönhage-Strassen 알고리즘 (거대한 정수 곱셈) 이해

정수 곱셈 알고리즘을 구현하기 위해 노력하고 있는데, 특히 그 정의와 수학, 특히 고속 푸리에 변환을 이해해야합니다.

실용적인 예 또는 의사 코드와 같은이 알고리즘을 이해하면 도움이됩니다.

2009-05-14 JPCosta

하나의 매우 중요한 힌트 : 꼭 필요한 경우가 아니면 자신의 FFT를 구현하지 마십시오. 파이썬에서 사용할 수 있다면 계산을 위해 FFTW를 사용하십시오. 너 자신을 구현하는 꿈을 꾸는 것이 무엇이든 훨씬 능가 할 것입니다. 간단한 FFT가 그리 어렵지는 않지만, 어려운 부분은 빨리 처리하고 있습니다. 특히 계산중인 숫자가 2의 거듭 제곱의 힘이 아니라면 더욱 그렇습니다. – LiKao

@LiKao : Schönhage-Strassen은 일반적으로 임의의 크기의 정수와 Number Theoretic Transform의 고정 크기 벡터를 사용하여 구현되지만 FFTW와 같은 패키지로 구현되는 FFT는 부동 소수점 및 고정 크기 요소를 사용하므로 실제로 매우 도움이됩니다. –

Knuth의 TAOCP의 4.3.3 절은이를 설명하고이 장에서 사용할 수있는 다른 장의 일부 FFT 의사 코드도 가지고 있습니다.

출처

2009-05-14 07:35:58 schnaader

1000 자리수는 Schönhage-Strassen이 "사용하는 가치가있는"작은 숫자입니다. Toom Cook 곱셈을 살펴보십시오. gmpy은 이러한 기능을 제공하는 gmp에 대한 파이썬 래퍼입니다.

출처

2009-05-14 07:34:22

+1, OP가 그 사실을 알고 있기를 바랍니다. 그가 링크 된 위키 피 디아 엔트리는 매우 초기에 설명합니다 ("오래된 메소드 [...] (10,000- 40,000 자릿수)를 능가하기 시작합니다.") – schnaader

미안하지만, 나는 " . 질문을 편집합니다. – JPCosta

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

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

출처

2011-11-03 03:35:25

예를 들어, PyopenCL은 어떻습니까? – user2284570

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

답변

관련 문제