Newsgroup: it.comp.appl.access
Titolo: Numeri Primi

Per chi avesse scritto una qualsiasi routine per il calcolo dei numeri 
primi sarei interessato a sapere i tempi di risposta per i seguenti
valori (numero primi da trovare, segnalo i miei tempi su Acer Aspire 
9112 - Intel Core Duo, 1.66GHz, 2Mb Ram)
1000 = <1sec
5000 = 4Sec
10000 = 15sec
15000 = 32sec
P.S. mi va bene anche se la routine non e' scritta in VBA.
-- 
ac (x=y-1)


wrote:

Ciao Alessandro.
Purtroppo devi dire come hai fatto il test, ti spiego la mia
domanda...!
Ho fatto 2 prove:
Function getPrimi()
    Dim sn  As Single
    Dim x   As Long
    sn = Timer
    For x = 1 To Totale
        Debug.print x & "è primo = ? " & Call IsPrime(x)
    Next
    Debug.Print Timer - sn
End Function
Questa su Totale=1000 impiega 1,4secondi...
Se ometto il Debug.Print invece impiega
 0,015625
ed impiega solo  0,0078125 su Totale=10000 ...
Quindi rispondere è poco serio... fammi capire meglio come fai il
ciclo in modo che paragoniamo effettivamente
la Routine che io ho chiamato IsPrime(...)
Ciao
@Alex


Intendevo che la 2° prova è questa:
Function getPrimi()
    Dim sn  As Single
    Dim x   As Long
    sn = Timer
    For x = 1 To Totale
         Call IsPrime(x)
    Next
    Debug.Print Timer - sn
End Function
La funzione è scritta in VBA.
@Alex

 ha scritto nel messaggio 
news:5N6Qo.16602$7b4....@tornado.fastwebnet.it...

Con il debug 0,32 per 10000 numeri.
Questo il codice usato tratto da Francesco Balena e modificando quello di 
Alex:
Function IsPrime(ByVal number As Long) As Boolean
    'di Francesco Balena
    ' manually test 2 and 3
    If number > 3 Then
        If number Mod 2 = 0 Then Exit Function
        If number Mod 3 = 0 Then Exit Function
    End If
    ' we can now avoid to consider multiples
    ' of 2 and 3. This can be done really simply
    ' by starting at 5 and incrementing by 2 and 4
    ' alternatively, that is:
    '    5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, ...
    Dim divisor As Long
    Dim increment As Long
    Dim maxDivisor As Long
    divisor = 5
    increment = 2
    ' we don't need to go higher than the square
    ' root of the number
    maxDivisor = Sqr(number) + 1
    Do Until divisor > maxDivisor
        If number Mod divisor = 0 Then Exit Function
        divisor = divisor + increment
        ' this modifies 2 into 4 and viceversa
        increment = 6 - increment
    Loop
    ' if we get here, the number is prime
    IsPrime = True
End Function
Function getPrimi(Totale As Long)
    Dim sn  As Single
    Dim x   As Long
    sn = Timer
    For x = 1 To Totale
         If IsPrime(x) = True Then
         Debug.Print x & " NP"
         End If
    Next
    Debug.Print Timer - sn
End Function
Ciao, Carlo 


Pero' col debug, quello che porta via e' lo scorrimento della finestra coi 
dati di debug
Piu alta e' e maggiore e' il tempo necessario
Nel mio caso (Athlon X2  3 GHz) varia da  0,625 con una riga visibile a 1,67 
con una cinquantina di righe visibili
Prove ripetute piu volte
Senza debug per vedere qualcosa sul tempo bisogna andare sui 10M come 
parametro routine
Ciao
RobertoA


Infatti è quello che sostenevo... tuttavia se si dice che il Test si
fà con il DEBUG tutti lo si fà uguale... e le differenze
sono, a parità di codice imputabili alle prestazioni della macchina,
per codici diversi invece su ottimizzazioni di codice...!
Sotto posto la routine che uso io, non mia scaricata dal WEB qualche
tempo addietro... non sò dove.
Test eseguito su 10000 cicli con il codice di Carlo, quindi con il
Debug.Print...
Il mio PC è una ciofeca:
Intel(R) Core(TM)2 Duo CPU P7450 @ 2.13GHz
Memoria (RAM) 4,00 GB
Scheda video ATI Mobility Radeon HD 4650
Punteggio di W7 5,7, ma non credo serva a nulla...
RISULTATI:
Routine(Sotto)          2,484375
Routine(Carlo)   2,453125
Public Function IsPrime1(ByVal n As Long) As Boolean
   Dim r As Long
   Select Case n
      Case Is < 1: Err.Raise 5, "IsPrimeX", "IsPrimeX: argomento
errato !"
      Case 1: ' niente, non e' primo !
      Case 2, 3: IsPrime1 = True
      Case Else
         r = n Mod 6
         If r = 1 Or r = 5 Then  ' se n Mod 6 e' diverso da 1 o 5 il
numero NON e' primo.
            For r = 3 To Sqr(n) Step 2   ' controllo tutti i divisori
dispari...
               If (n Mod r) = 0 Then Exit Function
            Next
            IsPrime1 = True
         End If
   End Select
End Function
@Alex

 @Alex
Intanto Buon Anno (tra l'altro 2011 e' primo).
Scusami per il ritardo nella risposta  (avevo da fare con la congettura 
di Goldbach).
Guardando anche gli interventi di Carlo C. e RobertoA mi e' venuto il 
dubbio che non sono stato chiaro quando parlo di 10.000 intendo 10.000 
numeri primi e quindi il 104743.
E poi la debug e' d'obbligo poiche' io li scrivo in una tabella  log e 
tale scrittura e' anche piu pesante del debug print.
Tra l'altro uso la semplice formula che prende in esame i dispari e non 
la leggermente piu' sofisticata che va sotto il nome di 6n+/- 1
-- 
ac (x=y-1)

 Alex:
Ciao Carlo, buon anno.
Grazie per l'intervento ma su 10000 numeri la valutazione del tempo e' 
molto imprecisa (gatto di Schrödinger?). Tra l'altro la formula 
generalmente usata (Balena la fa intuire nelle note alla routine) e' 
prendere i valori di 6n+/- 1 che sono le coppie *primo candidato*
-- 
ac (x=y-1)


Ciao RobertoA, buon anno.
Come vedi dalle mie risposte a Carl e Alessandro forse non mi sono 
spiegato bene. I miei valori si riferivano a numeri primi trovati
-- 
ac (x=y-1)

Il 02/01/2011 11.30, Alessandro Cara ha scritto:
Chiedo perdono, non *Carl* ma *Carlo*
-- 
ac (x=y-1)


wrote:

Beh posta il codice.... ed anche i risultati... anno nuovo Alessandro
vecchio...!!
;-)
@Alex

 ac (x=y-1)
Certo č meglio postare il codice che hai usato.
Con questi valori (104743) e con il debug ottengo:
3,53125 secondi
Ma, udite udite, utilizzando il recordset, cioč accodando i risultati ad una 
tabella, questo č il risultato in secondi:
0,140
Questa la funzione modificata:
Function getPrimi(Totale As Long)
    Dim sn  As Single
    Dim x   As Long
    Dim Tbl As Recordset
    Set Tbl = CurrentDb.OpenRecordset("TblNumeriPrimi") '(tabella con 
contatore ID, chiave primaria e NP, numerico)
    sn = Timer
    For x = 1 To Totale
         If IsPrime(x) = True Then
         With Tbl
         .AddNew
         !NP = x
         Tbl.Update
        End With
         'Debug.Print x & " NP"
         End If
    Next
    Debug.Print Timer - sn
End Function
Ciao, Carlo 

 ha scritto nel messaggio 
news:srYTo.20184$7b4....@tornado.fastwebnet.it...

Sì.
Ti ho postato una variante con il recordset e ti assicuro che i tempi sono 
quelli, meno di un secondo.
Non faccio in tempo a dare invio che i dati sono già tutti accodati e questo 
proprio visivamente a prescindere dal valore di timer.
Ciao, Carlo 

 Questa la funzione modificata:
Quello non e' un problema ma e proprio quello che mi interessa vedere e 
quindi "rivelare" il codice e' l'ultima cosa che si deve fare.
Come vedi alcuni risultati sorprendenti tipo che l'aggiunta a recordset 
e' piu' veloce della debug e' un dato importante.
Io non cercavo particolari prestazioni e faccio una insert (piu' lenta 
della addnew) ma per blocchi di numeri, scrivo stringhe di 210 caratteri)
Nel frattempo aggiungendo semplicemente il controllo sulla radice 
quadrata per 20.000 primi i tempi sono passati a due secondi circa
-- 
ac (x=y-1)

 @Alex
-- 
ac (x=y-1)



Ma no... chi se ne frega ... solo che se posti il tuo codice lo provo
al volo, in modo da darti un'equivalenza di efficienza in termini
relativi di paragone... se devo scrivermi il tuo algoritmo ...
ciccia... ti arrangi... ;-)
Buon Anno.
@Alex