Gli algoritmi per il calcolo del fattoriale

matteos43

Il fattoriale di un numero n, indicato con la simbologia n!, rappresenta il prodotto di tutti gli interi da 1 fino al numero n compresi, ovvero:

\prod_{i = 1}^{n} i

Il calcolo del fattoriale seguendo la formula canonica può rivelarsi essere molto lungo e molto esigente, dal punto di vista del costo computazionale. Tuttavia esistono diversi algoritmi che permettono il calcolo del fattoriale in un minor lasso di tempo. I principali sono:

  • SpliRecursive: è l’algoritmo più rapido che non utilizza la fattorizzazione in primi ed è relativamente semplice da implementare;
  • PrimeSwing: è l’algoritmo conosciuto asintoticamente più veloce per calcolare n!; si basa sul concetto di “Swing Numbers”, calcolando il fattoriale tramite la scomposizione in fattori primi;
  • Poor Man’s: questo algoritmo non utilizza nessuna libreria Big-Integer, può essere facilmente implementato su qualsiasi computer ed è rapido fino a 10000 fattoriale.
  • ParallelPrimeSwing: corrisponde all’algoritmo PrimeSwing con prestazioni migliorate grazie a metodi di programmazione concorrenti e sfruttando così processori multipli.

Lascia un commento