c++ - Primtal på hjernen... - Udvikleren.dk - Programmering, webdesign og grafik

Tags: c++

<< < 1 2 3 > >>

Bruger #4414 @ 08.02.06 22:43

Jeg har sat min computer og mit uforlignelige intellekt på prøve. ;-)

Skriv et program i c++, der udregner primtal.
Så mange som muligt, så hurtigt som muligt.
De omtale tal skal skrives til en fil på harddisken ikke på skærmen.
Gør koden så kort som mulig.
Der må kun bruges standard liberys/headers ect.

Her er hvad jeg er nået frem til:

Kode

#include <vector>
#include <cmath>
#include <fstream>
int main() {
  std::vector<unsigned long> P(1,3);
  int i;
  bool is_prime;
  std::ofstream primes("primes.txt",std::ios::out|std::ios::app);
  primes << "2" << std::endl;
  primes << P.back() << std::endl;
  for (unsigned long long test = 5; test > 4; test += 2) {
    for (i = 0, is_prime = true; P[i] <= sqrt(test) && is_prime == true; i++)
      if (test % P[i] == 0) is_prime = false;
    if (is_prime == true && test <= 0xffffffff) P.push_back(test);
    if (is_prime == true) primes << P.back() << std::endl;
  }
  primes.close();
}

Det vigtigste man bør lægge mærke til her er at vectoren er af typen unsigned long (32 bit), men variablen test er af typen unsigned long long (64 bit), dette har naturligvis en årsag.
Når man tester om en tal er et primtal, tester man som bekendt (medmindre man bruger mystiske algoritmer og den slags) om de primtal der er mindre en tallet går op i, dog er det ikke nødvengidt at teste primtal størrer end kvardratroden at primtalet op i test tallet (det her kunne formuleres bedre)
en unsigned long long kan max indeholde værdien 2^64-1 og en unsigned long værdien 2^32-1.
Kvardratroden af førstnævnte er lig med
4294967295,9999999998835846781731
det er lige 0,9999999998835846781731 mere end en unsigned long kan indeholde, detter er naturligvis ikke et problem, da vi ikke regner med kommatal her, vi tester kun med primtal der er mindre eller er lig med kvardratroden af tallet der skal testes, så vi kan med fordel runde ned, hvilket vil sige at vi ikke har brug for at gemme primtal størrer en typen unsigned long.
Det er hvad jeg kalder effektivitet ;-)

Nuvel, jeg lod mig vist rive lidt med, hvad jeg egenlig ville hvar at udfordre alle genierne herinde til at gøre det bedre og hvis ingen skulle have lyst til at gøre et forsøg, er jeg stadig lidt utilfreds med strukturen, men hvis jeg gør som jeg gerne vil, brokker kompileren sig over at en eller anden iso standard ikke bliver overholdt.

[Redigeret d. 08/02-06 22:57:39 af Felix Nielsen]

[Redigeret d. 08/02-06 22:58:42 af Felix Nielsen]

[Redigeret d. 09/02-06 00:53:14 af Felix Nielsen]

Bruger #4414 @ 09.02.06 15:54

113

Jeg kan se på det hele at der ikke er mange andre end mig der har interesse for primtal, ikke desto mindre udspringer der jo også andre spændende ting fra denne slags forsøg.

Jeg kan orientere om at mit program crashede efter at have skrevet primtallet 2.777.105.131 til filen "primes.txt" som "kun" nåede en størrelse af 1.44 GB.
Da jeg gerne skulle kunne have filer af størelsen 4 GB liggende, går jeg ikke ud fra at det er det der er problemet.
Disse 1.44 GB primtal har computerenjo også haft liggende i hukkommelsen, så jeg tror ikke at der kan sås tvivl om at det er der problemet ligger.

Personligt kan jeg se 2 løsnings modeller.
Den første er at istedet for at lade programmet læse og skrive til en vector hele tiden, kunne man jo bruge filen, derved kan man spare en hel del på hukkommelsen, jeg er dog ikke helt sikker på hvordan det kan gøres.

Den anden "løsningsmodel" er at optimere endnu mere ;-)
Det er jo ikke første gang at jeg har skrevet et sådan program, men sidste gang nåede jeg altså kun en fil ca. halv så stor som den nuværende.
Jeg er selv ret sikker på at det ikke kan optimeres meget mere, men der er altid et eller andet man kan gøre.
Noget har jeg da også gjort.
Jeg synes selv det er ret cool, men det er vist desværer ikke nok.

Kode

#include <vector>
#include <cmath>
#include <fstream>

struct _v1 {unsigned long v1:8;};
std::vector<_v1>v1(0);
struct _v2 {unsigned long v2:16;};
std::vector<_v2>v2(0);
struct _v3 {unsigned long v3:24;};
std::vector<_v3>v3(0);
struct _v4 {unsigned long v4:32;};
std::vector<_v4>v4(0);

unsigned long read(unsigned long i) {
  if (i < v1.size()) return v1[i].v1;
  else if (i < v2.size()) return v2[i-v1.size()].v2;
  else if (i < v3.size()) return v3[i-(v1.size()+v2.size())].v3;
  else if (i < v4.size()) return v4[i-(v1.size()+v2.size()+v3.size())].v4;
}

void write(unsigned long val) {
  if (val <= 0xff) {
    _v1 val1;
    val1.v1 = val;
    v1.push_back(val1);
  }
  else if (val <= 0xffff) {
    _v2 val2;
    val2.v2 = val;
    v2.push_back(val2);
  }
  else if (val <= 0xffffff) {
    _v3 val3;
    val3.v3 = val;
    v3.push_back(val3);
  }
  else if (val <= 0xffffffff) {
    _v4 val4;
    val4.v4 = val;
    v4.push_back(val4);
  }
}

int main() {
  int i;
  bool is_prime;
  write(3);
  std::ofstream primes("primes.txt",std::ios::out|std::ios::app);
  primes << "2" << std::endl;
  primes << "3" << std::endl;
  for (unsigned long long test = 5; test != 1; test += 2) {
    for (i = 0, is_prime = true; read(i) <= sqrt(test) && is_prime == true; i++)
      if (test % read(i) == 0) is_prime = false;
    if (is_prime == true && test <= 0xffffffff) write(test);
    if (is_prime == true) primes << test << std::endl;
  }
  primes.close();
}

Bruger #1151 @ 09.02.06 17:51

421

Jeg har også selv prøvet det

Meget sjovt. Kan dog ikke huske mit største tal andet end at jeg kørte den over 7 dage på en 800 mhz. Ang. dit program. Har du prøvet at få din primtals algoritme ned? Så den fx. ikke kører over 2 for løkker?

Slot - All your base are belong to us
http://www.sigsys.dk

Bruger #4414 @ 09.02.06 20:53

113

Jeg ser ikke umiddelbart nogen mulighed for kun at bruge én løkke, dog kunne jeg godt tænke mig at få de to variabler i og is_prime inkooporeret i disse løkker, det har dog ikke vist sig muligt da kompileren brokker sig overat ISO90 standarden (hvad det så end er) ikke bliver overholdt og kommer med besked om div. variabel lockups¿

Jeg kunne godt tænke mig en anden løsning end struct til at holde styr på hvor meget de enkelte celler i vectorerne fylder. Måden jeg gør det på nu fylder meget og er i det hele taget lidt besværlig.

Sidst men ikke mindst kunne jeg godt tænke mig at prøve idéen med at droppe den store vector og bruge en fil på harddisken, men jeg har ingen idé om hvordan jeg fx. får fat i linie 37 i filen uden at det kræver en masse recourser og jeg kunne også forestille mig at det giver visse vanskeligheder når man kommer op i filstørelsen på en eller flere GB.

Bruger #714 @ 09.02.06 20:57

321

Jeg ser ikke umiddelbart nogen mulighed for kun at bruge én løkke, dog kunne jeg godt tænke mig at få de to variabler i og is_prime inkooporeret i disse løkker, det har dog ikke vist sig muligt da kompileren brokker sig overat ISO90 standarden (hvad det så end er) ikke bliver overholdt og kommer med besked om div. variabel lockups¿

Jeg kunne godt tænke mig en anden løsning end struct til at holde styr på hvor meget de enkelte celler i vectorerne fylder. Måden jeg gør det på nu fylder meget og er i det hele taget lidt besværlig.

Sidst men ikke mindst kunne jeg godt tænke mig at prøve idéen med at droppe den store vector og bruge en fil på harddisken, men jeg har ingen idé om hvordan jeg fx. får fat i linie 37 i filen uden at det kræver en masse recourser og jeg kunne også forestille mig at det giver visse vanskeligheder når man kommer op i filstørelsen på en eller flere GB.

Hvis du tror at dit program crasher fordi det bruger for meget hukommelse, så øg da bare størrelsen på pagefilen, så er du fri for at tænke på at håndtere det med filerne, det gør windows for dig.

Mvh
Kaare

Bruger #4414 @ 09.02.06 21:31

113

det er naturligvis en løsningsmodel ;-)
Pointen er dog lidt at ved at stille sig selv sådanne opgaver lærer uværgeligt en hel masse...

Bruger #4414 @ 10.02.06 13:25

113

Denne gang nåede jeg så til 2.800.551.821 og en filstørrelse på 1.45 GB så det er jo ikke den stpre forskel.

Bruger #3789 @ 11.02.06 17:05

Denne gang nåede jeg så til 2.800.551.821 og en filstørrelse på 1.45 GB så det er jo ikke den stpre forskel.

Hvor lang tid tager det for din computer at nå det tal ?

Bruger #4414 @ 12.02.06 00:17

113

Denne gang nåede jeg så til 2.800.551.821 og en filstørrelse på 1.45 GB så det er jo ikke den stpre forskel.

Hvor lang tid tager det for din computer at nå det tal ?

Ved ikke, omkring 8 timer hvis den ikke er belastet af andre ting vil jeg tro.

[Redigeret d. 12/02-06 00:19:34 af Felix Nielsen]

Bruger #4414 @ 12.02.06 01:41

113

Denne gang nåede jeg så til 2.800.551.821 og en filstørrelse på 1.45 GB så det er jo ikke den stpre forskel.

Hvor lang tid tager det for din computer at nå det tal ?

Ved ikke, omkring 8 timer hvis den ikke er belastet af andre ting vil jeg tro.

[Redigeret d. 12/02-06 00:19:34 af Felix Nielsen]

Så er jeg gået igang med en omgang til.
ændringer er:
Størrer sidefil.
'int i' er nu 'unsigned long long i' jeg tror nøppe at det er det der har været skyld i fejlen, men under alle omstændigheder er en int ikke nok når man når op i de størrer tal.

Bruger #4414 @ 12.02.06 15:43

113

Med størrer sidefil og 'unsigned long long i' nåede jeg kun til 1.44 Gb ligesom tidligere, det bekræfter jo at det ikke er manglene hukkommelse.
Jeg tænker at der måske er en begrænsning på størrelsen at vectorer, men jeg er ivrig effter at høre jeres mening...

<< < 1 2 3 > >>

Primtal på hjernen...

Karma barometer (30 dage)

Modtaget

Givet

Favorit hos
Forum tråde
Artikler