Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C# / VB.NET - Fattorizzazione del prodotto di numeri primi
Forum - C# / VB.NET - Fattorizzazione del prodotto di numeri primi

Avatar
D@vide (Member)
Expert


Messaggi: 450
Iscritto: 30/06/2010

Segnala al moderatore
Postato alle 21:32
Martedì, 04/11/2014
Ragazzi sto sviluppando un programmino in C# per la scomposizione di un numero che è il prodotto di numeri primi (fino a 64bit).
Prima di implementarlo tramite MPI volevo assicurarmi che non ci sia un modo più ottimizzato per risolvere il problema.

Codice sorgente - presumibilmente C++

  1. using System;
  2. using System.Threading.Tasks;
  3.  
  4. namespace Primen
  5. {
  6.     class Factorization
  7.     {
  8.         public static Int64[] Factorize(Int64 k)
  9.         {
  10.             Int64 n = Math.Abs(k);
  11.  
  12.             var factors = new Int64[2];
  13.  
  14.             // Escludo a priori i numeri 1 e 2 che possono essere divisibili solo per se stessi e per 1
  15.             if (n == 1 || n == 2)
  16.             {
  17.                 factors[0] = n;
  18.                 factors[1] = 1;
  19.             }
  20.  
  21.             // Controllo preventivamente che il numero non sia divisibile per 2, escludendo tutti i suoi multipli nel for successivo
  22.             else if (n % 2 == 0)
  23.             {
  24.                 factors[0] = n / 2;
  25.                 factors[1] = 2;
  26.             }
  27.             else
  28.             {
  29.                 // Il cast è con troncamento e il ciclo Parallel.For è esclusivo del valore finale
  30.                 Int64 maxFactor = (Int64)Math.Ceiling(Math.Sqrt(n)) +1;
  31.  
  32.                 var loopResult = Parallel.For(3, maxFactor, (divisor, loopState) =>
  33.                 {
  34.                     if (n % divisor == 0)
  35.                     {
  36.                         factors[0] = n / divisor;
  37.                         factors[1] = divisor;
  38.  
  39.                         // Fermo tutti i for in parallelo compreso quello corrente
  40.                         loopState.Stop();
  41.                         return;
  42.                     }
  43.                 });
  44.  
  45.                 // Se il for è terminato senza trovare divisori, il numero è primo
  46.                 if(loopResult.IsCompleted)
  47.                 {
  48.                     factors[0] = n;
  49.                     factors[1] = 1;
  50.                 }
  51.             }
  52.  
  53.             //  Se il numero da fattorizzare è negativo, uno e un solo dei due numeri primi deve essere negativo
  54.             if (k < 0)
  55.                 factors[0] *= -1;
  56.  
  57.             return factors;
  58.         }
  59.     }
  60. }


PM Quote
Avatar
dnha (Member)
Pro


Messaggi: 137
Iscritto: 24/07/2014

Segnala al moderatore
Postato alle 18:51
Mercoledì, 05/11/2014
Un implementazione interessante potrebbe essere "L'Algoritmo rho di Pollard":
http://it.wikipedia.org/wiki/Algoritmo_rho_di_Pollard
http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm

Tra l'altro è il più veloce algoritmo deterministico per fattorizzare un numero primo. :k:


“La principale differenza tra una cosa che potrebbe rompersi e una cosa che non può in alcun modo rompersi è che quando una cosa che non può in alcun modo rompere si rompe, di solito risulta impossibile da riparare.” [Douglas Adams, Praticamente innocuo]
PM Quote
Avatar
D@vide (Member)
Expert


Messaggi: 450
Iscritto: 30/06/2010

Segnala al moderatore
Postato alle 19:03
Mercoledì, 05/11/2014
Testo quotato

Postato originariamente da dnha:

Un implementazione interessante potrebbe essere "L'Algoritmo rho di Pollard":
http://it.wikipedia.org/wiki/Algoritmo_rho_di_Pollard
http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm

Tra l'altro è il più veloce algoritmo deterministico per fattorizzare un numero primo. :k:



Ciao dnha, ero all'oscuro di questo metodo, ti ringrazio anticipatamente e faccio una bella ricerca, la complessità sembra comunque minore della mia O(sqrt(n))
Nel frattempo ho notato che si parla degli algoritmi sotto il nome di "Famiglia di Kraitchik", ne hai mai sentito parlare?

PM Quote
Avatar
dnha (Member)
Pro


Messaggi: 137
Iscritto: 24/07/2014

Segnala al moderatore
Postato alle 19:56
Mercoledì, 05/11/2014

Ultima modifica effettuata da dnha il 05/11/2014 alle 19:59


“La principale differenza tra una cosa che potrebbe rompersi e una cosa che non può in alcun modo rompersi è che quando una cosa che non può in alcun modo rompere si rompe, di solito risulta impossibile da riparare.” [Douglas Adams, Praticamente innocuo]
PM Quote
Avatar
D@vide (Member)
Expert


Messaggi: 450
Iscritto: 30/06/2010

Segnala al moderatore
Postato alle 22:59
Mercoledì, 05/11/2014
Testo quotato
PM Quote