Salve a tutti.
Se mi è concesso, ripropongo un post che era stato chiuso per crossposting circa due mesi fa.
Devo realizzare un programma in C, che mi permetta di calcolare il fattoriale di numeri grandi (la specifica del progetto è quella di calcolare il fattoriale di un milione).
Per calcolare il fattoriale ho usato il metodo del binary splitting, mentre le moltiplicazioni le eseguo con l'uso della FFT.
Il Programma calcola correttamente il fattoriale fino a 10.000!, poi però si hanno degli errori nel calcolo della fft e dell'inversa, che compromettono il risultato.
Le funzioni che uso per la fft sono quelle presenti nel libro Numerical Recipes-Seconda Edizione e si possono trovare anche online (four1.c e twofft.c).
Gli interi sono implementati come array di float (in notazione polinomiale in base 100).
Il calcolo della fft "sballa" quando tale array assume grosse dimensioni.
Già il fattoriale di 10.000 è un numero di 35k cifre, e la dimensione dell'array, a causa dell'imlementazione della fft, è di 64k posizioni.
Quindi chiedo a voi se percaso avete mai realizzato un programma che calcoli il fattoriale di grandi interi, e che strutture dati avete utilizzato (o in generale come lo avete implementato) o se avete mai avuto a che fare con la fft.
Non chiedo il programmino già fatto, ma solo qualche idea da cui partire, oppure qualche consiglio su come correggere la mia implementazione.
Vi ringrazio per l'attenzione.