[MatLab] Mathematica batte MatLab nel calcolo dell'antifattoriale

[extrabyte]

L'antifattoriale è la funzione inversa del fattoriale. Dato un intero naturale m, determinare un intero n tale che n! = m. Naturalmente ciò non è sempre possibile, poichè il fattoriale è un'applicazione non suriettiva.
Trattandosi di un'applicazione definita per ricorsione (o ciò che è lo stesso, per ricorrenza), essa si presta ad essere trasdotta in un algoritmo includenti le famose strutture di controllo che caratterizzano i vari linguaggi di programmazione. Ebbene, mentre con Matlab occorrono svariate righe di codice, con Mathematica basta un semplicissimo costrutto if annidato in un loop Do, come indicato qui

[onlyReferee]

Ogni tool è giusto usarlo per gli scopi per cui è più adatto: Mathematica è più forte sul calcolo simbolico rispetto a Matlab, che è invece migliore per quanto riguarda il calcolo numerico.
Ammetto che appena ho letto il titolo della discussione pensavo si trattasse di una "vittoria" in termini di prestazioni intese come velocità di esecuzione.

[apatriarca]

Non mi è chiaro dove vuoi arrivare con questo post. Matlab e Mathematica sono linguaggi molto diversi, progettati con obiettivi molto diversi tra di loro. Alcuni programmi sono più comodi da scrivere in Matlab e altri in Mathematica. Altri ancora è meglio scriverli in linguaggio ancora diversi. Il principale problema di Matlab in questo caso non è tanto legato alla poca espressività del linguaggio, ma del fatto che Matlab è principalmente pensato per fare calcoli con valori in virgola mobile e non con interi di grandi dimensioni.

[Esperanto]

...ma il cervello batte entrambi.
La potenza di calcolo dei computer tende a favorire l'approccio brute force invece dell'impegno all'ottimizzazione.
Io ho ancora del libri di matematica di mia mamma (classe '24) intitolati Calcolo Mentale Facilitato. Insegnavano a usare la testa.
Io ho accettato la sfida su questo problema e ho scoperto questo metodo . Non so se sono originale ma ve lo propongo.
Primo passo: ricerca dell' "ordine di grandezza" a passi di 5.
Un numero fattoriale ha un numero di Zeri che dipende dal numero di sottomultipli uguali a 5.
Ne ha uno per ogni 5, due ogni 25, tre ogni 125, ecc.
Partendo da qui, basta contare il numero di zeri per capire in che range si troverebbe il nostro Fattoriale.
Secondo passo: A questo punto basta dividere il numero di cui vogliamo l'antifattoriale per i 5 numeri successivi a quello trovato. Se una delle divisioni dà riultato frazionario...il numero non è un fattoriale ed è già un bel passo avanti
Se tutte danno risultato intero possiamo calcolare l'antifattoriale con l'algoritmo brute force o metodo migliore
Qualche idea l'ho stesa anche lì ma non voglio tediarvi
Forse richiede qualche linea di codice in più ma, sicuramente, abbrevia il tempo di calcolo e, soprattutto, da la soddisfazione all'uomo di essere superiore ai computer: con la forza si può imporre, col cervello si può creare.
Se qualcuno è interessato potrò postare anche qui un esempio di calcolo (http://it.emcelettronica.com/linversion ... le-inverso)
Mi farebbe piacere un consiglio o critica da parte di esperti.

[apatriarca]

Il problema del tuo metodo è che i numeri che sono immagine di fattoriali sono molto pochi. Il fattoriale è poi una successione che cresce molto velocemente. Il metodo più veloce è quindi certamente quello di costruirsi una tabella e andare a cercare il numero in tale tabella. Considera per esempio che se dovessi implementare questo antifattoriale per numeri a 64 bit, avresti appena 20 numeri nella tabella.

[Super Squirrel]

Come ha spiegato apatriarca da un punto di vista pratico il metodo ha una scarsa utilità.

Considera per esempio che se dovessi implementare questo antifattoriale per numeri a 64 bit, avresti appena 20 numeri nella tabella.

Ragionando però in termini matematici, posto:
n = m!
z --> numero di zeri finali di n
x --> valore iniziale dell'intervallo chiuso a cui dovrebbe appartenere m (ossia [x;x+4] o anche x <= m <= x+4)

per esempio la seguente rappresentazione:

[0 - 4] 0 , [5 - 9] 1 , [10 - 14] 2 , [15 - 19] 3 , [20 - 24] 4 , [25 - 29] 6 , [30 - 34] 7 , [35 - 39] 8 , [40 - 44] 9 , [45 - 49] 10 , [50 - 54] 12 ...

ci permette di dire che il fattoriale dei numeri compresi tra 0 e 4 non presenta zeri finali, tra 25 e 29 ne presenta 6 etc..

detto questo come si esplicita la funzione x=f(z) ? cioè contati gli zeri finali di n come facciamo a trovare il valore iniziale dell'intervallo di accettazione? oppure come facciamo a sapere se z è un valore accettabile ? infatti dall'esempio fatto sopra si nota che un numero che termina con 5 o 11 zeri non può essere un fattoriale.

[Esperanto]

Calcoliamo l'antifattoriale di:

2283860335914641457397265865115333727042973071546228701773634716126027
6926030248458777765497919211029457065581960747795750095505232241970499
5617697230205658766722616606097632340497755473254301355713314682574755
3799450849523377065894531021055272516334278466875614904921365807833845
8534285571551800849578848226429898670032945513859929938621783523490272
6469669185449361408000000000000000000000000000000000000000000000000000
00

ha 53 zeri di cui int(53/25) = 2 dovuti al passaggio per 125; int(53/5) = 10 dovuti a passaggio per 25 e quindi 53 -10 -2 = 41 dovuti a passaggi per 5.
Quindi il nostro numero va cercato a partire da 41 * 5 = 205! in su.
5 divisioni ci permettono di individuare il possibile buon candidato (massimo che non da resto).
Si prosegue poi a ritroso fino trovare una divisione che da resto.
Se non si trova, abbiamo l'antifattoriale (il numero massimo trovato prima). Se si trova, il numero sotto test non è un fattoriale.
Partendo dall'alto dobbiamo fare un numero di divisioni che è AL MASSIMO uguale a quello Brute force, ma potenzialmente più breve in molti casi.

Nessuna pretesa di avere trovato formule miracolose ma mi piaceva avere un confronto sul metodo.
Potenzialmente costa meno fare 209 moltiplicazioni SICURE e 209 confronti per decidere se abbiamo preso o superato il numero in indagine.
Io mi sono divertito a pensarci anche se accetto di buon grado che non serve a molto.
Lascio a voi ricalcolare il numero antifattoriale di quello di partenza

[Esperanto]

ERRATA CORRIGE
ha 53 zeri di cui int(53/25) = 2 dovuti al passaggio per 125; int(53/5) = 10 dovuti a passaggio per 25 e quindi 53 -10 -2 = 41 dovuti a passaggi per 5.
Quindi il nostro numero va cercato a partire da 41 * 5 = 205! in su.

DIVENTA
ha 53 zeri di cui int(53/31) = 1 dovuti al passaggio per 125; int(53/6) = 8 dovuti a passaggio per 25 e quindi 53 -8 -1 = 44 dovuti a passaggi per 5.
Quindi il nostro numero va cercato a partire da 44 * 5 = 220! in su.

Scusate. la gatta frettolosa fa i gattini ciechi.

[apatriarca]

Dovendo fare il calcolo a mano, può essere utile avere qualche idea intuitiva di quale potrebbe essere l'ordine di grandezza del fattoriale. Ma quando si tratta di fare calcoli con il PC, spesso la soluzione brute force supera qualsiasi metodo più intelligente. Considera per esempio il sudoku. Il metodo migliore per risolverlo per un umano è molto diverso da quello usato per un computer (che prova semplicemente tutte le possibilità fino ad arrivare ad una soluzione). La principale ragione è che i computer sono molto più lenti a prendere decisioni e a fare test di quanto non siano a fare calcoli.

Un computer ci metterebbe più o meno lo stesso tempo a fare le tue analisi sugli zeri di quanto non ci metta a calcolare tutti i 220 fattoriali necessari. Per noi umani il discorso è ovviamente diverso. Fare calcoli con numeri di quelle dimensioni è molto faticoso e la probabilità di errore troppo alta. Dovendo affrontare il problema a mano avremmo quindi bisogno di metodo come il tuo. In un certo senso, i fattoriali diventano così rari con il crescere del numero che potrebbe bastare probabilmente anche solo il conteggio delle cifre per stabilire quale fattoriale possa essere. Guardando manuali e articoli matematici di qualche decennio fa ci si rende conto che una volta erano molto più abili nel fare calcoli e che conoscevano trucchi che ora si sono persi. Abbastanza recente è il caso di un ricercatore di computer grafica che ha riscoperto tecniche di calcolo degli anni 60 in fisica delle particelle di cui l'attuale comunità scientifica non ne era a conoscenza* (e che gli ha valso alcune pubblicazioni nel campo).

* E l'ha fatto con l'obiettivo di simulare l'interazione tra la luce e la pelle umana. Penso che nessuno si sarebbe mai immaginato una applicazione del genere per quelle equazioni.

[Super Squirrel]

Avevo fatto il seguente programma in C++

Codice:

#include <iostream>
#include <cstdint>

int main()
{
    bool scelta;
    std::cout << "Intervallo di appartenenza di un numero il cui fattoriale presenta un certo numero di zero finali (0) ";
    std::cout << std::endl << "Numero di zero finali del fattoriale di un certo numero (1)" << std::endl << "Cosa vuoi fare? ";
    std::cin >> scelta;
    if(scelta == 0)
    {
        int64_t k = 5, j = 6, x = 0, z;
        std::cout << std::endl << "Numero di zero finali: ";
        std::cin >> z;
        while(z >= j)
        {
            x = x + z / j;
            k = k * 5;
            j = j + k;
        }
        x = (z - x) * 5;
        std::cout << std::endl << "Intervallo: " << x << " <= m <= " << x + 4 << std::endl;
    }
    else
    {
        int64_t k = 5, m, z = 0;
        std::cout << std::endl << "Valore: ";
        std::cin >> m;
        while(m >= k)
        {
            z = z + m / k;
            k = k * 5;
        }
        std::cout << std::endl << "Zero finali: " << z << std::endl;
    }
}

scelta (1) ----> inserisco 220 ----> mostra 53
scelta (0) ----> inserisco 53 ----> mostra 220 <= m <= 224
tutto giusto!

scelta (1) ----> inserisco 700 ----> mostra 174
scelta (0) ----> inserisco 174 ----> mostra 695 <= m <= 699

per ricavare il range dal numero di zero credo usiamo lo stesso metodo:
x = 5( 174 - int(174/6) - int(174/31) - int(174/156)) = 695
il fattoriale di 700 ha effettivamente 174 zero finali. come spiegate il fatto che l'intervallo parta da 695 e non da 700?