Comprendre l'algorithme Schönhage-Strassen (énorme multiplication entier)

Question

Je dois multiplier plusieurs 1000s chiffres entiers longs aussi efficacement que possible en Python. Les chiffres sont lus à partir d'un fichier.

Je suis en train de mettre en œuvre le Schönhage-Strassen algorithme entier multiplication, mais je suis coincé sur la compréhension de la définition et les mathématiques derrière elle, spécialement transformée de Fourier rapide.

Toute aide à comprendre cet algorithme, comme un exemple pratique ou d'un pseudo-code serait très apprécié.

Answer 1

Chapitre 4.3.3 de Knuth de TAOCP décrit et a aussi quelques FFT pseudocode dans d'autres chapitres qui pourraient être utilisés pour cela.

Answer 2

1000 chiffres est « petit » pour Schönhage-Strassen pour être vraiment intéressant d'utiliser. Vous pouvez jeter un oeil à la multiplication du Toom Cook. gmpy est une enveloppe de python pour gmp fournir ces fonctions.

Answer 3

Ne pas réinventer la roue. GMP a une excellente mise en œuvre de haute performance de cet algorithme et tout algorithme écrit en pur Python sera au moins 100 fois plus lent, tout simplement parce que Python est un langage interprété. Utilisez gmpy pour appeler aux BPF de votre application Python. Je suis aussi curieux de ce que l'application vous travaillez qui nécessite la multiplication de ces grands nombres - il pourrait y avoir un moyen de gérer votre problème plus simple

.

En outre, comme mentionné par d'autres réponses, « plusieurs 1000s chiffres » est pas assez longtemps pour justifier Schönhage-Strassen (vous devriez avoir au moins 10000 chiffres décimaux, probablement plus). Une variante de Toom-Cook comme Toom-3 est normalement utilisé dans cette gamme. Encore une fois, ne pas écrire vous-même en Python -. La mise en œuvre de BPF est très soigneusement optimisé