lib_3np1_mod__inline.hpp

Go to the documentation of this file.

/* -*- coding: latin-1 -*- */
/** \file lib_3np1_mod__inline.hpp
 *
 * Piece of severalgos.
 * https://bitbucket.org/OPiMedia/severalgos
 *
 * GPLv3 --- Copyright (C) 2015 Olivier Pirson
 * http://www.opimedia.be/
 */

#include <cassert>

#include <limits>



namespace lib_3np1_mod {

/* ***********
 * Functions *
 *************/
inline
value_type
C(value_type n) {
  assert(n <= (std::numeric_limits<value_type>::max() - 1)/3);

  return ((n & 1) == 0
          ? n >> 1     // even
          : n*3 + 1);  // odd
}


inline
value_type
C_mask(value_type n, value_type mask) {
  assert(n <= mask);

  return ((n & 1) == 0
          ? n >> 1              // even
          : (n*3 + 1) & mask);  // odd
}


inline
value_type
F(value_type n) {
  assert(n <= (std::numeric_limits<value_type>::max() - 1)/3);

  if ((n & 1) != 0) {  // odd
    n = n*3 + 1;
  }

  return (n != 0
          ? n >> m2(n)
          : 0);
}


inline
value_type
F_mask(value_type n, value_type mask) {
  assert(n <= mask);

  if ((n & 1) != 0) {  // odd
    n = (n*3 + 1) & mask;
  }

  return (n != 0
          ? n >> m2(n)
          : 0);
}


inline
value_type
m2(value_type n) {
  assert(n != 0);
  assert(std::numeric_limits<value_type>::digits
         <= std::numeric_limits<unsigned long long>::digits);  // NOLINT

  return __builtin_ctzll(n);
}


inline
value_type
T(value_type n) {
  assert(n <= (std::numeric_limits<value_type>::max() - 1)/3);

  return ((n & 1) == 0
          ? n               // even
          : n*3 + 1) >> 1;  // odd
}


inline
value_type
T_mask(value_type n, value_type mask) {
  assert(n <= mask);

  return ((n & 1) == 0
          ? n                        // even
          : (n*3 + 1) & mask) >> 1;  // odd
}

}  // namespace lib_3np1_mod