1
\$\begingroup\$

I followed your answers for my last questions (1st 2nd) and I came up with these new versions of my codes but I face some difficulties to measure the efficiency of my code, I use chrono library to determine the run time, and of course it does not give a full description of the efficiency of the code.

How can I do the benchmarking?

Are there any comments on the new versions of the codes?

/* 
This program generates all primes numbers up to a given limit where all multiples of 2, 3 and 5 are pre-eliminated.
They don't take any memory to be stored, or time to be eliminated.
It follows the concept of the wheel of prime numbers where 2, 3 and 5 are our basis
*/

#include <iostream>
#include<cmath>
#include <chrono>
#include<vector>
using namespace std::chrono;



void wheel_Sieve2(unsigned int Limit, unsigned int N, std::vector<char>& sieve)
{

     int position [8] = { -1 , 23, 19, 17, 13, 11, 7, 1 };

     unsigned int start[8][8] = { {0,6,10,12,16,18,22,28} ,  {0,4,6,10,12,16,22,24} ,
                                  {0,2,6,8,12,18,20,26}   ,  {0,4,6,10,16,18,24,28} ,
                                  {0,2,6,12,14,20,24,26}  ,  {0,4,10,12,18,22,24,28}, 
                                  {0,6,8,14,18,20,24,26}  ,  {0,2,8,12,14,18,20,24}  };
    
      for (unsigned int primes_order = 1; primes_order <= ceil((8 * (ceil((9 * floor(sqrt(N) / 3.0) - 8) / 10.0)) - 1) / 9.0); primes_order++)
    {
        unsigned int primes = 2 * (floor((3 * floor((10 * floor((9 * primes_order + 1) / 8.0) + 8) / 9.0) + 1) / 2.0)) + 1;

        unsigned int multiples_period = ceil((8 * (ceil((9 * floor(30 * primes  / 3.0) - 8) / 10.0)) - 1) / 9.0);

        unsigned int multiples_start = primes * primes;

        if (sieve[primes_order]==true)
        {
                for (unsigned int position_check = 0; position_check < 8; position_check++)
                {
                    if ((multiples_start + primes * position[position_check]) % 30 == 0)
                    {
                        for (unsigned int start_positions = 0; start_positions < 8; start_positions++)
                        {
                            unsigned int multiples_start_order = ceil((8 * (ceil((9 * floor( (multiples_start + primes * start[position_check][start_positions]) / 3.0) - 8) / 10.0)) - 1) / 9.0) ;
                           
                            for (unsigned int multiples_sieve = multiples_start_order; multiples_sieve < Limit; multiples_sieve += multiples_period)
                            {
                                sieve[multiples_sieve] = false; 
                            }
                        }
                        break;
                    }
                }
        }
    }
}

int main()
{
    unsigned int N = 0, Limit = 0;
    std::cout << "Enter limit : ";
    std::cin >> N;
    Limit = ceil((8 * (ceil((9 * floor(N / 3.0) - 8) / 10.0)) - 1) / 9.0);
    
    std::vector <char> sieve(Limit+1,true);

    auto start = steady_clock::now();

    wheel_Sieve2(Limit, N,sieve);

    auto stop = steady_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    std::cout << "Run time is : " << duration.count() << std::endl;

    // printing primes.
       std::cout << " 2 3 5 ";
         for (unsigned int primes_order = 1; primes_order <= Limit; primes_order++)
             if (sieve[primes_order]==true)
                 std::cout << 2 * (floor((3 * floor((10 * floor((9 * primes_order + 1) / 8.0) + 8) / 9.0) + 1) / 2.0)) + 1 << " ";

    return 0;
}
/*
This program generates all primes numbers up to a given limit where all multiples of 2 and 3 are pre-eliminated.
They don't take any memory to be stored, or time to be eliminated.
It follows the concept of the wheel of prime numbers where 2 and 3 are our basis.
*/

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

using namespace std::chrono;


void Wheel_Sieve1(unsigned int Limit, unsigned int N, std::vector<char>& sieve)
{
    int position[2] = { 1, -1 };

    int start[2] =  { 2 , 4 } ;

    for (unsigned int primes_order = 1; primes_order <= sqrt(N) / 3 ; primes_order++)
    {
        if (sieve[primes_order] == true)
        {  

                unsigned int primes = 2 * (floor(((3 * primes_order) + 1) / 2.0)) + 1;

                unsigned int multiples_start = primes * primes ;

                unsigned int multiples_period = (6 * primes) / 3;

                for (unsigned int multiples_sieve = multiples_start/3; multiples_sieve < Limit; multiples_sieve += multiples_period)
                {
                    sieve[multiples_sieve] = false;
                }

                for (unsigned int position_check = 0; position_check < 2; position_check++)
                {
                    if ((multiples_start + primes * position[position_check]) % 6 == 0)
                    {                            
                            for (unsigned int multiples_sieve = (multiples_start + primes * start[position_check]) / 3; multiples_sieve < Limit; multiples_sieve += multiples_period)
                            {
                                sieve[multiples_sieve] = false;
                            }
                    }
                }
        }
    }
}

int main()
{
    unsigned int N = 0, Limit = 0;

    std::cout << "Enter limit : ";
    std::cin >> N;
    Limit = N / 3;

    std::vector<char> sieve(Limit, true);

    auto start = steady_clock::now();
  
    Wheel_Sieve1(Limit, N, sieve);

    auto stop = steady_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    std::cout <<"Run time is : "<< duration.count() << std::endl;
  
    // printing primes
    std::cout <<"Prime numbers are :"<< "\n" << " 2 3 ";
    for (unsigned int prime_number = 1; prime_number < Limit; prime_number++)
        if (sieve[prime_number] == true)
            std::cout << 2 * (floor((3 * prime_number + 1) / 2.0)) + 1 << " ";
    return 0;
}
\$\endgroup\$
1

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.