BitCell

by **Mihai** » 15 Feb 2010, 22:14

Fiind foarte pasionat de numere [probabil, prietenii l-ar considera un ciudat - daca ar avea vreunul], George se intreaba ce procent din numerele naturale din intervalul inchis [1,N] (1<N<=2.000.000) sunt prime. Puteti sa-l ajutati ?

Exemplu:
Pentru N=15, numerele prime din intervalul [1,15] sunt: 2 3 5 7 11 13. In total, sunt 6 numere, deci se va afisa "40.00 %".

Atentie!
Intre numarul obtinut si simbolul "%", se va lasa un spatiu;
Rezultatul va fi afisat totdeauna cu 2 zecimale (sau mai mult);
Pentru a fi considerat corect, diferenta dintre rezultatul generat de program si cel corect trebuie sa fie, in modul, mai mica de 0.01;
Citirea lui N se va face din fisierul "bitcell3.in" iar afisarea rezultatului se va face in fisierul "bitcell3.out", in vederea evaluarii automate.

Durata:
15-20 Februarie - inscrierea in concurs
21 Februarie - declararea castigatorului

L.E.: Am modificat. Oboseala isi face simtit efectul. Daca mai gasiti lucruri in neregula, va rog nu mai postati in topicul concursului ci dati mesaj privat unuia dintre moderatori, pentru ca se face offtopic inutil, si vor fi mai greu de urmarit posturile cu adevarat importante.

by **andreiandreiq** » 18 Feb 2010, 18:26

Bitcell3.out trebuie sa contina si numerele care sunt prime sau doar procentul ?

by **Mihai** » 19 Feb 2010, 13:46

Doar procentul.

by **Wardog** » 19 Feb 2010, 20:43

Particip eu, desi nu sunt prea multumit de rezolvarea gasita. Am incercat sa implementez ceva operatii pe biti pentru reducerea consumului de memorie, dar nu am reusit. Niciodata nu am inteles operatiile pe biti.

Programul e in atasament.

Later edit: Se pare ca nu pot folosi functia Private Message. Cum procedez cu sursa atunci? Pun linkul aici?

by **DarkByte** » 20 Feb 2010, 01:16

Sursa o vei pune la sfarsitul concursului, cand trage Mihai alarma

P.S. Contributia mea la concurs - in atasament.

by **v0id** » 20 Feb 2010, 17:57

Programul meu: in atasament.

L.E.: A trebuit sa-l corectez pt. ca n-am fost atent la enunt... In loc de "<= 2.000.000", eu am considerat "< 2.000.000". Asta e, unii inca mai sunt obisnuiti ca la matematica, sa lase un patratel inainte si dupa operatori ca sa fie mai citet, iar orice alta forma de scriere este "parsata" gresit

Noul executabil in atasament.
Multumesc lui DarkByte ca mi-a atras atentia.

by **andreiandreiq** » 20 Feb 2010, 21:39

Programul meu: in atasament.

by **Dexter** » 20 Feb 2010, 23:16

Hop şi eu pe ultima sută de metri...

(in atasament)

by **Mihai** » 21 Feb 2010, 12:38

@WarDog: posteaza te rog sursa.

by **Wardog** » 21 Feb 2010, 16:42

Line number On/Off | Expand/Contract | Select all

#include <fstream>
#include <iomanip>
 
using namespace std;
 
ifstream f1 ("bitcell3.in");
ofstream f2 ("bitcell3.out");
 
int v[2000000];
long long n;
float p;
 
void citire ()
{
    f1>>n;
    f1.close ();
}
 
void ciur ()
{
    for ( int i = 0; i < n; i++ )
    {
        v[i] = 1;
    }
    for( int i = 2;i*i <= n; i++ )
    {
        if(v[i]==1) 
            for ( int j = 2; j*i <= n; j++ ) 
                v[i*j]=0;
    }
 
}
 
void rezolvare ()
{
    for ( int i = 2; i <= n; i++ )
    {
        if ( v[i] ) p++;
    }
 
    p = (p/n)*100;
 
    f2<<setprecision(4)<<p<<" "<<"%"<<endl;
    f2.close ();
}
 
int main ()
{
    citire ();
    ciur ();
    rezolvare ();
    return 0;
}

by **Mihai** » 21 Feb 2010, 19:52

Castigatorul concursului este Dexter. Implementarea ciurului este foarte rapida multumita operatiilor pe biti.
Au mai fost si alte implementari de ciur (v0id si wardog, daca nu ma insel) insa au fost ceva mai lente. DarkByte a venit cu o solutie destul de rapida bazata pe factorizare.
Cea mai lenta solutie este cea a lui andreiandreiq, care testeaza pentru fiecare numar din intervalul [1,N] daca este prim.
In continuare, puteti vedea sursele:

DarkByte:

Line number On/Off | Expand/Contract | Select all

program bitcell3;
 
{$APPTYPE CONSOLE}
 
uses SysUtils, Windows;
 
const LookupPrime : array [1..332] of Word = // pre-generated lookup table
      (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89,
       97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191,
       193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293,
       307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
       421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
       547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653,
       659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787,
       797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919,
       929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033,
       1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129,
       1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249,
       1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367,
       1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481,
       1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579,
       1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693,
       1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801,
       1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931,
       1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039,
       2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143,
       2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237);
 
  _FinishMessage = 'Press Enter to finish the program ...';
 
var nStart, nFinish, prCounter, prim: Longint;
    tDurata: Cardinal;
 
procedure ReadFile; // input
var fPrime: TextFile;
    fName: String;
begin
  nStart := 1;
 
  fName := ExtractFilePath(ParamStr(0)) + 'bitcell3.in';
  if FileExists(fName) then
    begin
      try
        AssignFile(fPrime, fName);
        try
          ReSet(fPrime);
          Read(fPrime, nFinish);
          if (nFinish < 2) or (nFinish > 2000000) then
            begin
              WriteLn('Oopsie daisy ... allowed numbers are between 2 and 2 millions.');
              WriteLn(_FinishMessage);
              ReadLn;
              halt(0);
            end;
        finally
          CloseFile(fPrime);
        end;
      except
        WriteLn('Weird error found : finders keepers !');
        WriteLn(_FinishMessage);
        ReadLn;
      end;
    end
    else
      begin
        WriteLn('Fisierul "bitcell3.in" lipseste !');
        WriteLn(_FinishMessage);
        ReadLn;
        Halt(0);
      end;
end;
 
procedure ComputePrimeNumbers; // calculations
var iCounter, cnt, radNr: Longint;
    ePrim, impar: Boolean;
begin
  prCounter := 0;
 
  prim := 0;
  impar := False;
 
  iCounter := nStart;
  while iCounter <= nFinish do
    begin
      radNr := Round(Sqrt(iCounter));
 
      ePrim := True;
      cnt := 1;
 
      while cnt <= 332 do
        begin
          if LookupPrime[cnt] > radNr
            then Break;
 
          if (iCounter mod LookupPrime[cnt] = 0) then
            begin
              ePrim := False;
              Break;
            end;
          Inc(cnt);
        end;
 
      if ePrim
        then inc(prCounter);
 
      if (not Impar) then
        if Odd(iCounter)
          then Impar := True;
 
      if Impar
        then Inc(iCounter, 2)
        else Inc(iCounter);
    end;
end;
 
procedure WriteFile; // output
var fPrime: TextFile;
    fName: String;
begin
  fName := ExtractFilePath(ParamStr(0)) + 'bitcell3.out';
  try
    AssignFile(fPrime, fName);
    try
      ReWrite(fPrime);
      Write(fPrime, ((prCounter * 100) / nFinish) : 7 : 5); // writing the percentage
      Write(fPrime, ' %');
    finally
      CloseFile(fPrime);
    end;
  except
    WriteLn('Weird error found : finders keepers !');
    WriteLn(_FinishMessage);
    ReadLn;
  end;
 
  fName := ExtractFilePath(ParamStr(0)) + 'bitcell3.exec';
  try
    AssignFile(fPrime, fName);
    try
      ReWrite(fPrime); // logging the program's duration
      Write(fPrime, 'Calculations done in ' + IntToStr(tDurata) + ' milliseconds.');
    finally
      CloseFile(fPrime);
    end;
  except
    WriteLn('Weird error found : finders keepers !');
    WriteLn(_FinishMessage);
    ReadLn;
  end;
end;
 
begin
  ReadFile;
 
  tDurata := GetTickCount;           // computing's start time
  ComputePrimeNumbers;
  tDurata := GetTickCount - tDurata; // computing's duration
 
  WriteFile;
end.

v0id:

Line number On/Off | Expand/Contract | Select all

unit frmMain;
 
interface
 
uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;
 
type
  TFormMain = class(TForm)
    btnCalculate: TButton;
    lblN: TLabel;
    lblResultsTop: TLabel;
    memResults: TMemo;
    procedure btnCalculateClick(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;
 
 
  TPrimes = class(TObject)
  private
    FNotPrimes: TBits;
    FMaxNo: integer;
  public
    constructor Create(aMaxNo: integer);
    destructor Destroy; override;
    function IsItPrime(aNumber: integer) : boolean;
  end;
 
var
  FormMain: TFormMain;
 
const
  FILENAME_INPUT = 'bitcell3.in';
  FILENAME_OUTPUT = 'bitcell3.out';
 
implementation
 
{$R *.dfm}
 
//---------------------------------TPrimeNumbers--------------------------------
constructor TPrimes.Create(aMaxNo: integer);
var
  lFirst, lSecond: integer;
begin
  // False = PRIM
  FNotPrimes := TBits.Create;
  FNotPrimes.Size := aMaxNo + 1;
  FMaxNo := aMaxNo;
 
  for lFirst := 2 to FMaxNo div 2 do
    if (not FNotPrimes[lFirst]) then
      begin
        // Numerele pare altele decat 2 nu sunt prime
        if (lFirst <> 2) and ((lFirst mod 2) = 0) then
          Continue;
 
        // Pornire de la al doilea element
        lSecond := lFirst + lFirst;
        while (lSecond <= FMaxNo) do
          begin
            // Nu este prim
            FNotPrimes[lSecond] := True;
            Inc(lSecond, lFirst);
          end;
      end;
 
   // Setare elemente 1 si 2
   FNotPrimes[1] := True;
   FNotPrimes[2] := False;
end;
 
function TPrimes.IsItPrime(aNumber: integer) : boolean;
begin
  Result := not FNotPrimes[aNumber];
end;
 
destructor TPrimes.Destroy;
begin
  FNotPrimes.Free;
  inherited;
end;
 
 
//---------------------------------TFormMain------------------------------------
procedure TFormMain.btnCalculateClick(Sender: TObject);
var
  lTempList: TStringList;
  lPrimeNumbers: TPrimes;
  lInputN: integer;
  lPrimeStr: string;
  lPrimeCount: integer;
  lPercentStr: string;
  iCounter: integer;
begin
  memResults.Clear;
 
  // Verificare daca exista fisierul de intrare
  if (not FileExists(ExtractFilePath(ParamStr(0)) + FILENAME_INPUT)) then
     begin
       MessageDlg('Fisierul de intrare "' + FILENAME_INPUT + '" nu exista!', mtError, [mbOK], 0);
       Exit;
     end;
 
  // TStringList pt. salvare/incarcare fisiere. Religia imi interzice sa folosesc TextFile.
  lTempList := TStringList.Create;
  try
    lTempList.LoadFromFile(ExtractFilePath(ParamStr(0)) + FILENAME_INPUT);
 
    // Verificare daca avem un N valid
    try
      lInputN := StrToInt(lTempList.Strings[0]);
    except
      on E: Exception do
        begin
          if (E is EConvertError)
            then MessageDlg('Fisierul de intrare nu contine un numar!' + E.Message, mtError, [mbOK], 0)
            else MessageDlg('S-a intalnit o exceptie la citirea numarului din fisierul de intrare: ' + E.Message, mtError, [mbOK], 0);
          Exit;
        end;
    end;
 
    // Verificare daca N se incadreaza in conditia 1 < N <= 2.000.000
    if (lInputN < 2) or (lInputN > 2000000) then
      begin
        MessageDlg('Numarul ' + IntToStr(lInputN) + ' nu se incadreaza in conditia 1 < N <= 2.000.000!', mtError, [mbOK], 0);
        Exit;
      end;
 
 
    // In sfarsit procesare...
    lblN.Caption := 'N: ' + IntToStr(lInputN);
    Application.ProcessMessages;
 
    lPrimeStr := EmptyStr;
    lPrimeCount := 0;
    lPrimeNumbers := TPrimes.Create(lInputN);
    try
      for iCounter := 2 to lInputN do
        begin
          if lPrimeNumbers.IsItPrime(iCounter) then
            begin
              if (lPrimeStr = EmptyStr)
                then lPrimeStr := IntToStr(iCounter)
                else lPrimeStr := lPrimeStr + ' ' + IntToStr(iCounter);
              Inc(lPrimeCount);
            end;
        end;
    finally
      FreeAndNil(lPrimeNumbers);
    end;
    lPercentStr := FormatFloat('0.00000000000000000000', lPrimeCount * 100 / (iCounter - 1)) + ' %';
 
    // Adaugare rezultate in TMemo
    memResults.Lines.Add(lPrimeStr + #13#10);
    memresults.Lines.Add('Numere prime gasite: ' + IntToStr(lPrimeCount));
    memResults.Lines.Add('Procent numere prime: ' + lPercentStr);
 
    // Scriere procent in fisier
    lTempList.Clear;
    lTempList.Add(lPercentStr);
    lTempList.SaveToFile(ExtractFilePath(ParamStr(0)) + FILENAME_OUTPUT);
  finally
    FreeAndNil(lTempList);
  end;
end;
 
end.

andreiandreiq

Line number On/Off | Expand/Contract | Select all

uses crt;
var N:1..2000000;
    i:1..2000000;
    procent:real;
    m:1..2000000;
    f,g:text;
  function Esteprim(x:longint):boolean;
  var prim:boolean;
      rad,d:longint;
  begin
    if x=1 then prim:=false
    else if x mod 2=0 then
           if x=2 then prim:=True
           else prim:=false
        else
           begin
             d:=3;
             prim:=true;
             rad:=trunc(sqrt(x));
             while (d<=rad) and prim do
                if x mod d=0 then prim:=false
                else d:=d+2;
           end;
  Esteprim:=prim;
  end;
begin
 
  clrscr;
  assign(f,'bitcell3.in');
  reset(f);
  assign(g,'bitcell3.out');
  rewrite(g);
  readln(f,N);
   if N>2000000 then
   Writeln('Numarul este mai mare de 2 milioane')
   else
   for i:=1 to N do
   begin
      if Esteprim(i)
      then  m:=m+1;
 
    procent:=(100/n)*m;
   end;
    writeln(g,procent:3:2,' %');
 
close(f);
close(g);
end.

Dexter:

Line number On/Off | Expand/Contract | Select all

 
/*
Rezolvarea este bazata pe 'Ciurul lui Eratostene' ( http://ro.wikipedia.org/wiki/Ciurul_lui_Eratostene )
 
*/
 
#include <stdio.h>
#include <math.h> //sqrt
 
#define AFISEAZA_TIMP_EXECUTIE 1
#define FISIER_IN "bitcell3.in"
#define FISIER_OUT "bitcell3.out"
 
#define REGISTER_SIZE (sizeof(int)*8)//marimea unui registru din CPU;
//folosind int-uri cu aceeasi dimensiune ca a registrului,
//vom beneficia de viteza mai mare de acces la nivel de CPU
 
#define getBit(bitfield,i) ((bitfield[(i)/(REGISTER_SIZE)]>>((i)%(REGISTER_SIZE)))&1)
#define setBit(bitfield,i) (bitfield[(i)/(REGISTER_SIZE)]|=(1<<((i)%(REGISTER_SIZE))))
 
int c=0,s=sizeof(int);
 
long int N; //datele de intrare
 
unsigned int*bitField=0;
unsigned int n; //spatiu alocat dinamic
 
//variabile folosite in program
unsigned int i,j,k,bitMask=0,currentBitMask,offset,a,b; 
unsigned int*p,*stop;
 
FILE*f;
 
#if AFISEAZA_TIMP_EXECUTIE 
#include <time.h>
time_t start_t,stop_t;
#endif/*
void afiseaza_biti(int integer)
{
    int bit,i;
    for(i=0;i<REGISTER_SIZE;i++){
        bit=(integer>>(i%(REGISTER_SIZE)))&1;
        printf("%d ",bit);
    }
}*/
 
int main(){
#if AFISEAZA_TIMP_EXECUTIE 
    start_t=clock();
#endif
    
/*  
    freopen("bitcell3.in","r",stdin);
    //freopen("bitcell3.out","w",stdout);
    scanf("%d",N);
*/
    f=fopen("bitcell3.in","r");
    if(!f) return 1; //lipseste fisierul de intrare
    fscanf(f,"%ld",&N);
    fclose(f);
    
    //conditii preliminare
    if(N<0||N>2000000)
    {
        puts("-1");//input invalid
        return 1;
    }
    if(N<2)
    {
        puts("0");//zero
        return 0;
    }
    
    //alocam pana la 2 000 000 biti, cate unul pentru fiecare numar de la 1 la 2 000 000
    //bitul i va fi 1 daca numarul i nu este prim, iar 0 daca
    
    n=N/REGISTER_SIZE; //alocam spatiu pentru cei N biti
    if(N%REGISTER_SIZE)n++; //rotunjind prin adaos, la urmatorul int
    
    bitField=new unsigned int[n];//alocam spatiul necesar (conform problemei, maxim 250 000 bytes, adica ~244 KB)
    /*
     bitul cel mai nesemnificativ, din bitField[0] corespunde lui 1
    */
    
    //preliminar, excludem numerele pare, initializand vectorul cu bitii 0 si 1, alternativ
    //1)creem o masca de biti cu 0 si 1, de marimea int-ului (16,32,64, sau cine mai stie...)
 
    bitMask=0xAAAA;// 1010 1010
    for(i=16;i<REGISTER_SIZE;i+=16)//din 16 in 16 biti
    {
        bitMask<<=16;
        bitMask|=0xAAAA;// 1010 1010
    }
    
    //2)aplicam masca in tot vectorul, initializandu-l si eliminand numerele pare
 
    p=bitField; //p = cursor
    stop=bitField+n;//stop = pozitia de oprire, la finalul zonei alocate
 
    while(p<stop) //cat timp cursorul nu a ajuns la final,
        *p++=bitMask; //copie int-ul, apoi treci la pozitia urmatoare
    
    //Am folosit implementarea cu pointeri doar pentru a grabi putin executia, la nivel de asamblare
 
    /*
            In vederea implementarii algoritmului, vom lua fiecare numar impar mai mare decat 2
        si vom exclude multiplii sai din lista numerelor prime.
    
        Astfel, la nivel de bit, bitField[i*k]=1, unde k*i reprezinta multiplii lui i
    */
    
    //in momentul de fata, 2 este marcat ca neprim, iar 1 ca prim
    bitField[0]^=3; //corectam printr-o operatie XOR pe biti
    
    unsigned int end=(unsigned int)sqrt((unsigned int)N);
    for(i=3;i<=end;i+=2) //numerele impare din 2 in 2, incepand cu 3...
    {
        if(0==getBit(bitField,i-1)) //daca bitul este zero, adica numarul este prim...
        {
            
            if(i<REGISTER_SIZE)
            {
                /* Observatie:
                    Pentru numerele mai mici decat `REGISTER_SIZE`, se poate crea o masca de biti,
                care aplicata pe bitField cu operatorul |, marcheaza numerele neprime.
                    
                    Exemplu: i=3, REGISTER_SIZE=32
                MSB                                 LSB
                0100 1001 0010 0100 1001 0010 0100 1001
                    
                    Notam:
                reg = REGISTER_SIZE
                i = numarul curent
                n = cmmmc(i,reg)   --cel mai mic multiplu comun
                m = n/reg
                    In masca de biti, la fiecare i biti, se repeta un 1, iar la fiecare n biti se repeta
                alinierea bitilor in int-uri. Am notat cu m = numarul de int-uri dintr-un ciclu complet.
                    Dupa ce am realizat prima masca (unde bitul cel mai nesemnificativ este 1), celelalte
                configuratii le obtinem printr-o rotatie pe biti, la stanga (sunt intotdeauna i configuratii
                diferite).              
                    Astfel: pentru i=3, REGISTER_SIZE=32, avem
                MSB                                  LSB
                0100 1001 0010 0100  1001 0010 0100 1001  -- configuratia 1
                1001 0010 0100 1001  0010 0100 1001 0010  -- configuratia 2
                0010 0100 1001 0010  0100 1001 0010 0100  -- configuratia 3
 
                    Cu un offset corespunzator, fiecare masca, aplicata pe bitField din m in m pozitii,
                va marca automat numerele neprime.
                */
 
                
                bitMask=1;
                for(j=0;j<REGISTER_SIZE/i;j++)//folosim variabila j pentru a adauga bitii de 1
                {
                    bitMask<<=i;
                    bitMask|=1;
                }
                //am creat prima masca de biti, de dimensiunea unui int
                
                /* 
                R=REGISTER_SIZE
                i=numarul prim
                R*a=int-ul pe care aplicam masca (raportat la bitField)
                i*b=primul bit din masca (raportat la bitField)
                X=offsetul bitului de inceput (raportat la bitMask)
                
                avem relatia: R*a+X=i*b, unde:
                -X ia valori de la 1 la i
                -r = constant
                -i = constant
                -a si b sunt variabile, cautam b=f(a)
                
                pentru a de la 0 la i
                    b = (R*a +X)/i  trebuie sa se imparta exact
                */
                
                for(offset=0;offset<i;offset++) //offset = `x` de mai sus
                {
                    for(a=0;a<i;a++)
                        if(!((REGISTER_SIZE*a+offset)%i))
                            break; //l-am gasit pe `a`
                    
                    currentBitMask=bitMask<<((offset+i-1)%i);
                    
                    for(j=0;j*i+a<n;j++)
                        bitField[j*i+a]|=currentBitMask;
                }
                bitField[0]^=1<<(i-1); //repara bitul i (l-am setat la 1 odata cu restul lui bitField)
            }
            else 
            {/* Aici vroiam sa mai fac o optimizare...
                Distanta dintr 2 biti cu valoarea 1 este mai mare decat REGISTER_SIZE, deci avem int-uri neatinse, iar numarul de masti
            diferite este = REGISTER_SIZE. Mai trebuia sa gasesc cate un offset pentru fiecare din mastile acestea si sa le aplic pe bitField,
            ca in liniile de mai sus.
                Din pacate, am ramas la varianta de mai jos:
            */
                for(j=2;j*i<=((unsigned int)N);j++)
                    setBit(bitField,i*j-1);
            }
        }
    }
    f=fopen("bitcell3.out","w");
 
    j=0;
    for(i=0;i<((unsigned int)N);i++){
        if(0==getBit(bitField,i))
            j++;
    }
    
    fprintf(f,"%.3f %%",(((float)j*100)/i));
    fclose(f);
    
#if AFISEAZA_TIMP_EXECUTIE 
    stop_t=clock();
    printf("\n\nExecution time: %f\n",float(stop_t-start_t)/CLK_TCK);
#endif
    return 0;
}
 

Sursa lui wardog o puteti vedea in postul anterior.
Felicitari tuturor participantilor, si asteptam cu totii un nou concurs

!

by **Dexter** » 21 Feb 2010, 20:42

Ca o paranteză...

Mi-au rămas unele linii de cod nefolosite/neşterse în sursa mai sus, şi asta pentru că am amânat rezolvarea problemei până în ultimul moment. După ce voi face ultimele finisaje, varianta finală va putea fi descărcată de aici.

by **v0id** » 21 Feb 2010, 21:11

As avea si eu niste paranteze

(daca nu e OK ca am postat aici, va rog sa-mi spuneti unde ar fi OK)

1. Nu m-am gandit sa pun si eu niste timere ca sa se vada viteza de executie. Am facut-o acum, iar cine e curios poate descarca aceasta varianta din atasament. Minunati-va de overhead-ul adus de afisarea numerelor prime :))

2. Nu pot rula programele lui andreiandreiq si Wardog pe Windows 7 x64. Al lui andreiandreiq imi da eroarea asta, iar al lui Wardog imi da asta. Imi amintesc si de programul lui Archangel de la concursul precedent, care imi dadea aceeasi eroare ca al lui Wardog... Acel program l-am testat pe vreo 4 masini si abia pe a 5-a masina mi-a mers. Acum daca stau sa-mi aduc aminte, primele 4 masini aveau toate Windows x64 instalat, iar a 5-a era avea Windows x86.
Se pune intrebarea: programele compilate de voi nu merg pe platforme x64? Asta mi s-ar parea mult prea tare

As fi curios daca mai poate confirma cineva treaba asta...

by **Mihai** » 21 Feb 2010, 22:11

@Dexter:
Ma bucur ca ai reusit sa-l termini la timp. Scuze ca nu ti-am raspuns la PM-ul ala, dar eram plecat.
@void:
Intr-adevar, afisarea numerelor prime ingreuneaza foarte mult executia programului tau.
Cat despre programul lui Wardog, nici mie nu mi-a mers - de asta i-am si cerut sursa

.
Oricum, eu am Windows x86, dar banuiesc ca e vorba de vreo dependinta.
@WarDog: In ce ai scris programul

?

by **Wardog** » 21 Feb 2010, 22:44

Mihai wrote:@Dexter:
Ma bucur ca ai reusit sa-l termini la timp. Scuze ca nu ti-am raspuns la PM-ul ala, dar eram plecat.
@void:
Intr-adevar, afisarea numerelor prime ingreuneaza foarte mult executia programului tau.
Cat despre programul lui Wardog, nici mie nu mi-a mers - de asta i-am si cerut sursa .
Oricum, eu am Windows x86, dar banuiesc ca e vorba de vreo dependinta.
@WarDog: In ce ai scris programul ?

Programul l-am compilat in Visual C++ 2008. Incerc sa il compilez si in Borland C++ si il pun aici, doar asa sa vad daca este vina compilatorului.
Later edit: in atasament.

by **andreiandreiq** » 21 Feb 2010, 23:42

@Wardog : acuma merge programul
PS. @Dexter: te asteptam maine cu noul concurs:P

by **DarkByte** » 22 Feb 2010, 00:43

v0id wrote:... Imi amintesc si de programul lui Archangel de la concursul precedent, care imi dadea aceeasi eroare ca al lui Wardog... Acel program l-am testat pe vreo 4 masini si abia pe a 5-a masina mi-a mers. Acum daca stau sa-mi aduc aminte, primele 4 masini aveau toate Windows x64 instalat, iar a 5-a era avea Windows x86.
Se pune intrebarea: programele compilate de voi nu merg pe platforme x64? Asta mi s-ar parea mult prea tare As fi curios daca mai poate confirma cineva treaba asta ...

Programul lui Archangel a mers pe calculatorul meu "main" de la birou, dude. Vista x65-1 ...

In alta ordine de idei, felicitari participantilor si, evident, lui Dexter

Imi place varietatea ideilor si a codului, keep 'em coming

P.S. Dexter, daca ne pui sa facem ceva soft de ghidare rachete, I'll pass

by **v0id** » 22 Feb 2010, 10:59

"Dude", nu stiu eu ce teste ai facut tu la birou pe programul lui Archangel.
Daca poti veni cu ceva constructiv ca oamenii sa se lamureasca de ce nu le merg programele compilate, cu atat mai bine. Deci... Din ce spuneti tu si Mihai, problema nu tine de platforma x64. Foarte bine atunci, era doar o presupunere de-a mea. Oricum, o problema clar exista, deci distractie placuta la gasirea si rezolvarea ei!

BitCell

[3] Concurs - Numere prime

[3] Concurs - Numere prime

Re: [3] Concurs - Numere prime

Re: [3] Concurs - Numere prime

Re: [3] Concurs - Numere prime

Re: [3] Concurs - Numere prime

Re: [3] Concurs - Numere prime

Re: [3] Concurs - Numere prime

Re: [3] Concurs - Numere prime

Re: [3] Concurs - Numere prime

Re: [3] Concurs - Numere prime

Re: [3] Concurs - Numere prime

Re: [3] Concurs - Numere prime

Re: [3] Concurs - Numere prime

Re: [3] Concurs - Numere prime

Re: [3] Concurs - Numere prime

Re: [3] Concurs - Numere prime

Re: [3] Concurs - Numere prime

Re: [3] Concurs - Numere prime

Who is online