[C]Calcolo del fattoriale

[Feazzu]

Salve a tutti..
sto realizzando un programma in C che calcoli il fattoriale di un numero arbitrariamente grandi (la specifica del progetto è quella di calcolare il fattoriale di un milione).
ho creato una piccola libreria per poter rappresentare i numeri in notazione polinomiale in base 100.
Per calcolare il fattoriale uso il metodo del binary splitting e per le moltiplicazioni uso la FFT.
Il programma calcola correttamente n! per n fino a 9000/10000, poi purtroppo succede che col calcolo della trasformata incersa, alcuni valori, a causa dell'arrotondamento, diventino "uni" anzichè "zeri", compromettendo tutti i successivi calcoli.
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).

Volevo chiedere a voi quindi se avete mai usato queste funzioni e se avevate mai avuto questi problemi.
In caso contrario, volevo chiederti se avete mai sviluppato un programma del genere e,se si, che librerie avete usato per il calcolo della FFT.
Come ultima cosa vi chiedo se avete mai sviluppato un programma che calcolasse n! di numeri molto grandi, e che algoritmo e strutture dati avete usato.
Vi ringrazio per l'attenzione..

[Cait Sith]

non conosco il metodo che stai usando per il calcolo del fattoriale però ti posso dire che è normale che la fft, dopo un andata e un ritorno, lasci del rumore numerico (trascurabile per gli usi normali)
poi non ho capito se questa fft è in float, double o con il tuo tipo base 100

a occhio direi che è non è un problema della fft (che è corretta) ma proprio della precisione numerica che non è sufficiente su dei numeri con quell'ordine di grandezza
poi per carità, può anche darsi che la routine che usi non si presta particolarmente a gestire numeri molto grandi ma qui più che problema di algoritmo credo sia un problema di analisi numerica e propagazione dell'errore

[demos88]

Il fattoriale è una operazione definita sui numeri naturali più lo zero.
Se il tuo programma usa variabili a virgola mobile (float o double) è sicuro che a un certo punto il fattoriale approssimato non sarà più corrispondente al reale, per il semplice fatto che molti interi non hanno una rappresentazione esatta in virgola mobile, ma approssimata, e man mano che il valore cresce, l'arrotondamento diventa sempre più grande. Se poi i calcoli sono consecutivi, ad ogni operazione aggiungi l'errore della precedente.
Prova a vedere se le librerie GMP ti possono aiutare: http://gmplib.org/
ma il fattoriale di un milione... mah
E' un esercizio didattico o un progetto di lavoro? perchè mi sembra esagerato

[Cait Sith]

giusto per curiosità ho controllato con la fft del matlab:
ho generato un vettore di zeri
ho posto un campione a 10^100 ho fatto fft e ifft, ebbene nel risultato c'erano un sacco di campioni che invece di essere zeri avevano valori dell'ordine di 10^83 (e matlab lavora in double)
quindi non è un problema della tua fft

[Feazzu]

Innanzittutto grazie per le risposte

Originariamente inviato da demos88

Il fattoriale è una operazione definita sui numeri naturali più lo zero.
Se il tuo programma usa variabili a virgola mobile (float o double) è sicuro che a un certo punto il fattoriale approssimato non sarà più corrispondente al reale, per il semplice fatto che molti interi non hanno una rappresentazione esatta in virgola mobile, ma approssimata, e man mano che il valore cresce, l'arrotondamento diventa sempre più grande. Se poi i calcoli sono consecutivi, ad ogni operazione aggiungi l'errore della precedente.
Prova a vedere se le librerie GMP ti possono aiutare: http://gmplib.org/
ma il fattoriale di un milione... mah
E' un esercizio didattico o un progetto di lavoro? perchè mi sembra esagerato

Si tratta di un esercizio didattico. Però qui non si parla di errore accumulato, perchè nel mio algoritmo, ad ogni risultato di una moltiplicazione io faccio in modo di avere un array di interi.
il problema però sorge quando devo calcolare una fft,e poi di conseguenza la sua inversa, su un array di 2^15 elementi..in questo caso credo che cmq i valori calcolati dalla routine di four1, essendo calcolati su un pigreco che sarà troncato in un certo punto, risentano appunta della dimensione dell'array e quindi il problema di calcolare la fft su un numero tropo elevato di punti.

Originariamente inviato da Cait Sith

giusto per curiosità ho controllato con la fft del matlab:
ho generato un vettore di zeri
ho posto un campione a 10^100 ho fatto fft e ifft, ebbene nel risultato c'erano un sacco di campioni che invece di essere zeri avevano valori dell'ordine di 10^83 (e matlab lavora in double)
quindi non è un problema della tua fft

Se ad esempio io ho il numero 2 che nella rappresentazione da me usata sarà un array a[]={02,00,00,00......,00} formato da n elementi, con n che può assumere valori di 2^15/2^16 elemnti (e anche molti di più)..quando io calcolo la fft non avrò tutti due, ma avrò valori tipo 1,99956; 2,00123; ecc..però una volta che eseguo la moltiplicazione membro a membro tra gli elementi dei vettori, e poi calcolo l'inversa, una volta che arrotondo, il valore che ottengo è quello esatto che si avrebbe coi valori esatti.
(forse non sono stato molto chiaro in questo ultimo pezzo).

Originariamente inviato da Cait Sith

non conosco il metodo che stai usando per il calcolo del fattoriale però ti posso dire che è normale che la fft, dopo un andata e un ritorno, lasci del rumore numerico (trascurabile per gli usi normali)
poi non ho capito se questa fft è in float, double o con il tuo tipo base 100

a occhio direi che è non è un problema della fft (che è corretta) ma proprio della precisione numerica che non è sufficiente su dei numeri con quell'ordine di grandezza
poi per carità, può anche darsi che la routine che usi non si presta particolarmente a gestire numeri molto grandi ma qui più che problema di algoritmo credo sia un problema di analisi numerica e propagazione dell'errore

la funzione per il calcolo della fft prende in ingresso due array di n float e calcola la fft di quei due array. Ottengo così due array che sono di dimensione 2*n essendo dei numeri complessi con parte immaginaria e parte reale.
a questo punto faccio una moltiplicazione membro a membro (tra numeri complessi) e poi calcolo la trasfomrata inversa.
gli array che dò in pasto a tale funzione sono la rappresentazione polinomiale dei miei numeri, in base 100. Ad esempio, il numero 1234567, sarà rappresentato come
foat a[]= {67,54,23,01}.

[Feazzu]

Salve a tutti di nuovo.
Potrei aver capito il problema.
penso si tratti dell'errore di convoluzione che, al momento dell'arrotondamento, mi da risultati che sono errati (come ad esempio gli "uni" di cui parlavo).
Ho letto che per risolvere questo problema bisogna utilizzare il metodo dell'overlap (add o save).
Da quel (poco) che ho capito, consiste nel dividere l'array in più parti e processarle per poi riunirle, sovrapponendo una porzione dell'array risultante a quello successivo.
Quello che non ho capito però è sapere con quale criterio dividere l'array e soprattutto con quale criterio unire i risultati con queste sovrapposizioni.
Sapete percaso darmi una mano con questo?
vi ringrazio ancora per l'attenzione