programma c++

[lucianorossi]

devo fare un proggy per calcolare i numeri primi per la scuola
Ho fatto una prima bozza in turbopascal
processo i primi 10000 numeri in 12 secondi [p4 1560mhz]
l'ho ribattuto in C++
l'ho migliorato più che ho potuto
250000 numeri processati in 12 secondi [solito proc]
ora però ho un problema: come andare oltre 250000 numeri?
perchè li devo memorizzare in un'array, ma non posso mandarlo oltre 250000 perchè se no il programma non parte, e non posso nemmeno fare una array doppio indice, perchè non parte lo stesso.
C'è un limite alla memoria utilizzaa? si può aumentare?
Uso Visual C++

Allego il programma

[lucianorossi]

eccolo

[a2000]

(un milione) di numeri processat
PII 350 MHz[/siz]
interpretato n VBA

tempo di calcolo 0.88 secondi[/siz] :cool:

Interessa ? :)

[misterx]

Originally posted by "a2000"

(un milione) di numeri processat
PII 350 MHz[/siz]
interpretato n VBA

tempo di calcolo 0.88 secondi[/siz] :cool:

Interessa ? :)


impossibile; tempo troppo basso ;)

[lucianorossi]

un milione in 1minuto e 7 secondi, per ora...

[lucianorossi]

è meglio fare un programma lungo che però faccia meno operazioni aritmetiche possibile o meglio farlo più corto e fargli fare un po' più di operazioni aritmetiche?

[misterx]

magari vedendo il sorgente in C++ si potrebbe capire qualcosa in più :)

[/\/\@®¢Ø]

Originally posted by "lucianorossi"

è meglio fare un programma lungo che però faccia meno operazioni aritmetiche possibile o meglio farlo più corto e fargli fare un po' più di operazioni aritmetiche?
Non e' possibile dire se sia meglio l'una o l'altra, dipende anche da quante volte ripeti le stesse operazioni. Piu' che contare le operazioni in questi casi e' meglio cercare l'algoritmo piu' adatto. Probabilmente il migliore e' la trivella di Eratostene (si chiama cosi' ? :confused: ), che suppongo sia la stessa tecnica che ha utilizzato a2000 (anzi, a onor del vero di questo argomento si era gia' parlato tempo fa, e mi sembra ne avesse accennato per primo lui)
L'idea e' abbastanza semplice: tieni una tabella di valori booleani che indichi se un numero e' primo o no. All'inizio tutti i valori della tabella sono veri, e man mano 'togli' tutti i multipli (per prima cosa togli i multipli di 2 poi quelli di 3 ... ).
Non dovrebbe risultare molto codice, 20 linee di codice basteranno.

[/\/\@®¢Ø]

Originally posted by "misterx"




impossibile; tempo troppo basso ;)
No, mi sembra piu' che ragionevole ;)

[a2000]

Originally posted by "/\/\@®¢Ø"


No, mi sembra piu' che ragionevole ;)

ohhh /\/\@®¢Ø !

"almeno tu nell'universooooo ...." :o :o :o

[lucianorossi]

grazie tante, questo è il primo programma che ho ideato, e girava benissimo, solo che non potevo fare un array di + di 250000 valori, e a me serve per trovare valori fra 2^128 e 2^129
C'è un metodo per fare un array di 2^129 valori?

Attualmente il codice è molto ingarbugliato, ora lo posto ma non so se ci capirete qualcosa :D

[lucianorossi]

#include <stdio.h>

void main()

{
unsigned long int a, b, c, d, e, f, h;
unsigned long int numerip[250000];
bool primo;
FILE *fw;
printf("Prime_Numbers v0.7.0.3 build 35 \n");
printf("Totalmente programmato da Giorgio Busoni \n");
printf("L''intevallo di numeri nel quale vuoi cercare i numeri primi \n");
printf("Digita la cifra di fine intervallo (massima) \n");
scanf("%d", &b);
printf(&"Please wait \n");
a=1;
fw = fopen("Primenumbers.txt","w");
c=a; /*copia a in un'altra variabile per non sovrascrivere il valore originario di a*/
if (b<=2)
{
printf("Il numero deve essere maggiore di 2 \n");
}
else
{
h=1;
numerip[2]=2;
while(c<b){
if(c>=250000)
{
break;
}
d=3;
e=c/2;
primo=true; /*il numero viene classificato come primo*/
while(numerip[d]<=e){
f= c % numerip[d]; /*resto delle divisione del numero per d (variabile che va da 2 a c-1)*/
numerip[h]=0;
if (f==0) /*se il resto=0...*/
{
primo=false; /*e viene anche memorizzato nella variabile temporanea*/
break;
}
d=d+1; /*si aumenta i divisore di 1 prima di ripetere l'operazione*/
}
if (primo==true) /*se alla fine del clico il numero non ha mai dato resto 0 in una divisione*/
{
numerip[h]=c; /*e il numero viene elencato nell'array come primo*/
if (numerip[h]==1)
{
numerip[h]=2;
}
fprintf(fw,"%d, " , numerip[h]);
h=h+1;
}
c=c+2; /*si passa al numero successivo prima di ripetere il ciclo*/
printf("Ready %d % \r", ((c*100)/(a*b)));
}
while(c<b){
if(c>5000000000)
{
break;
}
d=3;
e=c/2;
primo=true; /*il numero viene classificato come primo*/
while(numerip[d]<=e){
if (numerip[d]==0)
{
break;
}
f= c % numerip[d]; /*resto delle divisione del numero per d (variabile che va da 2 a c-1)*/
if (f==0) /*se il resto=0...*/
{
primo=false; /*e viene anche memorizzato nella variabile temporanea*/
break;
}
d=d+1; /*si aumenta i divisore di 1 prima di ripetere l'operazione*/
}
if (primo==true) /*se alla fine del clico il numero non ha mai dato resto 0 in una divisione*/
{
fprintf(fw,"%d, " , c);
}
c=c+2; /*si passa al numero successivo prima di ripetere il ciclo*/
if(c<b)
{
printf("Ready %d % \r", ((c*100)/(b)));
}
}
numerip[1]=2;
printf("Ricerca numeri primi completata");
}
}

[a2000]

Originally posted by "misterx"




impossibile; tempo troppo basso ;)

provare per credere.

interessa ?

[lucianorossi]

versione compilata e zippata aggiornata

[lucianorossi]

Originally posted by "a2000"



provare per credere.

interessa ?
si, se completo di codice

[a2000]

per ora il codice (12 righe). :)


Sub Primi()

Const iMax& = 250000000
Dim i As Long, j As Long
Dim aaa(1 To iMax) As Byte

For i = 2 To Sqr(iMax)
If aaa(i) = 0 Then
For j = 2 * i To iMax Step i
aaa(j) = 1
Next j
End If
Next i

End Sub

[a2000]

... adesso non ho tempo.

comunque, come sempre, l'algoritmo è TUTTO e ce ne sono tanti anche per intervalli numerici molto grandi.

ma la cosa divertente è comunque cimentarsi per trovare qualche soluzione personale e originale (ma semplice ed elegante).
con l'algoritmo del crivello di Eratostene naive il limite è la memoria di massa disponibile sulla macchina.
con qualche pensata sulla virtualizzazione del vettore aaa() e considerando che per valori di n molto grandi "quasi" tutti i numeri sono primi .... 2^129 non è poi così grande.

:)

[a2000]

comunque qualcosa bisogna saperla:

http://matematica.uni-bocconi.it/betti/AKS.htm

[lucianorossi]

cosa vuol dire dim?
che linguaggio è?
sul visual c++ non parte correttamente

[/\/\@®¢Ø]

In C++ puoi usare qualcosa del genere, per il calcolo e la stampa.

#include <iostream>
#include <cmath>
#include <vector>
int main()
{
unsigned long n = 1000000;
bool data[n];
fill( data , data + n , true );
data[0] = data[1] = false;
for ( unsigned long i=2 ; i < sqrt(n) ; ++i )
if ( data[i] )
{
unsigned long m = i*2;
do
{
data[m]=false;
m+=i;
}while( m < n );
}
for ( unsigned long i=0 ; i<n ; ++i )
if (data[i] )
cout << i << endl;
}

anche se cosi' come e' fatto non puoi arrivare a cifre dell'ordine del 2^128

[maxithron]

Originally posted by "lucianorossi"

cosa vuol dire dim?
che linguaggio è?
sul visual c++ non parte correttamente

è in Visual Basic.

[verloc]

+ lento ma senza limite.

[misterx]

Originally posted by "/\/\@®¢Ø"


No, mi sembra piu' che ragionevole ;)

se non manda in display nulla, come nel suo esempio sopra concordo: ma pensavo visualizzasse risultato per risultato; in questo caso di tempo ce ne vuole :)

[a2000]

beh, questo per esempio processa (tcalcolo = 2.36 second). :cool:

il tutto in con PIV 2.4GH. :D

se usiamo il cannone (Fortran) i tempi si dividono tranquillamente per 20. :)

[lombardp]

Ho tolto al tuo script l' IF, che da' fastidio alla pipeline del processore. Così si ottiene lo stesso comportamento, vengono fatti più calcoli, però non ci sono branch e la pipeline rimane carica.

Sulla mia macchina ho guadagnato un 2,6% sul tempo di esecuzione, ed è un PIII-600. Sarei curioso di sapere come cambia sul P4.


For i = 2 To Sqr(iMax)
For j = (2 * i + aaa(i) * iMax) To iMax Step i
aaa(j) = 1
Next j
Next i

[a2000]

ti piacciono gli IF calcolati ehh ... :D

sul PIV c'è un leggero peggioramento (ma non deterministico: una quindicina di task attivi).

comunque passando a vettori bit e puntatori ci si può divertire anche con Eratostene.

per numeri molto grandi (crittografia, non a caso a 128 bit ) bisogna passare ai "test di primalità" p.es. quello di Miller.

... anche se ...

[a2000]

per esempio delle belle mascherine bit per bit in OR overlay .... :

00000000000000000000000000000000000000000000000000000000000
10000001000000100000010000001 (7 p.es.)


lombardp ma ti piace o' presepe o no ? :D

[lombardp]

Originally posted by "a2000"

per esempio delle belle mascherine bit per bit in AND overlay .... :

00000000000000000000000000000000000000000000000000000000000
10000001000000100000010000001 (7 p.es.)

lombardp ma ti piace o' presepe o no ? :D

:D

Un'altra possibile ottimizzazione: dichiarare aaa come LONG. Questo dovrebbe evitare al processore (o a Windows forse) di dovere spacchettare i byte dalle word.

Sulla mia macchina si traduce in un ulteriore miglioramento del 27% ! ! !

[misterx]

Originally posted by "lombardp"



Ho tolto al tuo script l' IF, che da' fastidio alla pipeline del processore.




come fai ad asserire questo????? :)

[a2000]

Originally posted by "lombardp"



:D

Un'altra possibile ottimizzazione: dichiarare aaa come LONG. Questo dovrebbe evitare al processore (o a Windows forse) di dovere spacchettare i byte dalle word.

Sulla mia macchina si traduce in un ulteriore miglioramento del 27% ! ! !


PIV 2.4GHz (iMax = 1e7)
aaa() Byte -> 2.36 s
aaa() Integer -> 2.03 s
aaa() Long -> 2.25 s

ma lombardp, ripeto, ti piace o' presepe ?

(o sei rimasto alla [color=violet] nuda cruda ?) :p

[lombardp]

Originally posted by "misterx"


come fai ad asserire questo????? :)

Tutte le istruzioni di branch (tra cui gli IF) possono essere risolte solamente verso la fine della pipeline e questo potenzialmente può portare a dover annullare le esecuzioni in corso nella pipeline (svuotamento) per riprendere il corretto cammino di esecuzione.La soluzione che ho proposto elimina l'IF: prima il codice eseguito era diverso a seconda della condizione dell'IF, nella seconda soluzione rimane uguale; magari esegue più calcoli, ma la pipeline non dovrebbe bloccarsi.

Faccio un esempio:


// mettiamo che A possa essere 0 o 1

if (A==1) then C = C + 50;
else C = C + 30;


Io lo scriverei


C = C + 30 + A * 20;


Ho detto dovrebbe perché con la complessità dei processori e dei sistemi operativi moderni, spesso questi accorgimenti sono inutili se non controproducenti.

Le unità di "Branch Prediction" tendono a alleviare questo problema tentando di predirre la direzione che verrà presa nel branch, ma in questo caso (individuazione dei numeri primi) non possono essere efficaci. Detta in altro modo: se le unità di predizione dei salti riuscissero a predirre bene i branch dell'algoritmo dei numeri primi, allora sarebbero esse stesse un metodo deterministico iper-efficiente per l'individuazione dei numeri primi, cosa che attualmente non esiste.

[a2000]

Originally posted by "lombardp"



...
Ho detto dovrebbe perché con la complessità dei processori e dei sistemi operativi moderni, spesso questi accorgimenti sono inutili se non controproducenti.
....



infatti peggiora.

prima l'algoritmo, poi la struttura dati, poi la riduzione dei calcoli FP e poi la riduzione dei branch.

del presepe che mi dici ? ti è piaciuto ?

[a2000]

oh cazzo ho superato i mille post[/siz] ! :p

tanti auguri a tee :o :o :o :o :o :o
tanti auguri a teeee :o :o :o :o :o :o
tanti auguri feliciiiii :o :o :o
tanti auguri a2000 :o :o :o :o :o :o :o :o :o [/size]

grazie ragazzi !

[/\/\@®¢Ø]

Originally posted by "verloc"

+ lento ma senza limite.
Basta utilizzare una classe per "big integers" in C++.
In VB non ho idea se di default gli interi siano limitati come in C o illimitati come in Python :confused:

[/\/\@®¢Ø]

[quote="a2000"]oh cazzo ho superato i mille post[/siz] ! :p
[quote]
Io invece tra un po' arrivero' a2000 :o :D

[a2000]

Originally posted by "/\/\@®¢Ø"


Basta utilizzare una classe per "big integers" in C++.
In VB non ho idea se di default gli interi siano limitati come in C o illimitati come in Python :confused:

illimitati as the Python between my legs ! :p

[a2000]

Originally posted by "/\/\@®¢Ø"


Io invece tra un po' arrivero' a2000 :o :D


:D
e io ti accoglierò a braccia aperte (e gambe chiuse: sai il Phyton non fa tanta differenza: "il buso è buso e il ca+o no ga oci") !
:D :D

[a2000]

Originally posted by "lombardp"



Un'altra possibile ottimizzazione:
...

Sulla mia macchina si traduce in un ulteriore miglioramento del 27% ! ! !

se muoviamo le truppe corazzate e gli effetti speciali altro che 27% (?), puoi cominciare a dividere in successione per i primi 10 numeri primi :cool:

vabbe' che "chiedere è lecito e rispondere è cortesia", ma non mi hai ancora detto cosa ne pensi del presepe :mad:

[a2000]

no c'è un Ca++o da fare con a2000 va sempre a finire tutto a pOTane ! :D :D

[lombardp]

Originally posted by "a2000"


vabbe' che "chiedere è lecito e rispondere è cortesia", ma non mi hai ancora detto cosa ne pensi del presepe :mad:

E' che non ho capito di che presepe parli? :confused:

[a2000]

questo (con il pastorello e la ghiaina che hai aggiunto) :)


Sub Primi()

Const iMax& = 250000000
Dim i As Long, j As Long
Dim aaa(1 To iMax) As Byte

For i = 2 To Sqr(iMax)
If aaa(i) = 0 Then
For j = 2 * i To iMax Step i
aaa(j) = 1
Next j
End If
Next i

End Sub


ma chi c'hai nell'avatar Bohr e ... Chiorboli :D

[lucianorossi]

non và :cry:
Compiling...
primenumber8.cpp
e:\programmi\microsoft visual studio\myprojects\n_primi\primenumber8.cpp(7) : error C2057: expected constant expression
e:\programmi\microsoft visual studio\myprojects\n_primi\primenumber8.cpp(7) : error C2466: cannot allocate an array of constant size 0
e:\programmi\microsoft visual studio\myprojects\n_primi\primenumber8.cpp(7) : error C2133: 'data' : unknown size
e:\programmi\microsoft visual studio\myprojects\n_primi\primenumber8.cpp(8) : error C2065: 'fill' : undeclared identifier
e:\programmi\microsoft visual studio\myprojects\n_primi\primenumber8.cpp(20) : error C2374: 'i' : redefinition; multiple initialization
e:\programmi\microsoft visual studio\myprojects\n_primi\primenumber8.cpp(10) : see declaration of 'i'
e:\programmi\microsoft visual studio\myprojects\n_primi\primenumber8.cpp(22) : error C2065: 'cout' : undeclared identifier
e:\programmi\microsoft visual studio\myprojects\n_primi\primenumber8.cpp(22) : error C2065: 'endl' : undeclared identifier
e:\programmi\microsoft visual studio\myprojects\n_primi\primenumber8.cpp(22) : warning C4552: '<<' : operator has no effect; expected operator with side-effect
e:\programmi\microsoft visual studio\myprojects\n_primi\primenumber8.cpp(23) : warning C4508: 'main' : function should return a value; 'void' return type assumed
Error executing cl.exe.

primenumber8.obj - 7 error(s), 2 warning(s)[/code]

[a2000]

dai, dai un pò di buona volontà !

fai qualche modifica tua personale e vedrai che tutto và a posto. :)
a volte è solo un problema psicologico ... del compilatore. :p

[a2000]

mumble, mumble ... bisogna che mi metta a programmare in C++ :confused:

[a2000]

Originally posted by "lucianorossi"

non và :cry:


quando proprio non sai perchè e per come: [/siz] :muro: :muro: :muro: :muro:

metti in rem riga dopo riga, blocco dopo blocco fino a quando compila (a volte succede dopo che hai messo in rem TUTTO :D )

e poi reinserisci pezzo a pezzo. :sofico: :sofico: :sofico: :sofico:

[lucianorossi]

ragazzi, ho 2 programmi per calcolare i numeri primi (a parte questo suggerito qua che non mi va)
ma danno risultati differenti (uno sui 600KB, l'altro 800KB) per un milione di numeri primi

Qual'è quello buggato (il file di testo vi viene da 600KB o 800KB?)?

[a2000]

mah.

[lucianorossi]

risolto il bug (era quello da 800)

1000000 in 16 secondi può essere sufficente per uno che ha letto le prime 3 pagine di un manuale 4 giorni fa?

[lombardp]

Originally posted by "a2000"

questo (con il pastorello e la ghiaina che hai aggiunto) :)
ma chi c'hai nell'avatar Bohr e ... Chiorboli :D

L'algoritmo mi piace assai!!!

Nell'avatar c'è Dirac... in due età diverse.

[verloc]

Originally posted by "lombardp"



E' che non ho capito di che presepe parli? :confused:

Vedi,a2000 è come i bambini della prima elementare,se non gli dici
che ha fatto bene il compitino lui si rattrista. :D

Ha citato Eduardo: "Natale in casa Cupiello" :
il vecchio padre ogni anno ,dopo aver finito il presepe
chiedeva al figlio se gli piaceva "o' presepie" ;immancabilmente
gli rispondeva di NO! :)

E il vecchio ci si faceva il sangue amaro. :)

Rispondigli di si COME SI FA AI VECCHI [/siz] :D

[/\/\@®¢Ø]

Originally posted by "lucianorossi"

non và :cry:
[/code]
Ho fatto un errore io...
inserisci

using namespace std;

dopo i tre include e prima del main.
Per il resto dovrebbe essere tutto ok (a me funziona :confused:)

[a2000]

Originally posted by "lombardp"



L'algoritmo mi piace assai!!!

Nell'avatar c'è Dirac... in due età diverse.

e c'hai pure la maglietta [/siz] ?
:D

[lucianorossi]

:cry: :cry: :cry: :cry: :cry:
--------------------Configuration: primenumber7 - Win32 Debug--------------------
Compiling...
primenumber7.cpp
E:\Programmi\Microsoft Visual Studio\MyProjects\n_primi\primenumber7.cpp(16) : error C2057: expected constant expression
E:\Programmi\Microsoft Visual Studio\MyProjects\n_primi\primenumber7.cpp(16) : error C2466: cannot allocate an array of constant size 0
E:\Programmi\Microsoft Visual Studio\MyProjects\n_primi\primenumber7.cpp(16) : error C2133: 'data' : unknown size
Error executing cl.exe.

primenumber7.obj - 3 error(s), 0 warning(s)

[/\/\@®¢Ø]

Ufff... il codice va', e dovrebbe essere piu' che corretto !
Sapevo che il VC++ piu' che un compilatore C++ e' un "compilatore del C++" (:D), ma fino a questo punto....

prova a scrivermi quale e' la riga 16 !

[lucianorossi]

righe 15-16:
unsigned long n = 1000000;
bool data[n];

[/\/\@®¢Ø]

:confused: :confused: :confused: :confused:

boh ! L'unica cosa che posso consigliarti e' di cambiare gli unsigned long in unsigned int o int,

oppure di buttare il compilatore nel... WC++ :D (hai un altro compilatore con cui provare ? )

[cionci]

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

#define N 1000000

int main()
{
unsigned long n = N;
bool data[N];
fill( data , data + n , true );
data[0] = data[1] = false;
for ( unsigned long i=2 ; i < sqrt(n) ; ++i )
if ( data[i] )
{
unsigned long m = i*2;
do
{
data[m]=false;
m+=i;
}while( m < n );
}
for (i=0 ; i<n ; ++i )
if (data[i] )
cout << i << endl;
}

VC++ come altri compilatori vuole una costante nella dichiarazione della dimensione dei vettori...

Inoltre c'era il problema di i... Per VC++ lo statement di inizializzazione del for ha visibilità anche all'esterno del for...mentre per i compialtori GNU ha scope locale solamente al for...

[a2000]

Originally posted by "verloc"



Vedi,a2000 è come i bambini della prima elementare,se non gli dici
che ha fatto bene il compitino lui si rattrista. :D

Ha citato Eduardo: "Natale in casa Cupiello" :
il vecchio padre ogni anno ,dopo aver finito il presepe
chiedeva al figlio se gli piaceva "o' presepie" ;immancabilmente
gli rispondeva di NO! :)

E il vecchio ci si faceva il sangue amaro. :)

Rispondigli di si COME SI FA AI VECCHI :D

Verloc, se scopro che sei stato tu a suggerire alla mia gatta di pisciare nel fiume del presepie dell'anno scorso ti giuro che vengo ngopp' o Vomero e ti castro :mad:

scusate l'OT :D

[/\/\@®¢Ø]

Originally posted by "cionci"

[code]

VC++ come altri compilatori vuole una costante nella dichiarazione della dimensione dei vettori...

Dormita mia ! :eek: :( (con il gcc funziona e con icc pure, cosi' non mi sono accorto dell'errore)
Il consiglio su come usare il VC++ resta comunque sempre valido :D !

[verloc]

Inoltre c'era il problema di i... Per VC++ lo statement di inizializzazione del for ha visibilità anche all'esterno del for...

triplo :eek: :eek: :eek:

sapevo che VC++ sullo standard era una m...
ma questo mi lascia allibito!

Benedetto il giorno che ho scaricato il Borland
(non sarà un granchè ma ste schifezze non le fa)

iettatel' int'o ciess!!! :D

[cionci]

Originally posted by "verloc"


sapevo che VC++ sullo standard era una m...
ma questo mi lascia allibito!
Non vorrei dire una caxxata, ma credo che lo standard non dia istruzioni in merito...

Sinceramente a me VC++ piace, non tanto per il compilatore in se stesso, ma per l'ambiente di debugging che IMHO è superiore a tutti quelli che ho visto...

[lucianorossi]

:cry: :cry: :cry:ma sono io o è questo WC?
ecco il programma:

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <vector>

using namespace std;

void main()

{
unsigned long int a, b, c, d, e, f, h;
unsigned long int numerip[250000];
bool primo;
int tipo;
FILE *fw;
...}
else if (tipo==2)
{
unsigned long n = N;
bool data[N];
fill( data , data + n , true );
data[0] = data[1] = false;
for ( unsigned long i=2 ; i < sqrt(n) ; ++i )
if ( data[i] )
{
unsigned long m = i*2;
do
{
data[m]=false;
m+=i;
}while( m < n );
}
for (i=0 ; i<n ; ++i )
if (data[i] )
cout << i << endl;
}
else
{
printf("Erore: nessuna funzione associata a");
printf("%d", &tipo);
}
}

Cosa sbaglio?
Compiling...
primenumber7.cpp
E:\Programmi\Microsoft Visual Studio\MyProjects\n_primi\primenumber7.cpp(107) : error C2065: 'N' : undeclared identifier
E:\Programmi\Microsoft Visual Studio\MyProjects\n_primi\primenumber7.cpp(108) : error C2057: expected constant expression
E:\Programmi\Microsoft Visual Studio\MyProjects\n_primi\primenumber7.cpp(108) : error C2466: cannot allocate an array of constant size 0
E:\Programmi\Microsoft Visual Studio\MyProjects\n_primi\primenumber7.cpp(108) : error C2133: 'data' : unknown size
Error executing cl.exe.

primenumber7.obj - 4 error(s), 0 warning(s)
linea 107: unsigned long n = N;

[lucianorossi]

Il programma da solo funziona:
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

#define N 1000000

void main()
{
unsigned long n = N;
bool data[N];
FILE *fw;
fw = fopen("Primenumbers.txt","w");
fill( data , data + n , true );
data[0] = data[1] = false;
for ( unsigned long i=2 ; i < sqrt(n) ; ++i )
if ( data[i] )
{
unsigned long m = i*2;
do
{
data[m]=false;
m+=i;
}while( m < n );
}
for (i=0 ; i<n ; ++i )
if (data[i] )
cout << i << endl;
}
PS: come faccio a far stampare i numeri su file di testo? (come potete vedere ho aggiunto
FILE *fw;
fw = fopen("Primenumbers.txt","w");

[cionci]

Originally posted by "lucianorossi"


Cosa sbaglio?

linea 107: unsigned long n = N;
Basta mettere il #define N 100000 o quello che vuoi...

[/\/\@®¢Ø]

Originally posted by "cionci"


Non vorrei dire una caxxata, ma credo che lo standard non dia istruzioni in merito...

No, fino ad un po' di tempo fa lo standard prevedeva che lo scoping delle variabili dichiarate tra le parentesi del for fosse del blocco che lo includeva e non del blocco piu' interno, poi questa cosa e' stata cambiata. Se non ricordo male fino a poco tempo fa anche gcc dava solo un warning.

[/\/\@®¢Ø]

Originally posted by "lucianorossi"

:cry: :cry: :cry:ma sono io o è questo WC?
ecco il programma:


Cosa sbaglio?

linea 107: unsigned long n = N;

Non hai dichiarato la variabile N.
Devi aggiungerne la dichiarazione e, visto che poi la usi per un array,
dichiararla costante

const int N = 150000;

nella parte di codice che ti interessa. Se non puoi decidere il valore a priori (ad esempio vuoi leggerlo da tastiera) allora devi cambiare un po' il codice che dichiara l'array.

[lucianorossi]

Originally posted by "cionci"


Basta mettere il #define N 100000 o quello che vuoi...
è vero, grazie

me l'ha compilato!!1 :)

ma all'avvio si blocca, windows da errore e lo chiude :cry: :cry: :cry:

[a2000]

nuova versione del crivello con piccola e semplice [color=violet] (spero non mi sospendano per linguaggio oscno :D )

ho tolto dai C++ a priori i numeri pari:
del tempo d calcolo. :p


For i = 3 To Sqr(iMax) Step 2
If aaa(i) = 0 Then
For j = 3 * i To iMax Step 2 * i
aaa(j) = 1
Next j
End If
Next i


stessa "purga virtuale" si può effettuare facilmente per i multipli di 3 (... e per la struttura dati: aaa())

[a2000]

tanto vale toglierli anche (i pari) dal vettore aaa() dimezzandolo:


kMax = Int((iMax + 1) / 2)

For k = 2 To Int((Sqr(iMax) - 1) / 2)
If aaa(k) = 0 Then
For h = 3 * k - 1 To kMax Step 2 * k - 1
aaa(h) = 1
Next h
End If
Next k

[cionci]

Originally posted by "lucianorossi"


è vero, grazie

me l'ha compilato!!1 :)

ma all'avvio si blocca, windows da errore e lo chiude :cry: :cry: :cry:
Il problema è che i vattori locali vengono allocati nello stack...se metti valori troppo grandi (cn qualsiasi compilatore) vai oltre la dimensione dello stack e chiaramente da errore...

Devi ricorrere all'allocazione dinamica...in questo modo il vettore viene allocato nello heap e c'è un po' più spazio...

Sostituisci bool data[N]; con:

bool *data = new bool[N];

Quando non ti serve più data:

delete[] data;

[lombardp]

Originally posted by "a2000"



e c'hai pure la maglietta [/siz] ?
:D


No... però negli anni di università ho seriamente preso in considerazione di crearmi una maglietta con le equazioni di Maxwell!!! :D :D :cool:

[a2000]

[/siz]

[a2000]

del tempo di calcolo rispetto al crivello naiv:

con VBA-Excel su PIV 2.4GHz:

5.93 secondi[/siz]
65.42 secondi[/siz]

:D

[cionci]

Originally posted by "lombardp"

No... però negli anni di università ho seriamente preso in considerazione di crearmi una maglietta con le equazioni di Maxwell!!! :D :D :cool:
Se non altro potrebbe tornare utile...a quelli che ti stanno intorno :)

[misterx]

Originally posted by "a2000"

del tempo di calcolo rispetto al crivello naiv:

con VBA-Excel su PIV 2.4GHz:

5.93 secondi[/siz]
65.42 secondi[/siz]

:D


va che a furia di sbavare mi è arrivata l'acqua sui piedi :D

ma sei sicuro che serve crivellarsi il cervello come stai facendo tu? ;)

[a2000]

eh, caro mio, se questo ti sembra crivellarsi il cervello ... :D :p

[a2000]

... hai visto un belmondo :pig:

[misterx]

Originally posted by "a2000"

eh, caro mio, se questo ti sembra crivellarsi il cervello ... :D :p


beh, non tanto per i metodi di calcolo proposti ma....

farsene una malattia per rosicchiare qualche secondo è altro che crivellarsi ;)

[a2000]

Originally posted by "lombardp"


No... però negli anni di università ho seriamente preso in considerazione di crearmi una maglietta con le equazioni di Maxwell!!! :D :D :cool:

Originally posted by "cionci"


Se non altro potrebbe tornare utile...a quelli che ti stanno intorno :)

io invece ho preso in seria considerazione di farmi tatuare le equazioni di Navier-Stokes, Fourier e Fick sull'uC++llo ! :D :sofico:
(in coordinate cilindriche, of course)

... sempre per l'utilità di quelli che stanno intorno. :cool:

[lombardp]

Originally posted by "misterx"


ma sei sicuro che serve crivellarsi il cervello come stai facendo tu? ;)

Probabilmente non serve... ma se non altro è divertente!! :D

[a2000]

Originally posted by "misterx"



farsene una malattia per rosicchiare qualche secondo è altro che crivellarsi ;)

ti ripeto, questa è una malattia come uno starnuto alla peste.

comunque ridurre il tempo di calcolo di routine fondamentali che vengono richiamate centinaia di migliaia di volte in un codice di calcolo è fondamentale (esempio tipico routine di calcolo di proprietà chimico-fisiche in codici di simulazione di processo).

e giocare ... serve a tenersi in allenamento.

[a2000]

Originally posted by "lombardp"


Probabilmente non serve... ma se non altro è divertente!! :D

ohhhh bravo il fisico ludico ..... il gioco è tutto ! :D


P.S.
e a volte "serve" pure:
Premio di 100.000 $ per un primo si 10.000.000 di cifre, etc...
Premio di 1.000.000 $ per la congettura di Riemann.
Premio di 1.000.000 $ per la congettura di Goldbach.

http://alpha01.dm.unito.it/personalpages/cerruti/primi/primigrandi/motivazioni.html

[a2000]

Originally posted by "misterx"


...
farsene una malattia per rosicchiare qualche secondo è altro che crivellarsi ;)

poi schiusa, nè ... potrei anche essere un carcerato nel braccio della morte (e potrei esserlo ... )
e allora piuttosto che farmi crivellare dal plotone di esecuzione preferisco farmi crivellare da Eratostene che almeno è uno solo e per giunta morto !
(scusa /\/\@®¢Ø ... ma poi è morto Eratostene ?)
o insomma! comunque se non è morto sicuramente è vecchio rinC++lionito e sbaglia mira ! :cool:

[cionci]

Originally posted by "a2000"


io invece ho preso in seria considerazione di farmi tatuare le equazioni di Navier-Stokes, Fourier e Fick sull'uC++llo ! :D :sofico:
(in coordinate cilindriche, of course
Non sapevo che facessero i tatuaggi anche con il microscopio elettronico... :cool:

[lucianorossi]

Originally posted by "a2000"

del tempo di calcolo rispetto al crivello naiv:

con VBA-Excel su PIV 2.4GHz:

5.93 secondi[/siz]
65.42 secondi[/siz]

:D
come fai, il programma che mi hai segnalato và piuttosto lento, va + veloce il mio, che però fa "solo" 1 milione in 16 secondi

[misterx]

Originally posted by "a2000"



ti ripeto, questa è una malattia come uno starnuto alla peste.

comunque ridurre il tempo di calcolo di routine fondamentali che vengono richiamate centinaia di migliaia di volte in un codice di calcolo è fondamentale (esempio tipico routine di calcolo di proprietà chimico-fisiche in codici di simulazione di processo).

e giocare ... serve a tenersi in allenamento.


va benissimo; contento te contenti tutti :D

[a2000]

Originally posted by "lucianorossi"


come fai, il programma che mi hai segnalato và piuttosto lento, va + veloce il mio, che però fa "solo" 1 milione in 16 secondi

non te l'ho segnalato, te l'ho allegato.
confermo, giuro tutto su cionci: 100 milioni in meno di sei secondi con

VBA6.0-Excel2000 con PIV 2.4GHz (516 MB di RAM).

:)

e un miliardo in 65.5 secondi.
numero massimo prima di swappare su HD : 1.5*10^9

[a2000]

Originally posted by "cionci"


Non sapevo che facessero i tatuaggi anche con il microscopio elettronico... :cool:

ehhh ... ti piacerebbe .... la trivella di Eratostene ! :sofico:

[a2000]

Originally posted by "misterx"


va benissimo; contento te contenti tutti :D

no, no ... è che se fai codici che richiedono poca memoria, corti e soprattutto veloci non sono contento io, sono proprio contenti tutti ! :cool:

almeno nei posti ... come dire ... normali. :)

[a2000]

Originally posted by "a2000"



... codici che richiedono poca memoria, corti e soprattutto veloci ...



i tre requisiti sono spesso in contrasto tanto che si dice che, a parità di efficienza, la somma delle tre cose è costante.
e in effetti la domanda di lucianorossi su righe di codice e memoria non è banale:
è in genere più veloce:
a(1) = b
a(2) = 2*b
.....
a(9) = 9*b
a(10) = 10*b

di:
For i=1 To 10
a(i) = i*b
Next i

come in genere, a parità di efficienza, è più veloce un codice che utilizza maggiore memoria dati; proprio perchè, in qualche unità di misura:

memoria di programma + memoria dati + tempo di calcolo = cost = 1/efficienza

[a2000]

prima mi sono perso "Diario d'Amore" per portare i bimbi al bat, ora mi sto perdendo Zelig (sì so' onnivoro: me magno tutto :pig: ) per star dietro a sti' quattro buontemponi ... ma adesso vi saluto.

Ciao

:)


P.S.
meditate gente, meditate :D
Marcoooo ma sto' Ca++o di Eratostene è ancora vivo o no ? :confused:

[lombardp]

Originally posted by "a2000"


è in genere più veloce:
a(1) = b
a(2) = 2*b
.....
a(9) = 9*b
a(10) = 10*b

di:
For i=1 To 10
a(i) = i*b
Next i



LOOP UNROLLING !!!

Tanto per riallacciarsi al discorso del "rimuovere gli IF", è un'altra delle tecniche per rimuovere i branch, a tutto favore della pipeline.

[a2000]

bravo lombardp: "the class (and magnetohydrodinamic equations) is not water ! "
:D

P.S.
ci deve essere anche un metacommand al compilatore ...

[a2000]

lombardp, testimoniamo a questi isolati-isolani le cose elementari: che computer vuol dire calcolatore e che serve in definitiva, in senso lato (sono provocatorio ma attuale) a menare e a non essere menati (matrix reloaded and revolution)!

Non a fare il travaso dati col filtro.

[/\/\@®¢Ø]

Originally posted by "lombardp"




LOOP UNROLLING !!!

Tanto per riallacciarsi al discorso del "rimuovere gli IF", è un'altra delle tecniche per rimuovere i branch, a tutto favore della pipeline.

Non e' piu' semplice usare il flag "-funroll-all-loops" (con gcc ad esempio) ? :D
Comunque il vantaggio non e' cosi' scontato, esplicitare i loop porta ad una maggior quantita' di codice e quindi se, usato estensivamente, una minor efficacia della cache. In definitiva se il codice passa il 90% del tempo in quei loop (in caso di elaborazione numerica non e' infrequente) puo' valerne la pena, altrimenti il vantaggio e' irrisorio.

Per a2000: penso di si', abbiamo bevuto una birra al bar l'altra sera ! Come, non intendevi Eratostene da Vicenza ? :D

[lombardp]

Originally posted by "/\/\@®¢Ø"



Non e' piu' semplice usare il flag "-funroll-all-loops" (con gcc ad esempio) ? :D
Comunque il vantaggio non e' cosi' scontato, esplicitare i loop porta ad una maggior quantita' di codice e quindi se, usato estensivamente, una minor efficacia della cache. In definitiva se il codice passa il 90% del tempo in quei loop (in caso di elaborazione numerica non e' infrequente) puo' valerne la pena, altrimenti il vantaggio e' irrisorio.


E' indubbio il fatto che non sempre questi accorgimenti portano dei vantaggi (lo avevo sottolineato anche in un post precedente).

Riguardo la questione, sicuramente l'unrolling ha senso per i loop corti, ripetuti per poche iterazioni, quelli per cui l'overhead di loop si sente. In questi casi non ci dovrebbero essere problemi con la cache.

[a2000]

i codici di calcolo numerico, quelli buoni, o perlomeno le inner subroutine, anche unrollati devono stare TUTTI nella cache e non devono scambiare dati di programma con la RAM.
non a caso nei test di calcolo scientifico tra AMD XP 3000+ e PIV 3000 si ottiene il risultato opposto dei test comparativi su applicazioni generiche.

[a2000]

ma lombardp non vuoi diventare testimone di nabla[/siz] ?

[a2000]

Originally posted by "/\/\@®¢Ø"


...
Per a2000: penso di si', abbiamo bevuto una birra al bar l'altra sera ! Come, non intendevi Eratostene da Vicenza ? :D

chi ? quello che ha vinto la gara di rutti al Bar Bepi ?

[misterx]

Originally posted by "a2000"

i codici di calcolo numerico, quelli buoni, o perlomeno le inner subroutine, anche unrollati devono stare TUTTI nella cache e non devono scambiare dati di programma con la RAM.
non a caso nei test di calcolo scientifico tra AMD XP 3000+ e PIV 3000 si ottiene il risultato opposto dei test comparativi su applicazioni generiche.

se la cache è da 3 Gbyte che ti frega??? :D :D

[a2000]

:D :D

giusto! anche se il thread è da 100 post !

:D :D