divisors__inline.hpp

Go to the documentation of this file.

/* -*- coding: latin-1 -*- */
/** \file common/sigmaodd/divisors__inline.hpp (January 7, 2018)
 *
 * GPLv3 --- Copyright (C) 2017, 2018 Olivier Pirson
 * http://www.opimedia.be/
 */

#ifndef PROGS_SRC_COMMON_SIGMAODD_DIVISORS__INLINE_HPP_
#define PROGS_SRC_COMMON_SIGMAODD_DIVISORS__INLINE_HPP_

// \cond
#include <cassert>
#include <cstring>  // for ffsl, https://linux.die.net/man/3/ffs

#include <utility>
// \endcond


namespace sigmaodd {

  /* ********
   * Struct *
   **********/
  constexpr
  bool
  FactorExp::operator==(const FactorExp &other) const {
    return (factor == other.factor) && (exp == other.exp);
  }


  constexpr
  nat_type
  FactorExp::value() const {
    return pow_nat(factor, exp);
  }



  /* *********************
   * constexpr functions *
   ***********************/

  constexpr
  nat_type
  gcd(nat_type a, nat_type b) {
    while (b != 0) {
      const nat_type m = a % b;

      a = b;
      b = m;
    }

    return a;

    /*
      "We might call Euclid's method the granddaddy of all algorithms,
      because it is the oldest nontrivial algorithm that has survived to the present day."
      (Donald E. Knuth.
      The Art of Computer Programming, Volume 2: Seminumerical Algorithms. 3rd 1997)
    */
  }


  constexpr
  nat_type
  is_coprime(nat_type a, nat_type b) {
    return (gcd(a, b) == 1);
  }


  constexpr
  bool
  is_divide(nat_type d, nat_type n) {
    assert(d != 0);

    return n % d == 0;
  }


  constexpr
  bool
  is_first_mersenne_prime_unitary_divide(nat_type n) {
    return (is_unitary_divide(3, n)
            || is_unitary_divide(7, n)
            || is_unitary_divide(31, n)
            || is_unitary_divide(127, n));
  }


  constexpr
  bool
  is_first_mersenne_prime_unitary_divide_or_square(nat_type n) {
    return is_first_mersenne_prime_unitary_divide(n) || is_square(n);
  }


  constexpr
  bool
  is_little_mersenne_prime_unitary_divide(nat_type n) {
    return (is_first_mersenne_prime_unitary_divide(n)
            || is_unitary_divide(8191, n)
            || is_unitary_divide(131071, n)
            || is_unitary_divide(524287, n));
  }


  constexpr
  bool
  is_mersenne_prime_unitary_divide(nat_type n) {
    return (is_little_mersenne_prime_unitary_divide(n)
            || is_unitary_divide(2147483647u, n)
            || is_unitary_divide(2305843009213693951u, n));
  }


  constexpr
  bool
  is_unitary_divide(nat_type d, nat_type n) {
    assert(d != 0);

    return is_divide(d, n) && !is_divide(d, n/d);
  }



  /* ******************
   * inline functions *
   ********************/

  inline
  nat_type
  divide_until_odd(nat_type n) {
    assert(n != 0);

    // https://linux.die.net/man/3/ffs
    return n >> (static_cast<unsigned int>(ffsl(static_cast<long int>(n))) - 1);
  }


  inline
  std::pair<nat_type, unsigned int>
  divide_until_odd_nb(nat_type n) {
    assert(n != 0);

      // https://linux.die.net/man/3/ffs
    const unsigned int alpha = static_cast<unsigned int>(ffsl(static_cast<long int>(n))) - 1;

    return std::make_pair(n >> alpha, alpha);
  }

}  // namespace sigmaodd

#endif  // PROGS_SRC_COMMON_SIGMAODD_DIVISORS__INLINE_HPP_