OK, thanks for the encouragements. Note that I'm well aware that
I won't solve the Collatz conjecture that way. It is the canvas,
C++ is the picture. Also, I know the standard doesn't speak to
those MSVC artifacts, but if you think they could be better
handled I'm very interested in hearing about that as well.
There are three files; word wrap is off.
Martin
// main.cpp
/* This program searches for a seed value
yielding a Collatz sequence that is long
in relation to the seed's magnitude.
*/
#ifdef _MSC_VER
// "identifier was truncated to '255' characters in the debug information"
#pragma warning(disable: 4786)
#endif
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include "collatztree.h"
using namespace std;
const string KSeqFile = "collatz.txt";
const unsigned KCheckInterval = 10000000;
//-----------------------------------------------
void awaitEnter()
{
char c[2];
cout << "Program finished. Hit <Enter> to close.";
cin.getline(c, 2);
}
bool prompt(const string& message)
{
char c;
cout << message << " (y/n <Enter>) ";
cin >> c;
#ifdef WIN32
cin.ignore(); // Swallow Windows newline's second character.
#endif
cout << '\n';
return c == 'y';
}
bool checkUserBreak()
{ return !prompt("Continue searching?"); }
void writeBest(const CollatzTree::Best& best,
ostream& os, unsigned nodeCount = 0)
{
os << "The best seed found ";
if(nodeCount > 0) os << "among the first " << nodeCount << " nodes ";
os << "is n = " << best.pNode->value
<< "\nwith number of iterations it(n) = " << best.depth
<< "\nand cost c(n) = it(n) / log2(n) = " << best.cost << ".\n";
}
void writeBest(const CollatzTree::Best& best, unsigned nodeCount)
{ writeBest(best, cout, nodeCount); }
void writeSequence(const CollatzTree::Best& best)
{
if(prompt("Write the longest sequence found to " + KSeqFile + "?")) {
ofstream ofs(KSeqFile.c_str());
writeBest(best, ofs);
ofs << '\n';
CollatzTree:
Node pn = best.pNode;
ofs << pn->value;
while(!pn->isRoot()) {
pn = pn->parent;
ofs << ", " << pn->value;
}
ofs << '\n';
}
}
//-----------------------------------------------
int main()
{
CollatzTree ct(writeBest, checkUserBreak, KCheckInterval);
cout << "Building Collatz tree...\n\n" << fixed << setprecision(3);
do ct.addLevel(); while(!ct.isFinished());
writeSequence(ct.getBest());
awaitEnter();
return 0;
}
// end of file ----------------------------------------------------------------
// collatztree.h
#ifndef COLLATZTREE_H
#define COLLATZTREE_H
#include <vector>
#include <list>
#include <utility>
#include <memory>
/* The class CollatzTree creates, level for level, the
tree of terminating Collatz sequences that do not
exceed the range of type unsigned. It also tracks
the seed value n with largest quotient of the number
of iterations from n and log2(n), and periodically
outputs the most expensive seed found so far.
Smaller values are favored in case of equal cost.
The user can interrupt the class' operation.
The possibility of memory exhaustion is ignored.
*/
class CollatzTree {
public:
struct Node;
struct Best;
typedef void (*WriteBest)(const Best&, unsigned nodeCount);
typedef bool (*CheckUserBreak)();
typedef const Node* PNode;
struct Node {
Node(unsigned value, PNode parent);
bool isRoot() const;
unsigned value;
PNode parent;
};
struct Best {
PNode pNode;
unsigned depth;
float cost;
};
//--------------
CollatzTree(WriteBest writeBest,
CheckUserBreak checkUserBreak, unsigned checkInterval);
~CollatzTree();
void addLevel();
const Best& getBest() const;
bool isFinished() const;
private:
typedef std::vector<Node> Level;
typedef std::vector<Level*> Levels;
typedef std:
air<unsigned, unsigned> Children;
PNode addInitial(unsigned value, PNode parent);
bool insert(unsigned value, PNode parent);
Children getChildren(unsigned value);
size_t getNewLevelSize();
const WriteBest writeBest_;
const CheckUserBreak checkUserBreak_;
const unsigned checkInterval_;
Levels levels_;
Best best_;
unsigned nodeCount_;
bool isFinished_;
};
#endif // COLLATZTREE_H
// end of file ----------------------------------------------------------------
// collatztree.cpp
#include "collatztree.h"
#if defined(_MSC_VER) && _MSC_VER == 1200 // MSVC 6
namespace std {
#include <math.h>
}
#else
#include <cmath>
#endif
#include <limits>
// CollatzTree ----------------------------------------------------------------
// public
CollatzTree::Node::Node(unsigned value, CollatzTree:
Node parent)
: value(value), parent(parent)
{}
bool CollatzTree::Node::isRoot() const
{ return parent == 0; }
//-----------------------------------------------
/* The constructor creates the entries up to 8 so that
getChildren() need not handle 1 as a spurious child of 4.
*/
CollatzTree::CollatzTree(CollatzTree::WriteBest writeBest,
CollatzTree::CheckUserBreak checkUserBreak, unsigned checkInterval)
: writeBest_(writeBest), checkUserBreak_(checkUserBreak),
checkInterval_(checkInterval), nodeCount_(4), isFinished_(false)
{
PNode pn = addInitial(1, 0);
pn = addInitial(2, pn);
best_.pNode = pn;
best_.depth = 1;
best_.cost = 1;
addInitial(8, addInitial(4, pn));
}
CollatzTree::~CollatzTree()
{
Levels::iterator pl = levels_.begin();
for(; pl != levels_.end(); ++pl) delete *pl;
}
/* The method addLevel() finds the numbers that a single
Collatz iteration takes to those in the previous top level.
It controls the new level's capacity to avoid memory waste.
*/
void CollatzTree::addLevel()
{
if(isFinished_) return;
const Level& oldTop = *levels_.back();
levels_.push_back(new Level());
levels_.back()->reserve(getNewLevelSize());
Children children;
Level::const_iterator parent = oldTop.begin();
for(; parent != oldTop.end() && !isFinished_; ++parent) {
children = getChildren(parent->value);
if(children.first != 0)
isFinished_ = insert(children.first, parent);
if(children.second != 0 && !isFinished_)
isFinished_ = insert(children.second, parent);
}
}
const CollatzTree::Best& CollatzTree::getBest() const
{ return best_; }
bool CollatzTree::isFinished() const
{ return isFinished_; }
// private --------------------------------------
CollatzTree:
Node
CollatzTree::addInitial(unsigned value, CollatzTree:
Node parent)
{
Level* pl = new Level();
levels_.push_back(pl);
pl->push_back(Node(value, parent));
return &pl->back();
}
bool CollatzTree::insert(unsigned value, CollatzTree:
Node parent)
{
static const float KLn2 = std::log(2.f);
static const unsigned KMaxNodeCount = std::numeric_limits<unsigned>::max();
levels_.back()->push_back(Node(value, parent));
unsigned depth = levels_.size() - 1;
float cost(depth / std::log(float(value)) * KLn2);
if(cost >= best_.cost && (cost > best_.cost || value < best_.pNode->value)) {
best_.pNode = &levels_.back()->back();
best_.depth = depth;
best_.cost = cost;
}
if(++nodeCount_ % checkInterval_ == 0) {
writeBest_(best_, nodeCount_);
if(checkUserBreak_()) return true;
}
return nodeCount_ == KMaxNodeCount;
}
CollatzTree::Children CollatzTree::getChildren(unsigned value)
{
static const unsigned
KHalfMaxValue = std::numeric_limits<unsigned>::max() / 2;
unsigned c1 = value * 2, c2 = (value - 1) / 3;
if(value > KHalfMaxValue) c1 = 0;
if(c2 % 2 == 0 || c2 * 3 + 1 != value) c2 = 0;
return Children(c1, c2);
}
/* Empirically determining the factors in getNewLevelSize() is easy,
but I have not proven that there are no outliers further up.
*/
size_t CollatzTree::getNewLevelSize()
{
static const float KFactors[] = {
0.f, 1.f, 1.f, 1.f, 1.f, 2.f, 1.f, 2.f, 1.f, 1.5f, 1.f,
1.34f, 1.25f, 1.4f, 1.29f, 1.34f, 1.21f, 1.25f, 1.23f, 1.32f
};
static const size_t NFactors(sizeof(KFactors) / sizeof(KFactors[0]));
float factor;
unsigned depth = levels_.size() - 1;
if(depth < NFactors) factor = KFactors[depth]; else factor = 1.28f;
return static_cast<size_t>(std::ceil(levels_[depth - 1]->size() * factor));
}
// end of file ----------------------------------------------------------------
