Nepoužívajte Avast

zbytočne blokuje všetko. Rozbehol som programy, ktoré sú schopné paralelizovať výpočty medzi všetky jadrá CPU. (Aby sa cpu moc nezahrieval, uživateľ si môže zvoliť na koľko % pobeží jeho procesor) -Ako test som si zvolil prvočísla. Desiatky miliárd prvočísel za pár minút. (Knižnica OpenMP) ....Najvprv prebehne výpočet. Bloky sú rozdelené tak, aby sa zmestili do cache L1 a L2 CPU. To je extrémne rýchle. CPU použije RAM len vtedy, keď je cache zaplnená. (Vyklopí výsledky naraz.) Najzdĺhavejší je potom proces tvorby binárnych súborov. Každé jadro má najprv svoj vlastný bin súbor. Na konci hľadania sa spoja do jedného. To trvá najdlhšie, lebo na tento proces sa nedajú využiť všetky jadrá, ale len jedno. Vznikne tak súbor s desiatkami miliárd prvočísel. To je najpomalšia časť algoritmu (ešte sa mám veľa čo učiť)

Hrdlo láhve - zápis na disk.

A to mám SSD s 500MB/s.

Mám to už hotové. ...Ale keď to budem mať už skutočne hotové, zverejním to tu... (vrátane zdrojového kódu)

A ešte aby som nezabudol: na pozadí výpočtov beží klasické staroveké, najlepšie Eratostenovo sito. To je najlepší algoritmus na prvočísla...

Samozrejme mám hotový prehliadač bin súborov a tiež prekladač do txt. Ale na ten txt súbor budete potrebovať disk s terabajtami...

Tu je predbežná verzia:

1. Vypnite antivirák

2. Spustite a nechajte prebehnúť toto: odkaz (na začiatku zadávate koľko chcete zistiť prvočísel a s akým výkonom procesora)


Takto to vyzerá na konci:

odkaz

3. Výsledok prehliadajte týmto: odkaz (...tam volíte od ktorého prvočísla a koľko ich chcete zobraziť)

Občas sa nárast percent nachvíľu zastaví, lebo sa zapisuje...

Napíšte sem, aké "nemožné" úlohy by sme mohli nechať počítač ďalej riešiť. Snáď to dám. A ak nie, dá to niekto druhý...

Predpovedanie výherných čísel v Lotto 😉

👍: Fotón

Noo, predpovedať budúcnosť sa asi nedá...

Nepotešil jste mně, ani já vás nepoteším 😉

Je to na prdel, keď sa to nedá 😉

Všetko má svoje limity...

Nemám rád limity 😉

Lebo smerujú do nekonečna a nikdy tam nedobehnú 😉

Lenže budúcnosť ešte len príde. Nevieme, čo bude...

Jedine, žeby minulosť, prítomnosť i budúcnosť už existovala 😉

Naraz 😉

Akurát, že my vidíme len tú prítomnosť 😉

Ale ten, ktorý je mimo času, môže vidieť všetky stavy a priebehy Vesmíru naraz 😉

Ako náhrdelník s korálkami, kde každá korálka je jednou verziou reality v danom okamihu 😉

Dám vám aj tie kódy:

Kód hľadania:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <omp.h>

#define SEGMENT_SIZE 1048576 // 1 MB segment ideálny pre L2/L3 Cache jadier
#define MAX_GAP 1500
#define RAM_LIMIT_MB 200 // Navýšené na 200 MB pre rýchlejšie disky na stolnom PC

int main() {
long long int CIELOVY_POCET;
int percenta_cpu;

printf("--- MAXIMALNA PARALELIZACIA S KONTROLOU VYKONU ---\n");
printf("Zadaj cielovy pocet prvocisiel (napr. 1000000000): ");
if (scanf("%lld", &CIELOVY_POCET) != 1 || CIELOVY_POCET <= 0) return 1;

printf("Zadaj kolko %% vykonu CPU chces pouzit (1 - 100): ");
if (scanf("%d", &percenta_cpu) != 1 || percenta_cpu < 1 || percenta_cpu > 100) {
printf("Neplatne percento výkonu.\n");
return 1;
}

double start_time = omp_get_wtime();

// 1. Nastavenie počtu jadier podľa zvolených percent
int max_dostupnych_jadier = omp_get_max_threads();
int pocet_vlakien = (int)ceil((max_dostupnych_jadier * percenta_cpu) / 100.0);
if (pocet_vlakien < 1) pocet_vlakien = 1;

// Prikážeme OpenMP použiť len určený počet jadier
omp_set_num_threads(pocet_vlakien);
printf("\nAlokujem %d z %d jadier CPU (zvolenych %d%% vykonu)...\n",
pocet_vlakien, max_dostupnych_jadier, percenta_cpu);

// 2. Odhad horného číselného limitu na základe požadovaného počtu
long long int MAX_CISLO = (CIELOVY_POCET < 10) ? 100 : (long long int)(CIELOVY_POCET * log(CIELOVY_POCET) * 1.2) + 1000;

// Predsito pre generovanie základných prvočísel
int sqrt_limit = (int)sqrt(MAX_CISLO);
std::vector<char> is_prime_small(sqrt_limit + 1, 1);
for (int p = 2; p * p <= sqrt_limit; p++) {
if (is_prime_small[p]) {
for (int i = p * p; i <= sqrt_limit; i += p) is_prime_small[i] = 0;
}
}
std::vector<int> primes;
for (int p = 2; p <= sqrt_limit; p++) if (is_prime_small[p]) primes.push_back(p);

// Globálne premenné a štatistiky
long long int globalny_pocet_celkovo = 0;
long long int globalna_statistika_medzier[MAX_GAP] = {0};
long long int globalne_posledne_prvocislo = 2;

// Zastavovací príznak pre vlákna, ak už máme dosť prvočísel
bool koniec_vsetko = false;

// 3. PARALELNA ZÓNA
#pragma omp parallel
{
int thread_id = omp_get_thread_num();
int num_threads = omp_get_num_threads();

// Rozdelenie megablokov podla REÁLNE spusteného počtu vlákien
long long int rozsah_jedneho_jadra = (MAX_CISLO - 3) / num_threads;
long long int thread_low = 3 + thread_id * rozsah_jedneho_jadra;
long long int thread_high = (thread_id == num_threads - 1) ? MAX_CISLO : (thread_low + rozsah_jedneho_jadra - 1);

if (thread_low % 2 == 0) thread_low++;

char t_filename[32];
sprintf(t_filename, "tmp_thread_%d.bin", thread_id);
FILE *f_bin = fopen(t_filename, "wb");

long long int max_v_ram = (RAM_LIMIT_MB * 1024LL * 1024LL) / sizeof(long long int);
long long int *ram_buffer = (long long int *)malloc(max_v_ram * sizeof(long long int));
long long int miestna_statistika_medzier[MAX_GAP] = {0};

long long int miestny_pocet = 0;
long long int posledne_miestne_prvocislo = 0;
int v_ram = 0;

long long int low = thread_low;
while (low <= thread_high && !koniec_vsetko) {
long long int high = low + SEGMENT_SIZE - 1;
if (high > thread_high) high = thread_high;

std::vector<char> segment(high - low + 1, 1);

for (size_t i = 0; i < primes.size(); i++) {
int p = primes[i];
long long int start = (low + p - 1) / p * p;
if (start < (long long int)p * p) start = (long long int)p * p;
if (start % 2 == 0) start += p;
for (long long int j = start; j <= high; j += 2 * p) {
segment[j - low] = 0;
}
}

for (long long int n = low; n <= high; n += 2) {
if (segment[n - low]) {
// Poistka: Ak iné vlákno medzitým naplnilo celkový počet, končíme zápis
if (koniec_vsetko) break;

if (posledne_miestne_prvocislo != 0) {
long long int medzera = n - posledne_miestne_prvocislo;
if (medzera < MAX_GAP) miestna_statistika_medzier[medzera]++;
}
posledne_miestne_prvocislo = n;

ram_buffer[v_ram++] = n;
miestny_pocet++;

if (v_ram >= max_v_ram) {
fwrite(ram_buffer, sizeof(long long int), v_ram, f_bin);
v_ram = 0;
}
}
}

// Kontrola ukončenia: sčítame priebežný bezpečný stav (len občas, aby sme nespomaľovali CPU)
if (low % (SEGMENT_SIZE * 20) == 3) {
long long int aktualny_globalny_stav = 0;
#pragma omp atomic read
aktualny_globalny_stav = globalny_pocet_celkovo;

if (aktualny_globalny_stav >= CIELOVY_POCET) {
koniec_vsetko = true;
}

if (thread_id == 0) {
double percenta = (double)(low - thread_low) * 100.0 / (thread_high - thread_low);
if (percenta > 100.0) percenta = 100.0;
printf("\rVlakno 0 Progres: %.1f %% | Spracovava sa... ", percenta);
fflush(stdout);
}
}

low += SEGMENT_SIZE;
}

if (v_ram > 0) fwrite(ram_buffer, sizeof(long long int), v_ram, f_bin);
fclose(f_bin);
free(ram_buffer);

// Bezpečné sčítanie výsledkov z tohto jadra
#pragma omp critical
{
globalny_pocet_celkovo += miestny_pocet;
for (int i = 0; i < MAX_GAP; i++) {
globalna_statistika_medzier[i] += miestna_statistika_medzier[i];
}
if (posledne_miestne_prvocislo > globalne_posledne_prvocislo) {
globalne_posledne_prvocislo = posledne_miestne_prvocislo;
}
}
} // Koniec paralelnej zóny

printf("\rVlakno 0 Progres: 100.0 %%\n");
printf("Vypocty ukoncene. Spajam a orezavam docasne subory na presny pocet...\n");

// 4. Spojenie súborov a presné orezanie na požadovaný cieľový počet
FILE *f_vysledok = fopen("tmp.bin", "wb");
long long int cislo_dva = 2;
fwrite(&cislo_dva, sizeof(long long int), 1, f_vysledok);

long long int zapisane_celkovo = 1; // Započítaná dvojka

for (int i = 0; i < pocet_vlakien; i++) {
char t_filename[32];
sprintf(t_filename, "tmp_thread_%d.bin", i);
FILE *f_in = fopen(t_filename, "rb");
if (f_in) {
long long int buffer_spojenia[4096];
size_t precitane;
while ((precitane = fread(buffer_spojenia, sizeof(long long int), 4096, f_in)) > 0) {
for (size_t j = 0; j < precitane; j++) {
if (zapisane_celkovo < CIELOVY_POCET) {
fwrite(&buffer_spojenia[j], sizeof(long long int), 1, f_vysledok);
zapisane_celkovo++;
// Aktualizujeme posledné reálne zapísané prvočíslo
globalne_posledne_prvocislo = buffer_spojenia[j];
} else {
break;
}
}
if (zapisane_celkovo >= CIELOVY_POCET) break;
}
fclose(f_in);
remove(t_filename); // Vyčistenie disku
}
}
fclose(f_vysledok);

// Zápis štatistiky
FILE *f_stat = fopen("statistika_medzier.txt", "w");
fprintf(f_stat, "Medzera;Pocet_vyskytov\n");
for (int i = 1; i < MAX_GAP; i++) {
if (globalna_statistika_medzier[i] > 0) {
fprintf(f_stat, "%d;%lld\n", i, globalna_statistika_medzier[i]);
}
}
fclose(f_stat);

printf("\n=== HOTOVO ===\n");
printf("Celkovy cas: %.2f s\n", omp_get_wtime() - start_time);
printf("Presny pocet zapisanych prvocisiel: %lld\n", zapisane_celkovo);
printf("Posledne prvocislo (index %lld): %lld\n", zapisane_celkovo, globalne_posledne_prvocislo);

printf("\nStlac Enter pre ukoncenie...");
fflush(stdout);
getchar(); getchar();

return 0;
}

Kód zobrazenia:

#include <stdio.h>
#include <stdlib.h>

// Definujeme makra pre podporu velkych suborov
#define fseeko fseeko64
#define ftello ftello64

int main() {
// Pouzijeme "rb" pre binarne citanie
FILE *f = fopen("tmp.bin", "rb");
if (!f) {
printf("Chyba: Subor 'tmp.bin' nebol najdeny!\n");
system("pause");
return 1;
}

// Zistíme veľkosť súboru pomocou 64-bitovej verzie ftello
fseeko(f, 0, SEEK_END);
long long velkost = ftello(f);
long long pocet_prvocisiel = velkost / 8; // sizeof(long long) je 8
rewind(f);

printf("--- OPRAVENY BINARNY PREHLIADAC (64-bit) ---\n");
printf("V subore je celkovo: %lld prvocisiel.\n", pocet_prvocisiel);
printf("Velkost suboru: %.2f GB\n", (double)velkost / (1024.0 * 1024.0 * 1024.0));

while (1) {
long long index;
int rozsah;

printf("\nZadaj poradove cislo (1 - %lld), 0 pre koniec: ", pocet_prvocisiel);
if (scanf("%lld", &index) != 1 || index <= 0) break;

printf("Kolko prvocisiel chces vypisat? ");
scanf("%d", &rozsah);

if (index > pocet_prvocisiel) {
printf("Chyba: Tolko prvocisiel tam nie je!\n");
continue;
}

// Skočíme na pozíciu pomocou 64-bitového fseeko
fseeko(f, (index - 1) * 8, SEEK_SET);

printf("\n--- VYPIS ---\n");
for (int i = 0; i < rozsah; i++) {
long long prvocislo;
if (fread(&prvocislo, 8, 1, f) == 1) {
printf("%lld. prvocislo: %lld\n", index + i, prvocislo);
} else {
break;
}
}
printf("-------------\n");
}

fclose(f);
printf("\nProgram ukonceny.\n");
system("pause");
return 0;
}

Všimnite si sekciu: #pragma omp parallel
To je ten zázrak...