lib_3np1_mod.cpp

Go to the documentation of this file.

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

#include <iostream>
#include <limits>
#include <set>
#include <unordered_set>
#include <vector>

#include "lib_3np1_mod.hpp"



namespace lib_3np1_mod {

std::set<value_type>
search_mask_exceptions(value_type mask) {
  if (mask == 4294967295u) {
    return search_mask_exceptions_32();
  } else if (mask == 18446744073709551615ull) {
    return search_mask_exceptions_64();
  }

#ifndef NVERBOSE
  const value_type verbose_mask(mask > (static_cast<value_type>(1) << 26) - 1
                                ? (static_cast<value_type>(1) << 26) - 1
                                : 0);
#endif

  std::set<value_type> exceptions;
  std::unordered_set<value_type> visited_values;

  exceptions.insert(0);

#ifndef NVERBOSE
  if (verbose_mask != 0) {
    std::cerr << '[';
    std::cerr.flush();
  }
#endif

  for (value_type start_n(1); start_n <= mask; start_n += 2) {
    value_type n(start_n);

#ifndef NVERBOSE
    if ((start_n & verbose_mask) == 1) {
      std::cerr << ' ' << start_n;
      std::cerr.flush();
    }
#endif

    do  {
      assert((n & 1) != 0);

      n = (n*3 + 1) & mask;
      if (n != 0) {
        n >>= m2(n);

        if (!visited_values.insert(n).second) {
          n = 0;
        }
      }
    } while (n > start_n);

    visited_values.clear();

    if (exceptions.find(n) != exceptions.cend()) {
      exceptions.insert(start_n);

#ifndef NVERBOSE
      std::cerr << "* Exception: " << start_n << "*";
      std::cerr.flush();
#endif
    }
  }

#ifndef NVERBOSE
  if (verbose_mask != 0) {
    std::cerr << ']' << std::endl;
    std::cerr.flush();
  }
#endif

  return exceptions;
}


std::set<value_type>
search_mask_exceptions_32() {
  assert(std::numeric_limits<value_type>::digits >= 32);

#ifndef NVERBOSE
  const value_type verbose_mask((static_cast<value_type>(1) << 26) - 1);
#endif

  std::set<value_type> exceptions;
  std::unordered_set<value_type> visited_values;

  exceptions.insert(0);

#ifndef NVERBOSE
  std::cerr << '[';
  std::cerr.flush();
#endif

  for (uint32_t start_n(3); start_n != 1; start_n += 2) {
    uint32_t n(start_n);

#ifndef NVERBOSE
    if ((start_n & verbose_mask) == 1) {
      std::cerr << ' ' << start_n;
      std::cerr.flush();
    }
#endif

    do  {
      assert((n & 1) != 0);

      n = n*3 + 1;
      if (n != 0) {
        n >>= m2(n);

        if (!visited_values.insert(n).second) {
          n = 0;
        }
      }
    } while (n > start_n);

    visited_values.clear();

    if (exceptions.find(n) != exceptions.cend()) {
      exceptions.insert(start_n);

#ifndef NVERBOSE
      std::cerr << "* Exception: " << start_n << "*";
      std::cerr.flush();
#endif
    }
  }

#ifndef NVERBOSE
  std::cerr << ']' << std::endl;
  std::cerr.flush();
#endif

  return exceptions;
}


std::set<value_type>
search_mask_exceptions_64() {
  assert(std::numeric_limits<value_type>::digits >= 64);

#ifndef NVERBOSE
  const value_type verbose_mask((static_cast<value_type>(1) << 26) - 1);
#endif

  std::set<value_type> exceptions;
  std::unordered_set<value_type> visited_values;

  exceptions.insert(0);

#ifndef NVERBOSE
  std::cerr << '[';
  std::cerr.flush();
#endif

  for (uint64_t start_n(3); start_n != 1; start_n += 2) {
    uint64_t n(start_n);

#ifndef NVERBOSE
    if ((start_n & verbose_mask) == 1) {
      std::cerr << ' ' << start_n;
      std::cerr.flush();
    }
#endif

    do  {
      assert((n & 1) != 0);

      n = n*3 + 1;
      if (n != 0) {
        n >>= m2(n);

        if (!visited_values.insert(n).second) {
          n = 0;
        }
      }
    } while (n > start_n);

    visited_values.clear();

    if (exceptions.find(n) != exceptions.cend()) {
      exceptions.insert(start_n);

#ifndef NVERBOSE
      std::cerr << "* Exception: " << start_n << "*";
      std::cerr.flush();
#endif
    }
  }

#ifndef NVERBOSE
  std::cerr << ']' << std::endl;
  std::cerr.flush();
#endif

  return exceptions;
}


std::vector<value_type>
start_path_mask(value_type n,
                operation_mask_type operation_mask, value_type mask) {
  assert(n <= mask);

  const value_type start_n(n);

  std::vector<value_type> path{n};
  std::unordered_set<value_type> visited_values;

  while ((n >= start_n) && visited_values.insert(n).second) {
    n = operation_mask(n, mask);
      path.push_back(n);
  }

  return path;
}

}  // namespace lib_3np1_mod