Autore Topic: Crivello di Eratostene  (Letto 2792 volte)

Offline Top Fuel

  • Gran Maestro dei Gamberi
  • *****
  • Post: 959
    • Mostra profilo
Crivello di Eratostene
« il: 04 Ottobre 2016, 23:38:36 »
Semplice implementazione del Crivello di Eratostene per la ricerca dei numeri primi.
Se non sapete cosa è cercate su Wikipedia che non ho voglia di spiegarlo. :P
Ditemi che ne pensate. :)
« Ultima modifica: 05 Ottobre 2016, 00:38:40 da Top Fuel »
Dear youtube administrators, your search bar is broken. When I type the letter "J" it appears justin bieber when it should appear Jimi Hendrix. Fix this, please.

Offline vuott

  • Moderatore globale
  • Senatore Gambero
  • *****
  • Post: 11.723
  • Ne mors quidem nos iunget
    • Mostra profilo
Re:Crivello di Eratostene
« Risposta #1 il: 05 Ottobre 2016, 00:25:09 »
...non ho voglia di spiegarlo. :P
E su, dai, un piccolo sforzo !    :-\






« Ultima modifica: 05 Ottobre 2016, 00:29:56 da vuott »
« Chiunque, non ricorrendo lo stato di necessità, nel proprio progetto Gambas fa uso delle istruzioni Shell o Exec, è punito con la sanzione pecuniaria da euro 20,00 a euro 60,00. »

Offline Top Fuel

  • Gran Maestro dei Gamberi
  • *****
  • Post: 959
    • Mostra profilo
Re:Crivello di Eratostene
« Risposta #2 il: 05 Ottobre 2016, 00:39:07 »
E' tardi, ho sonno. :)
Dear youtube administrators, your search bar is broken. When I type the letter "J" it appears justin bieber when it should appear Jimi Hendrix. Fix this, please.

Offline Gianluigi

  • Moderatore globale
  • Senatore Gambero
  • *****
  • Post: 4.244
  • Tonno verde
    • Mostra profilo
Re:Crivello di Eratostene
« Risposta #3 il: 05 Ottobre 2016, 13:57:23 »
Dovresti cambiare così l'ultimo passaggio altrimenti scrive anche 1:
Codice: [Seleziona]
For j = 1 To limite
  If serie[j] > 1 Then ListaNumeri.Add(Str$(serie[j])) 'scrive i numeri primi rimasti nella Listbox
Next

 :ciao:
nuoto in attesa del bacio di una principessa che mi trasformi in un gambero azzurro

Offline Top Fuel

  • Gran Maestro dei Gamberi
  • *****
  • Post: 959
    • Mostra profilo
Re:Crivello di Eratostene
« Risposta #4 il: 05 Ottobre 2016, 21:46:17 »
Beh, piccolezze... :)
Dear youtube administrators, your search bar is broken. When I type the letter "J" it appears justin bieber when it should appear Jimi Hendrix. Fix this, please.

Offline Gianluigi

  • Moderatore globale
  • Senatore Gambero
  • *****
  • Post: 4.244
  • Tonno verde
    • Mostra profilo
Re:Crivello di Eratostene
« Risposta #5 il: 05 Ottobre 2016, 21:57:55 »
nuoto in attesa del bacio di una principessa che mi trasformi in un gambero azzurro

Offline vuott

  • Moderatore globale
  • Senatore Gambero
  • *****
  • Post: 11.723
  • Ne mors quidem nos iunget
    • Mostra profilo
Re:Crivello di Eratostene
« Risposta #6 il: 05 Ottobre 2016, 22:20:35 »


     
« Chiunque, non ricorrendo lo stato di necessità, nel proprio progetto Gambas fa uso delle istruzioni Shell o Exec, è punito con la sanzione pecuniaria da euro 20,00 a euro 60,00. »

Offline vuott

  • Moderatore globale
  • Senatore Gambero
  • *****
  • Post: 11.723
  • Ne mors quidem nos iunget
    • Mostra profilo
Re:Crivello di Eratostene
« Risposta #7 il: 07 Ottobre 2016, 16:54:30 »
All'interno del suo programma Top Fuel giustamente avverte che "sui numeri grossi (sopra il milione) il programma ci metterà parecchio".

Confrontiamo, dunque, per mera curiosità le prestazioni di Gambas con quelle di un codice scritto in C, trasformato in libreria dinamica .so richiamata successivamente in un programma Gambas.

Utilizzate un valore, ad esempio, di 10000000 (diecimilioni) per entrambe le prove - con il codice Gambas (quello già disponibile di Top Fuel) e con il codice C della libreria esterna .so - e verificate il tempo impiegato da ciascuno dei due programmi nel rispettivo processo dei dati.

Il programma Gambas che utilizzerà il codice C puro, sarà il seguente:
Codice: [Seleziona]
Private Extern Eratostene_C(limes As Integer) As Integer In "/tmp/crivello"


Public Sub Main()

Dim limite, i As Integer

 limite = 10000000

' Crea l'apposita libreria dinamica .so esterna:
  Creaso()
 
' Invoca la funzione esterna della libreria dinamica .so:
  i = Eratostene_C(limite)
  If i < 0 Then Error.Raise("Memoria insufficiente !")

End


Private Procedure Creaso()
 
  File.Save("/tmp/crivello.c", "#include <stdio.h>\n"
                               "#include <stdlib.h>\n" &
                               "#include <string.h>\n" &
                               "#include <math.h>\n\n" &
                               "int Eratostene_C(int limes) {\n\n" &
                               "   int lim, dim, i, j, z;\n" &
                               "   int *list;" &
                               "\n\n" &
                               "   dim = (limes / 2 + 1);\n" &
                               "   if((list = (int *)calloc(sizeof(int), dim)) == NULL)\n" &
                               "   return -1;\n\n" &
                               "   for(i=0; i<dim; i++)\n" &
                               "   list[i]=0;\n\n" &
                               "   printf(\"2 \");\n\n" &
                               "   lim = (int)sqrt(limes);\n\n" &
                               "   for(j=1,i=3; i<=lim; ++j,i+=2) {\n" &
                               "     if(!list[j]) {\n" &
                               "       for(z=j+i; z<dim; z+=i)\n" &
                               "         list[z] = -1;\n" &
                               "       printf(\"%d \", i);\n" &
                               "     }\n   }\n\n" &
                               "   for(; i<limes; i+=2, ++j)\n" &
                               "     if(!list[j])\n" &
                               "       printf(\"%d \", i);\n\n" &
                               "   return 0;\n\n}")
                         
  Shell "gcc -o /tmp/crivello.so /tmp/crivello.c -shared -fPIC -lm" Wait
 
End


   :-X
« Chiunque, non ricorrendo lo stato di necessità, nel proprio progetto Gambas fa uso delle istruzioni Shell o Exec, è punito con la sanzione pecuniaria da euro 20,00 a euro 60,00. »

Offline Gianluigi

  • Moderatore globale
  • Senatore Gambero
  • *****
  • Post: 4.244
  • Tonno verde
    • Mostra profilo
Re:Crivello di Eratostene
« Risposta #8 il: 07 Ottobre 2016, 17:14:16 »
Intanto tu non usi la grafica, poi occorrerebbe vedere se il codice scritto da Top Fuel è efficiente o si possa migliorare magari usando anche FAST.
 :ciao: :ciao:
nuoto in attesa del bacio di una principessa che mi trasformi in un gambero azzurro

Offline vuott

  • Moderatore globale
  • Senatore Gambero
  • *****
  • Post: 11.723
  • Ne mors quidem nos iunget
    • Mostra profilo
Re:Crivello di Eratostene
« Risposta #9 il: 07 Ottobre 2016, 17:31:36 »
Intanto tu non usi la grafica, poi occorrerebbe vedere se il codice scritto da Top Fuel è efficiente o si possa migliorare magari usando anche FAST.


Passi dal crivello al cavillo !

Ad ogni modo, in applicazione a riga di comando + Fast siamo quasi ai tempi del C.
« Chiunque, non ricorrendo lo stato di necessità, nel proprio progetto Gambas fa uso delle istruzioni Shell o Exec, è punito con la sanzione pecuniaria da euro 20,00 a euro 60,00. »

Offline Gianluigi

  • Moderatore globale
  • Senatore Gambero
  • *****
  • Post: 4.244
  • Tonno verde
    • Mostra profilo
Re:Crivello di Eratostene
« Risposta #10 il: 07 Ottobre 2016, 17:45:02 »

Passi dal crivello al cavillo !

 :D
Citazione
Ad ogni modo, in applicazione a riga di comando + Fast siamo quasi ai tempi del C.

Evvai! Evvieni! Gambas è una forza  :D :D

 :ciao: :ciao:
nuoto in attesa del bacio di una principessa che mi trasformi in un gambero azzurro

Offline vuott

  • Moderatore globale
  • Senatore Gambero
  • *****
  • Post: 11.723
  • Ne mors quidem nos iunget
    • Mostra profilo
Re:Crivello di Eratostene
« Risposta #11 il: 07 Ottobre 2016, 18:08:16 »
...questo però con valori bassi.
Se, invece, inserisco cinquencentomilioni il tempo impiegato dal C rispetto al codice Gambas è di quasi un terzo.

Inoltre volendo provare con seicentomilioni, con Gambas mi da errore di memoria esaurita :-X ; invece con la libreria esterna in C ho potuto gestire anche centomiliardi    (non ho provato oltre) !
« Ultima modifica: 08 Ottobre 2016, 00:49:21 da vuott »
« Chiunque, non ricorrendo lo stato di necessità, nel proprio progetto Gambas fa uso delle istruzioni Shell o Exec, è punito con la sanzione pecuniaria da euro 20,00 a euro 60,00. »

Offline Top Fuel

  • Gran Maestro dei Gamberi
  • *****
  • Post: 959
    • Mostra profilo
Re:Crivello di Eratostene
« Risposta #12 il: 08 Ottobre 2016, 00:27:10 »
Il mio programma era solo un piccolo esercizio, buono a scopo didattico volendo, dopo aver trovato per caso su Wikipedia questa cosa del crivello di Eratostene. :)
Se poi è venuta fuori una base di confronto e magari di miglioramento, ben venga la cosa.
Prova a parlarne sulla Mailing List, sentiamo che ti dicono. :)
« Ultima modifica: 08 Ottobre 2016, 00:28:34 da Top Fuel »
Dear youtube administrators, your search bar is broken. When I type the letter "J" it appears justin bieber when it should appear Jimi Hendrix. Fix this, please.

Offline vuott

  • Moderatore globale
  • Senatore Gambero
  • *****
  • Post: 11.723
  • Ne mors quidem nos iunget
    • Mostra profilo
Re:Crivello di Eratostene
« Risposta #13 il: 08 Ottobre 2016, 00:46:44 »
Prova a parlarne sulla Mailing List, sentiamo che ti dicono.
Non ho messo in discussone il tuo codice, il quale appare essenziale, coinciso.
Ho solo fatto un mero test sui due linguaggi; nulla di più.
« Chiunque, non ricorrendo lo stato di necessità, nel proprio progetto Gambas fa uso delle istruzioni Shell o Exec, è punito con la sanzione pecuniaria da euro 20,00 a euro 60,00. »

Offline Gianluigi

  • Moderatore globale
  • Senatore Gambero
  • *****
  • Post: 4.244
  • Tonno verde
    • Mostra profilo
Re:Crivello di Eratostene
« Risposta #14 il: 08 Ottobre 2016, 17:27:20 »
Il mio programma era solo un piccolo esercizio, buono a scopo didattico volendo, dopo aver trovato per caso su Wikipedia questa cosa del crivello di Eratostene. :)
Se poi è venuta fuori una base di confronto e magari di miglioramento, ben venga la cosa.
Prova a parlarne sulla Mailing List, sentiamo che ti dicono. :)
Giusto quello che dice vuott, ma si può anche discutere e provare a vedere come mai Gambas esaurisce la memoria a 600 milioni.
Sul mio computer ad esempio il codice di Top Fuel la esaurisce a 300 sempre milioni.
Lascio volentieri indagare Top Fuel sul suo codice.  :P :P
Io mi sono spremuto per farlo diversamente (prendendo spunto da un articolo su internet) e pur avendo partorito il codice meno veloce (risultati su 100 milioni):
Codice: [Seleziona]
Vuott     22550,8399009705 msec / 22620,2738285065 msec
Top Fuel  36794,9628829956 msec / 36589,7300243378 msec
Gianluigi 41717,2560691833 msec / 41830,934047699 msec
sono arrivato a 2 miliardi (su 3 mi da out of bound e non memoria esaurita) anche se nell'attesa del risultato ho schiacciato un sonnellino  ;D
Allego Codice foto documentale
Nota: Se non erro il codice di Vuott non fa uso di vettori e questo potrebbe spiegare il fatto che è veloce il doppio.

Codice: [Seleziona]
' Gambas module file

Fast

Public Sub Main()

  Setaccio(100000000)

End
Private Sub Setaccio(n As Long)
 
  Dim v As New Boolean[n + 1]
  Dim l, j, i As Long 
  Dim StartTime As Float
  Dim DiffTime As Float
 
  StartTime = Timer
  l = Int(Sqr(n) + 1) 
  For i = 2 To l
    For j = i * i To n Step i     
      v[j] = True     
    Next
  Next
  For i = 2 To n
    If v[i] = False Then
      Print i
    Endif
  Next
  DiffTime = Timer - StartTime
  Print "Setaccio ", DiffTime * 1000; " msec"
 
End
:ciao: :ciao: :ciao:
« Ultima modifica: 08 Ottobre 2016, 17:32:38 da Gianluigi »
nuoto in attesa del bacio di una principessa che mi trasformi in un gambero azzurro