benchmarks.cpp

Go to the documentation of this file.

/* -*- coding: latin-1 -*- */
/** \file common/benchmarks.cpp (January 5, 2018)
 * \brief
 * Some benchmarks for the sigma_odd problem.
 *
 * GPLv3 --- Copyright (C) 2017, 2018 Olivier Pirson
 * http://www.opimedia.be/
 */

// \cond
#include <cstdlib>

#include <algorithm>
#include <chrono>
#include <iostream>
// \endcond

#include "helper/helper.hpp"
#include "sigmaodd/pentagonal.hpp"
#include "sigmaodd/primes.hpp"
#include "sigmaodd/sigmaodd.hpp"



/* ***********
 * Prototype *
 *************/

void
help_and_exit();



/* **********
 * Function *
 ************/

void
help_and_exit() {
  std::cerr << "Usage: benchmarks [option]" << std::endl
            << std::endl
            << "Option:" << std::endl
            << "  --nb -n   number of odd numbers to check by range (100 by default)" << std::endl;

  exit(EXIT_FAILURE);
}



/* ******
 * Main *
 ********/

int
main(int argc, const char* const argv[]) {
  // Load primes table
  if (!sigmaodd::read_primes_table()) {
    std::cerr << "! Impossible to load \"" << sigmaodd::prime_filename << '"' << std::endl
              << std::endl;
    help_and_exit();
  }


  std::srand(666);  // to have deterministic "random" numbers

  sigmaodd::nat_type nb = 100;

  // Read command line parameters
  for (unsigned int i = 1; i < static_cast<unsigned int>(argc); ++i) {
    const std::string param(argv[i]);

    if (param == "--nb") {
      nb = helper::get_ulong(argc, argv, ++i, &help_and_exit);;
    }
    else {
      help_and_exit();
    }
  }


  // Print intern configuration
  helper::print_intern_config_compiler();


  // Print parameter
  std::cout << "Nb: " << nb << std::endl;


  // Print table legend
  std::cout << std::endl
            << "First n\tLast n\tNb\tNaive\tFactorize\tFactorize bound\tEuler"
            << std::endl;
  std::cout.flush();


  // Main calculation
  const sigmaodd::nat_type firsts[] = {3,
                                       11,
                                       101,
                                       1001,              // 10^3  =                 1,000
                                       10001,
                                       100001,
                                       1000001,           // 10^6  =             1,000,000
                                       10000001,
                                       100000001,
                                       1000000001,        // 10^9  =         1,000,000,000
                                       10000000001,
                                       100000000001,
                                       1000000000001,     // 10^12 =     1,000,000,000,000
                                       10000000000001,
                                       100000000000001,
                                       1000000000000001,  // 10^15 = 1,000,000,000,000,000
                                       10000000000000001};
  const unsigned int firsts_nb = sizeof(firsts)/sizeof(sigmaodd::nat_type);

  std::chrono::duration<double> total_duration = std::chrono::duration<double>(0);

  for (sigmaodd::nat_type i = 0; i < firsts_nb; ++i) {
    const sigmaodd::nat_type first = firsts[i];
    const sigmaodd::nat_type last = (i + 1 < firsts_nb
                                     ? std::min(firsts[i + 1] - 2, first + (nb - 1)*2)
                                     : first + nb*2);
    const sigmaodd::nat_type current_nb = (last - first)/2 + 1;

    // Coefficient to convert seconds -> microseconds and divide by #
    const unsigned int repeat = (last < 100000
                                 ? 10000
                                 : 1);
    const double duration_coef = 1000000.0;

    assert(sigmaodd::is_odd(first));
    assert(sigmaodd::is_odd(last));

    std::cout << first << '\t' << last << '\t' << current_nb;
    std::cout.flush();

    // Naive
    if (first <= 100000000000000) {  // 10^14 = 100,000,000,000,000
      sigmaodd::nat_type real_nb = 0;
      const std::chrono::steady_clock::time_point clock_start = std::chrono::steady_clock::now();

      for (unsigned int k = 0; k < repeat; ++k) {
        for (sigmaodd::nat_type n = first; n <= last; n += 2) {
          if (sigmaodd::is_little_mersenne_prime_unitary_divide(n)) {
            continue;
          }

          ++real_nb;

#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-but-set-variable"
          volatile const std::pair<sigmaodd::nat_type, unsigned int> result_length
            = sigmaodd::sum_odd_divisors_divided_until_odd_iterate_until_lower__naive(n);
#pragma GCC diagnostic pop
        }
      }

      const std::chrono::duration<double> duration = std::chrono::steady_clock::now() - clock_start;

      std::cout << '\t' << duration.count()*duration_coef/static_cast<double>(real_nb);
      total_duration += duration;
    }
    else {
      std::cout << '\t';
    }
    std::cout.flush();

    // Factorize
    {
      sigmaodd::nat_type real_nb = 0;
      const std::chrono::steady_clock::time_point clock_start = std::chrono::steady_clock::now();

      for (unsigned int k = 0; k < repeat; ++k) {
        for (sigmaodd::nat_type n = first; n <= last; n += 2) {
          if (sigmaodd::is_little_mersenne_prime_unitary_divide(n)) {
            continue;
          }

          ++real_nb;

#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-but-set-variable"
          volatile const std::pair<sigmaodd::nat_type, unsigned int> result_length
            = sigmaodd::sum_odd_divisors_divided_until_odd_iterate_until_lower__factorize(n);
#pragma GCC diagnostic pop
        }
      }

      const std::chrono::duration<double> duration = std::chrono::steady_clock::now() - clock_start;

      std::cout << '\t' << duration.count()*duration_coef/static_cast<double>(real_nb);
      total_duration += duration;
    }
    std::cout.flush();

    // Factorize bound
    {
      sigmaodd::nat_type real_nb = 0;
      const std::chrono::steady_clock::time_point clock_start = std::chrono::steady_clock::now();

      for (unsigned int k = 0; k < repeat; ++k) {
        for (sigmaodd::nat_type n = first; n <= last; n += 2) {
          if (sigmaodd::is_little_mersenne_prime_unitary_divide(n)) {
            continue;
          }

          ++real_nb;

#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-but-set-variable"
          volatile const std::pair<sigmaodd::nat_type, unsigned int> result_length
            = sigmaodd::sum_odd_divisors_divided_until_odd_iterate_until_lower__factorize_bound(n);
#pragma GCC diagnostic pop
        }
      }

      const std::chrono::duration<double> duration = std::chrono::steady_clock::now() - clock_start;

      std::cout << '\t' << duration.count()*duration_coef/static_cast<double>(real_nb);
      total_duration += duration;
    }

    // Euler
    if (sigmaodd::sum_divisors__euler_cache_nb() == 0) {
      sigmaodd::nat_type real_nb = 0;
      const std::chrono::steady_clock::time_point clock_start = std::chrono::steady_clock::now();

      for (unsigned int k = 0; k < repeat; ++k) {
        for (sigmaodd::nat_type n = first; n <= last; n += 2) {
          if (sigmaodd::is_little_mersenne_prime_unitary_divide(n)) {
            continue;
          }

          ++real_nb;

#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-but-set-variable"
          volatile const std::pair<sigmaodd::nat_type, unsigned int> result_length
            = sigmaodd::sum_odd_divisors_divided_until_odd_iterate_until_lower__euler(n);
#pragma GCC diagnostic pop
        }
      }

      const std::chrono::duration<double> duration = std::chrono::steady_clock::now() - clock_start;

      std::cout << '\t' << duration.count()*duration_coef/static_cast<double>(real_nb);
      total_duration += duration;
    }

    std::cout << std::endl;
  }

  std::cerr << "Total duration (for all calculation): "
            << helper::duration_to_string(total_duration)
            << std::endl;

  return EXIT_SUCCESS;
}