Pagina 2 di 3
Inviato: 01 dic 2006, 00:09
da SkZ
effettivamente dati $ ~n $ numeri $ ~a_i $ esistono infiniti polinomi di grado $ ~n $ che passano per i punti $ ~(k,a_k) $
un po' dura scegliere il successivo.
Una sequenza casuale e' quella ottenuta basandosi su processi fisici noti per essere casuali, come fenomeni quantistici & similia (v. generatore hardware di numeri casuali)
Inviato: 01 dic 2006, 11:17
da rand
Una definizione di sequenza casuale è quella di Kolmogorov: fissato un linguaggio di programmazione di riferimento, si dice casuale una sequenza che non può essere generata da un programma più corto della sequenza stessa.
Se la adottiamo allora curiosamente (questo è relativo...) i primi da 1 a N, per N abbastanza grande, non sono una sequenza casuale, perchè sappiamo scrivere una procedura di lunghezza C + log N, dove C è costante dipendente solo dal linguaggio e log N è la lunghezza del contatore, che genera i primi da 1 a N, ed essendoci circa N/logN primi nella sequenza questa diverrà inevitabilmente più lunga del programma al crescere di N.
Inviato: 08 dic 2006, 16:18
da thenigma
Per trovare tutti i primi da 1 ad n basta applicare il crivello di eratostene (sempre che non si abbiano particolari esigenze computazionali).
Una veloce (e senza alcuna pretesa) implementazione in matlab è:
Codice: Seleziona tutto
n = input('inserisci il numero di partenza ');
L = [0, 2 : n];
for i = 2 : sqrt(n)
for j = 1 : n-i
if ( mod(L(1,i+j), i) == 0 )
L(1,i+j)=0;
end
end
end
for i=1:n
if L(1,i) ~= 0
disp(L(1,i));
end
end
In C è la stessa cosa (si usa l'operatore %), la traduzione è davvero molto vicina (ma non ho idea di quale sia il linguaggio richiesto quindi me la risparmio
).
Inviato: 29 mar 2007, 23:30
da giorgiobusoni87
allora, partecipo alla discussione dato che è un problema che styo' riaffrontando in questi giorni...avevo un buon programma ma ho perso il codice, adesso ne sto riscrivendo uno e cercando di renderlo efficace.
Il primo metodo che mi è venuto in mente è stato spiegato subito, chè creare un array e infilarci i primi uno dietro l'altro, e per trovare altri primi usare i primi a nostra disposizione nell'array. Ottimizzazioni aggiunte: controlla fino a sert(x) e salta i numeri pari.
Tuttavia usando un array normale in C non sono riuscito ad andare oltre 150000 numeri primi (se creo array più grossi crasha). Allora ho fatto una cosa così:
Codice: Seleziona tutto
#include "numerip.h"
#include <stdio>
#include <vector>
#include <malloc>
#include <algorithm>
using namespace std;
vector<unsigned> numerip;
vector<unsigned>::iterator it;
void main()
{
unsigned long long int i=1, n, j, r;
// struct elemento *lista = NULL;
bool primo;
// unsigned long int numerip[250000]={2, 3};
printf("Inserisci l'estremo superiore dell'intervallo\n");
scanf("%llu", &n);
numerip.resize(n);
numerip[0]=2;
numerip[1]=3;
j=5;
/* dichiara lo stream e il prototipo della funzione fopen */
FILE * stream;
/* apre lo stream del file */
stream = fopen("primi.txt", "w");
/* controlla se il file viene aperto */
if ((stream = fopen("primi.txt", "w")) == NULL)
{
printf("Non posso aprire il file %sn", "primi.txt");
}
fprintf(stream, "%llu, ", numerip[0]);
fprintf(stream, "%llu, ", numerip[1]);
while (j<n>=numerip[h]*numerip[h]) {
r=j%numerip[h];
if(r==0) {
primo=false;
break;
}
h++;
}
if(primo==true) {
i++;
numerip[i]=j;
fprintf(stream, "%llu, ", numerip[i]);
}
j=j+2;
}
printf("Ho trovato %d numeri\n", i);
}
Questa funziona tranquillamente fino a p<100000000 sul mio pc (credo dipenda dalla ram, per calcolarne i primi <100000000 ne cosumanva 700MB). Da questo ho dedotto che un programma così è fortemente limitato....certo, con i primi <100000000 potrei calcolarli fino a 100000000^2 ma ci ha messo quasi 20 minuti a farne 100000000).
Pensavo allora di usare il crivello di eratostene. Andrea M. ha sviluppato questo programma allora:
Codice: Seleziona tutto
#include <stdio>
#include <vector>
#include <algorithm>
using namespace std;
unsigned long long int N;
vector<bool> V;
vector<bool>::iterator it;
int
main()
{
FILE *fw;
fw=fopen("output.txt","w");
if(fw==NULL){printf("ERROR while opening output.txt\n");return 1;}
printf("Inserisci N\n");
scanf("%llu",&N);
V.resize(N);//settati tutti a 0: 0 se è primo 1 se no
for(unsigned long long int i=2;i<N;i++)
{
if(!V[i])
for(unsigned long long int j=2 ;i*j<N;j++)
V[i*j]=true;
}
//STAMPA
for(unsigned long long int i=2;i<N;i++)
if(!V[i])fprintf(fw,"%llu ",i);
return 0;
}
A lui su linux va molto veloce, ma a me su windows va estremamente lento (più dell'altro, per esempio per calcolare i primi <3000000 il mio ci mette sui 5 secondi, il suo (sul mio pc) 80 secondi, sul suo pc 2 secondi. Ancora non abbiamo capito perchè. A qualcuno viene in mente un metodo più veloce (non solo a livello di algoritmo matematico, ma anche si programma in C)?
Inviato: 30 mar 2007, 01:30
da MindFlyer
Beh, un'ottimizzazione ovvia di quel crivello di Eratostene "pecorone" è:
trovato un primo p, inizia a crivellare da p*p, e non da 2p.
E poi, For Fuck's Sake, non fate tutte quelle moltiplicazioni!!!
Fare j++ e poi calcolare i*j ad ogni ciclo, con i che resta costante, è da fessi, scusatemi...
Migliorato
Inviato: 21 apr 2007, 22:51
da mykelyk
Gli ho dato una buona ottimizzazione, che ne pensate?
N = 1000000000 Sul mio computer l'ho portato a 1 secondo di uso cpu
Meglio di così cosa c'è?
Codice: Seleziona tutto
#include "stdafx.h"
int main(){
__w64 unsigned int t, i, j;
bool* V = new bool[1000000000];
V[0] = V[1] = false;
for(j=4; j<1000000000; j+=2)
V[j] = false;
for(i=3; i<1000000000; i+=2)
if(V[i])
for(j=i*i, t=2*i; j<1000000000; j+=t)
V[j] = false;
//FILE *fw = fopen("output.txt", "w");
//fprintf(fw, "%i\n", 2);
//for(i=3; i<1000000000; i+=2)
// if(V[i])
// fprintf(fw,"%i\n",i);
return 0;
}
Inviato: 21 apr 2007, 23:55
da fph
Inviato: 22 apr 2007, 00:22
da Reese
Così ha anche senso l'array dinamico, dato che prima sarebbe stato meglio dichiararlo normalmente.
Inviato: 22 apr 2007, 14:44
da mykelyk
L'array è dinamico perché è troppo grosso 1000000000 bool tengono circa un giga di ram, troppo per essere dichiarato normalmente.
Non mi funziona, non ho la più vaga idea del perchè.
Potrei naturalmente inserire una nuova variabile N = 1000000000, ma l'algoritmo sarebbe più lento.
Re: Migliorato
Inviato: 22 apr 2007, 16:17
da SkZ
si puo' cercare di eliminare i pari, ricordando che il primo pari e' ovviamente primo
in modo che V
mi dia indicazioni su $ ~2i+1 $
(soprattutto dato che tu gia' stampi il 2 come primo a priori del valore in V[2])
Codice: Seleziona tutto
#include "stdafx.h"
int main(){
__w64 unsigned int t, i, j;
bool* V = new bool[1000000000];
V[0] = false;
for(i=1; i<1000000000; i++)
if(V[i])
for(j=i*(i+1)<<1, t=2*i+1; j<1000000000; V[j+=t] = false);
//FILE *fw = fopen("output.txt", "w");
//fprintf(fw, "%i\n", 2);
//for(i=1; i<1000000000; i++)
// if(V[i])
// fprintf(fw,"%i\n",2*i+1);
return 0;
}
Nuova versione
Inviato: 22 apr 2007, 21:45
da mykelyk
@SkZ: Ci stavo già pensando ieri, ed oggi l'ho fatto:
Ora i pari vengono saltati e V
da indicazioni su 2i +1 esattamente come diceva SkZ:
Codice: Seleziona tutto
#include "stdafx.h"
#include <iostream>
#include <math>
using namespace std;
int main(){
#define MAX 2000000000
__w64 unsigned int t, i, j,
HALFMAX = (MAX+1)/2,
RADMAX = (int)sqrt((long double)MAX)+1,
HALFRADMAX = (RADMAX+1)/2;
bool* V = new bool[HALFMAX];
V[0] = false;
for(i=1; i<HALFMAX; i++)
V[i] = true;
for(i=1; i<HALFRADMAX; i++)
if(V[i])
for(j= i*(t=2*i+2), t--; j<HALFMAX; j+=t)
V[j] = false;
//FILE *fw;
//fopen_s(&fw, "output.txt", "w");
//fprintf(fw, "%i\n", 2);
//for(i=1; i<HALFMAX; i++)
// if(V[i])
// fprintf(fw,"%i\n",2*i+1);
cout << 2 << endl;
for(i=j=1; i<HALFMAX; i++){
if(!V[i])
continue;
cout << 2*i+1;
if(++j%20)
cout << endl;
else{
char pause[2];
cin.getline(pause, 1);
}
}
cout << ">- Finito -<" << endl;
char pause[2];
cin.getline(pause, 1);
return 0;
}
Tempo sul mio computer(ottimizzato tutto) 44-45 secondi.
Mi è venuta un'idea per aumentare ancora la capacità, provo a metterla in pratica
Lascio perdere
Inviato: 23 apr 2007, 02:40
da mykelyk
Lascio perdere.
Se qualcuno ha voglia di provarci...
Codice: Seleziona tutto
union bools{
public:
unsigned char byte;
struct bits{
public:
unsigned char _0:1, _1:1, _2:1, _3:1, _4:1, _5:1, _6:1, _7:1;
} bit;
};
//Permette di accedere ai singoli bit.
bools V;
V.byte = 0XFF; // reset
V.bit._3 = 0;
In questo modo si ottiene un risparmio di memoria dell'87,5%
Ma mi sono perso.
Buona notte.
Inviato: 23 apr 2007, 08:55
da Reese
mykelyk ha scritto:
Non mi funziona, non ho la più vaga idea del perchè.
Potrei naturalmente inserire una nuova variabile N = 1000000000, ma l'algoritmo sarebbe più lento.
Prova
.
Inviato: 23 apr 2007, 09:30
da SkZ
l'effetto e' diverso:
col define la sostituzione viene fatto dal preprocessore, quindi al momento della compilazione, mentre definendo la variabile la sostituzione viene al momento dell'esecuzione con accesso alla memoria
hai controllato che il tuo sistema non usi gia' 1bit per i bool?
Inviato: 23 apr 2007, 13:11
da Reese
SkZ ha scritto:l'effetto e' diverso:
col define la sostituzione viene fatto dal preprocessore, quindi al momento della compilazione, mentre definendo la variabile la sostituzione viene al momento dell'esecuzione con accesso alla memoria
hai controllato che il tuo sistema non usi gia' 1bit per i bool?
Ti riferisci al const N = ... ?
Mi sa che e' la stessa cosa di define..