Fattoriale

[venexian]

Sto cercando di imparare il C#.
Come primo esercizio ho scritto un programmino ricorsivo per il calcolo del fattoriale per numeri un po' più grandi dell'usuale.
Sono arrivato a 9519!, ottenendo un numero che non riesco a trascrivere perché troppo lungo.
Lo allego come .zip
Su una lunghezza totale di 33741 cifre, le ultime 2377 sono '0'.
All'inizio credevo fosse un errore di calcolo. Poi, pensandoci, la motivazione è ovvia: se la cifra meno significativa diversa da zero, diventa zero in una delle moltiplicazioni, resterà tale anche in tutte le moltiplicazioni successive.
Pertanto, il numero di cifre meno significative uguali a '0' è un numero crescente all'aumentare del numero del quale viene calcolato il fattoriale.
Mi chiedevo se questa relazione fosse già stata studiata.
Mentre provo a tracciare un grafico di numTrailingZero(n!) in funzione di n, magari qualcuno di voi ne sa già qualcosa.

9519!.zip

(15.38 KiB) Scaricato 125 volte

[IsidoroKZ]

Mi pare semplice: ci sono piu` fattori 2 che fattori 5.

Il numero di fattori 5 e` pari alla somma della serie geometrica di ragione 1/5 moltiplicato per il numero di cui calcoli il fattoriale.

La serie da` 1/4 e quindi il numero di zeri e` pari a N/4, meno qualche unita` dovuta al fatto che si dovrebbero fare i conti con interi, quindi INT(N/5)+INT(N/25)+INT(N/125)+INT(N/625)+INT(N/3125)...

[DanteCpp]

Ma l'arrotondamento non dovrebbe stare fuori dalla sommatoria?

[IsidoroKZ]

Troncamento, non arrotondamento, e mi pare di no, che debba essere dentro.

[DanteCpp]

Ah, si!

La domanda è 'quanti cinque ci sono in...'.

[venexian]

Sì, è corretto. Questi sono i grafici per i primi e gli ultimi 120 N.
Il gioco era per provare il C#, che è entusiasmante. Ha fatto milioni di moltiplicazioni con numeri fino a 30 mila cifre in pochi minuti. Non lo credevo possibile.

gr1.gif (8.48 KiB) Osservato 3439 volte

gr2.gif (12.65 KiB) Osservato 3439 volte

[IlGuru]

Distribuendo il lavoro su più elaboratori si può fare anche di più

[venexian]

Mi hai fatto pensare ad un particolare, ho rilanciato il programma e verificato: il carico della CPU è solo il 25%. Avendo un i7 come processore, che è un quad-core, significa che il programma gira solo su uno dei quattro. Sicuramente è possibile lanciare il programma per utilizzarne di più, se non tutti. Mi chiedo se la cosa dipenda solo dal modo in cui si invoca l'eseguibile o se dipenda anche dalla compilazione. Domanda aggiunta alla lunga lista...

[IlGuru]

Potresti scrivere una funzione (n, m) che con n>m>0 calcola il fattoriale (n-x)(n-1)...(m)
Poi eseguirla 4 volte in 4 thread separati con diversi n ed m, alla fine moltiplicare tra loro i 4 risultati
Usare la ricorsione in questi casi, è elegante ma anti economico perché spendi un sacco di memoria per allocare la pila di sistema e quando lo fai con i microcontrollori poi te ne penti.
Così dovresti poter usare tutti i core

Codice: Seleziona tutto

using System;
using System.Threading;


[venexian]

@IlGuru
Il threading è argomento avanzato, previsto tra una ventina di ore di corso, ma... chi può resistere? Adesso provo
In effetti non mi interessa velocizzare il calcolo dei fattoriali da 30mila cifre, il lavoro era solo per fare qualcosa di più interessante del solito "Hello World!". Sono entusiasta del C#: un 'C++' senza tutta la verbosità e lo stantio di un linguaggio ormai troppo vecchio per essere al passo con i tempi, ma con le fondamenta che mancano a Java.

Adesso mi tirerò addosso orde di pinguini impazziti, ma Microsoft ha fatto davvero un bel lavoro.