factoriel utilisant FFT

Question

Je suis en train de mettre en œuvre un programme C qui calcule la factoriel d'un n très grand nombre (jusqu'à un million), en utilisant fft et méthode de fractionnement binaire.

J'ai implémenté une bibliothèque simple pour représenter entier arbitraire de précision. Pour calculer le tout se passe bien, fft et IFFT, j'utilise twofft.c et four1.c routines de "Recettes numériques en C"

Jusqu'à un certain n, mais Lorsque les nombres (tableaux flottants) sont trop grands, le ifft (calculer avec quatre1), après normalisation et arrondi, a des valeurs qui sont fausses.

Par exemple, si j'ai deux nombres avec 2000 chiffres qui se termine avec 40 zéros, et je dois les multiplier l'autre (en utilisant fft), quand je calcule la IFFT, des zéros qui se terminent devenir « un ». cela se produit parce que lorsque j'ai arrondi un de ces "zéros", (0,50009 pour des exemples), ils sont devenus "un". Maintenant, je ne sais pas si ma mise en œuvre est fausse ou si je dois arrondir ce numebrs d'une manière différente. J'ai essayé d'utiliser les deux méthode split binaire et factorisation, mais pour n> = 9000, le résultat est mauvais .

existe un moyen de résoudre ce problème? merci pour votre attention et désolé pour mon mauvais anglais.

Answer 1

Comment représentez-vous des entiers de précision arbitraires?

Je veux dire quel type utilisez-vous actuellement?

Pouvez-vous s'il vous plaît nous montrer votre code?

Si vous vous sentez vraiment paresseux, vous pouvez cloner ce projet, je l'ai fait il y a quelques mois: https://github.com/nomadster/ESP

Edit:

En plus de lire votre message je suppose par cette déclaration

« ce arrive parce que quand j'ai arrondi un de ces "zéros", (0,50009 pour des exemples), ils sont devenus "un" "

que vous n'êtes toujours pas conscient du fait que la multiplication fft ne fonctionne que lorsque le L'erreur ndoff est inférieure à 0,5. Donc il me semble (si et seulement si j'ai correctement interprété votre message cryptique) que vous utilisez un type de virgule flottante qui n'a pas la précision requise.

Answer 2

Pour mémoire:

J'ai aussi remarqué de mauvaises valeurs renvoyées par IFFT à partir four1.c à partir de recettes numériques. Je l'ai seulement testé avec des valeurs complexes N = 256 en entrée, assemblées d'une manière, qu'elles devraient aboutir à un vrai signal de domaine temporel. Le vecteur du domaine temporel résultant doit être mis en miroir (de bout en bout et vice versa ...) et décalé de un pour correspondre aux IFFT des autres implémentations. (J'ai testé numpy.fft.ifft, ifft d'octave et une transformation de Fourier discrète inverse sans aucune optimisation, basée simplement sur la formule IDFT, qui devrait être définitivement correcte).

Il doit y avoir un défaut d'algorithme fondamental dans la version fournie par les recipies numériques. Dans leurs livres rien de relié à ce problème n'est décrit.