Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
Algoritmi - Comparazione Numeri primi
Forum - Algoritmi - Comparazione Numeri primi

Pagine: [ 1 2 3 4 ] Precedente | Prossimo
Avatar
Fharamir (Normal User)
Rookie


Messaggi: 21
Iscritto: 06/05/2011

Segnala al moderatore
Postato alle 15:13
Mercoledì, 27/11/2013
Salve gente,

Ho terminato poco fa un programma che elenca i numeri primi da 19 in poi.
Volevo verificare la sua efficienza mettendolo a confronto con un altro programma molto simile trovato su questo sito.

Il risultato è stato che il programma trovato su questo sito ha battuto 12 a 1 il mio... :grr: :grr:

Bene, dato che adoro migliorare i miei algoritmi sono andato nello specifico del secondo sorgente a cercare il segreto che custodisce...
Purtroppo la ricerca è stata vana, per questo mi rivolgo a voi.

Il mio codice [scritto in C#] inizia a verificare da 19, tutti i numeri dispari.
Li memorizza in una List
E utilizza quelli memorizzati per verificare i successivi. (controlla solo con i numeri primi).
Termina quindi il controllo del numero se supera la radice quadrata del numero da verificare.
Ho aggiunto in più un "pre-controllo" per escludere i divisori più bassi e più facilmente riconoscibili (2, 3, 5, 7, 9, 11, 13, 17)

Codice sorgente - presumibilmente VB.NET

  1. List<UInt64> primi = new List<UInt64>(Load());
  2.  
  3.             do
  4.             {
  5.                 while (!Console.KeyAvailable)
  6.                 {
  7.                     num += 2;
  8.  
  9.                     P = true;
  10.                     stop = ((UInt64)Math.Sqrt(num));
  11.  
  12.                     if (!LastIsFive(num))
  13.                         if (Sommacifre(num) % 3 != 0)
  14.                             if (ScomponiSette(num) % 7 != 0)
  15.                                 if (ScomponiUndici(num) % 11 != 0)
  16.                                     if (ScomponiTredici(num) % 13 != 0)
  17.                                         if (ScomponiDiciassette(num) % 17 != 0)
  18.                                             foreach (UInt64 Primo in primi)
  19.                                             {
  20.                                                 if ((num % Primo) == 0) { P = false; break; }
  21.                                                 if (Primo >= stop) { break; }
  22.                                             }
  23.                                         else P = false;
  24.                                     else P = false;
  25.                                 else P = false;
  26.                             else P = false;
  27.                         else P = false;
  28.                     else P = false;
  29.  
  30.                     if (P)
  31.                     {
  32.                         primi.Add(num);
  33.                         Console.WriteLine(num);
  34.                         SW.WriteLine(num);
  35.                     }


(riporto solo la parte di codice essenziale)

L'altro codice invece [scritto in C] verifica ogni numero (pari compresi),
verifica ogni divisore (numeri non primi compresi)
e anche questo termina il calcolo al raggiungimento della radice quadrata del numero da verificare...

Io non credo che una differenza così grande sia dovuta al linguaggio usato (C# e C)
Forse c'è qualcosa che rallenta molto l'esecuzione del mio, ma non saprei dire cosa...

Secondo voi cosa può essere la causa della differenza?

Grazie :D

PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 15:50
Mercoledì, 27/11/2013
Stai eseguendo il tuo programma in modalita' Release invece di Debug?


Il mio blog: https://piero.dev
PM Quote
Avatar
Fharamir (Normal User)
Rookie


Messaggi: 21
Iscritto: 06/05/2011

Segnala al moderatore
Postato alle 16:06
Mercoledì, 27/11/2013
Si, sto eseguendo il mio direttamente dall'exe compilato senza passare per il compilatore.

PM Quote
Avatar
HeDo (Founder Member)
Guru^2


Messaggi: 2765
Iscritto: 21/09/2007

Segnala al moderatore
Postato alle 16:45
Mercoledì, 27/11/2013
Secondo me il problema sta in tutte quelle funzioncine Scomponi* et simila.
Posta quel codice :)

Ultima modifica effettuata da pierotofy il 27/11/2013 alle 17:11
PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 17:11
Mercoledì, 27/11/2013
Testo quotato

Postato originariamente da Fharamir:

Si, sto eseguendo il mio direttamente dall'exe compilato senza passare per il compilatore.



:noway: non c'entra da dove lo stai eseguendo, hai compilato in modalita' release?


Il mio blog: https://piero.dev
PM Quote
Avatar
Fharamir (Normal User)
Rookie


Messaggi: 21
Iscritto: 06/05/2011

Segnala al moderatore
Postato alle 17:47
Mercoledì, 27/11/2013
Queste sono gli "scomponi" :D

Codice sorgente - presumibilmente VB.NET

  1. static Boolean LastIsFive(UInt64 num)
  2.         {
  3.             string n = num.ToString();
  4.             if (((short)n[n.Length - 1] - 48) == 5)
  5.                 return true;
  6.  
  7.             return false;
  8.         }
  9.  
  10.         static UInt64 Sommacifre(UInt64 num)
  11.         {
  12.             string n = num.ToString();
  13.  
  14.             if (n.Length == 1) return num;
  15.             UInt64 total = 0;
  16.  
  17.             for (int x = 0; x < n.Length; x++)
  18.                 total += (UInt64)n[x] - 48;
  19.  
  20.             return Sommacifre(total);
  21.         }
  22.  
  23.         static UInt64 ScomponiSette(UInt64 num)
  24.         {
  25.             string n = num.ToString();
  26.  
  27.             if (n.Length <= 2) return num;
  28.  
  29.             UInt64 Unit = (UInt64)n[n.Length - 1] - 48;
  30.             UInt64 Numero = Convert.ToUInt64(n.Substring(0, n.Length - 1));
  31.  
  32.             if (Numero < (Unit * 2)) return ScomponiSette((Unit * 2) - Numero);
  33.             return ScomponiSette(Numero - (Unit*2));
  34.         }
  35.  
  36.         static UInt64 ScomponiUndici(UInt64 num)
  37.         {
  38.             string n = num.ToString();
  39.  
  40.             if (n.Length <= 2) return num;
  41.  
  42.             UInt64 A = 0;
  43.             for (int x = 0; x < n.Length; x += 2)
  44.                 A += (UInt64)n[x] - 48;
  45.  
  46.             UInt64 B = 0;
  47.             for (int x = 1; x < n.Length; x += 2)
  48.                 B += (UInt64)n[x] - 48;
  49.  
  50.             if (A > B)
  51.                 return A - B;
  52.             return B - A;
  53.         }
  54.  
  55.         static UInt64 ScomponiTredici(UInt64 num)
  56.         {
  57.             string n = num.ToString();
  58.  
  59.             if (n.Length <= 2) return num;
  60.  
  61.             UInt64 Unit = (UInt64)n[n.Length - 1] - 48;
  62.             UInt64 Numero = Convert.ToUInt64(n.Substring(0, n.Length - 1));
  63.  
  64.             return ScomponiTredici(Numero + (Unit * 4));
  65.         }
  66.  
  67.         static UInt64 ScomponiDiciassette(UInt64 num)
  68.         {
  69.             string n = num.ToString();
  70.  
  71.             if (n.Length <= 2) return num;
  72.  
  73.             UInt64 Unit = (UInt64)n[n.Length - 1] - 48;
  74.             UInt64 Numero = Convert.ToUInt64(n.Substring(0, n.Length - 1));
  75.  
  76.             if (Numero < (Unit * 5)) return ScomponiDiciassette((Unit * 5) - Numero);
  77.             return ScomponiDiciassette(Numero - (Unit * 5));
  78.         }



mmh... allora non ho capito cosa intendi per "compilato in modalita' release" ...

PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 18:27
Mercoledì, 27/11/2013


Il mio blog: https://piero.dev
PM Quote
Avatar
nessuno (Normal User)
Guru^2


Messaggi: 6379
Iscritto: 03/01/2010

Segnala al moderatore
Postato alle 19:59
Mercoledì, 27/11/2013
Ammesso e non concesso che il codice che hai scritto abbia un senso, è ovvio che sia lentissimo rispetto ad una normale implementazione di un Crivello di Eratostene ... che domanda è ?

Cerca di capire come si scrive effettivamente un programma del genere senza inventare strani meccanismi e chiederti perché questi sono lenti ...

Qualcosa del genere ...

Codice sorgente - presumibilmente C++

  1. UInt64 i, j, n=1000;
  2.             UInt64 [] a = new UInt64[n];
  3.            
  4.             for (i = 2; i<n-1; i++)
  5.                 a[i] = 1;
  6.  
  7.             for (i = 2; i < n - 1; i++)
  8.                 if (a[i]>0)
  9.                     for (j = i; (j * i) < n; j++)
  10.                         a[i*j] = 0;
  11.  
  12.             for (i = 2; i<n-1; i++)
  13.                 if (a[i]>0)
  14.                     Console.Write(i + " ");



è sufficiente ... al posto di quelle millemila linee ...

Ultima modifica effettuata da nessuno il 27/11/2013 alle 20:11


Ricorda che nessuno è obbligato a risponderti e che nessuno è perfetto ...
---
Il grande studioso italiano Bruno de Finetti (uno dei padri fondatori del moderno Calcolo delle probabilità) chiamava il gioco del Lotto Tassa sulla stupidità.
PM Quote
Avatar
GN (Member)
Guru


Messaggi: 772
Iscritto: 30/04/2011

Segnala al moderatore
Postato alle 20:10
Mercoledì, 27/11/2013
Testo quotato

Postato originariamente da Fharamir:

Si, sto eseguendo il mio direttamente dall'exe compilato senza passare per il compilatore.


Detta così sembra che modifichi il codice e poi lanci l'exe senza riicompilare... ma non è così vero?

PM Quote
Pagine: [ 1 2 3 4 ] Precedente | Prossimo