I am trying to solve a problem from projecteuler.net http://projecteuler.net/problem=14
This is the problem:
The following iterative sequence is defined for the set of positive integers:
n → n/2 (n is even)
n → 3n + 1 (n is odd)
Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?
NOTE: Once the chain starts the terms are allowed to go above one million.
I first used a recursive solution, but after 100,000 or so iterations there was a segmentation fault. So I made an iterative solution hoping that would solve the problem. A segmentation fault occurred at the same point. I looked at the stack trace and found that the problem showed up when a value was added to the vector I marked the line below. I thought the vector would automatically resize so I'm really confused about this problem. Thanks for your help. Here's the code:
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
int ITERATIONS=100000;
int main()
{
vector<int> maxArray;
vector<int> newArray;
int max_size = 0;
int n = 2;
int collatz = n;
while(n <= ITERATIONS){
#Stack trace error#
newArray.push_back(collatz);
#Stack trace error#
if(collatz == 1){
++n;
if(newArray.size() > max_size){
maxArray.clear();
for(vector<int>::const_iterator i = newArray.begin(); i < newArray.end(); ++i){
maxArray.push_back(*i);
}
max_size = newArray.size();
}
newArray.clear();
collatz = n;
}
else if(collatz%2 == 0)
collatz = collatz/2;
else
collatz = 3*collatz+1;
}
for(vector<int>::const_iterator i = maxArray.begin(); i < maxArray.end(); ++i){
cout << *i << " ";
}
cout << "\n" << max_size;
}
The stack Trace:
#0 0x00132416 in __kernel_vsyscall ()
#1 0x002641df in raise () from /lib/i386-linux-gnu/libc.so.6
#2 0x00267825 in abort () from /lib/i386-linux-gnu/libc.so.6 #3 0x001e013d in __gnu_cxx::__verbose_terminate_handler() () from /usr/lib/i386-linux-gnu/libstdc++.so.6
#4 0x001dded3 in ?? () from /usr/lib/i386-linux-gnu/libstdc++.so.6
#5 0x001ddf0f in std::terminate() () from /usr/lib/i386-linux-gnu/libstdc++.so.6
#6 0x001de05e in __cxa_throw () from /usr/lib/i386-linux-gnu/libstdc++.so.6
#7 0x001de67f in operator new(unsigned int) () from /usr/lib/i386-linux-gnu/libstdc++.so.6
#8 0x08049362 in __gnu_cxx::new_allocator<int>::allocate (this=0xbffff214,
__n=536870912) at /usr/include/c++/4.6/ext/new_allocator.h:92
#9 0x0804923c in std::_Vector_base<int, std::allocator<int> >::_M_allocate (
this=0xbffff214, __n=536870912) at /usr/include/c++/4.6/bits/stl_vector.h:150
#10 0x08048e7f in std::vector<int, std::allocator<int> >::_M_insert_aux (
this=0xbffff214, __position=..., __x=@0xbffff220: -91)
at /usr/include/c++/4.6/bits/vector.tcc:327
#11 0x08048bdd in std::vector<int, std::allocator<int> >::push_back (
this=0xbffff214, __x=@0xbffff220: -91)
at /usr/include/c++/4.6/bits/stl_vector.h:834
#12 0x08048897 in main () at iterativeCollatz.cpp:16
We make the following observations:
- The single smallest chain consists of just the number 1. Its length is 1.
- Long chains can only be formed by prepending
x to a tail chain that begins at either x/2 (if x is even) or 3x+1 (if x is odd). The length of a long chain is 1 plus the length of its tail.
- Once the chain starts the terms are allowed to go above one million.
- Negative numbers are not really needed to solve this problem.
- No chain has length 0.
And we arrive at the following conclusions:
- From observations 1 and 2: Once we find the length of a chain beginning at
x, we must memoize it. This avoids recomputing the lengths of tails. Furthermore, we can interpret a chain length being 0 (which results by default-constructing a std::size) as "this length has not been computed yet".
- From observation 3: For any
x > 1000000, if we eventually need to compute the length of the chain beginning at x, nothing guarantees we will be interested in the length of every chain beginning at a y such that x > y >= 1000000. So we should use an associative data structure (such as std::map), not std::vector, for storing the memoized lengths:
- From observations 3 and 4: We shall use an unsigned integral type as big as possible. Without going as far as using a bignum library (such as GMP), the type we want is
std::uint64_t.
- From observation 5: We can use a chain length value of 0 to denote "this chain length has not been computed yet". This is particularly convenient because C++'s associative containers default-construct a value when using
operator [] with a key that does not exist in the container, and a default-constructed value of an integral type is initialized to 0.
The resulting program, written using C++11 constructs for convenience, is this:
#include <iostream>
#include <map>
#include <set>
#include <stack>
int main()
{
typedef std::uint64_t num;
// ys[x] is the length of the chain starting at x.
// xms is the set of numbers that yield the longest chains.
// ym is the length of the longest chain so far.
std::map<num, num> ys = {{1,1}};
std::set<num> xms = {1};
num ym = 1;
for (num i = 2; i < 1000000; ++i)
{
std::stack<num> xs;
num x = i, y = ys[x];
// Compute successive chain elements until
// a base element is reached whose chain
// length has already been memoized.
while (!y)
{
xs.push(x);
x = (x & 1) ? (3*x + 1) : (x/2);
y = ys[x];
}
// The lengths of the newly computed elements
// can be found by repeatedly incrementing
// the base element's chain length.
while (!xs.empty())
{
x = xs.top();
ys[x] = ++y;
xs.pop();
}
// Keep track of which number(s)
// yield the longest chain(s).
if (y >= ym)
{
if (y > ym)
{
xms.clear();
ym = y;
}
xms.insert(x);
}
}
for (num xm : xms)
std::cout << xm << ' ';
return 0;
}
The condition i < newArray.end() should be i != newArray.end(). And of course the same applies to i < maxArray.end().
#6 0x001de05e in __cxa_throw () from /usr/lib/i386-linux-gnu/libstdc++.so.6
This call to __cxa_throw indicates a C++ exception is being thrown.
#5 0x001ddf0f in std::terminate() () from /usr/lib/i386-linux-gnu/libstdc++.so.6
The std::terminate function exits the application immediately. This can be due to several reasons:
- The exception is being thrown in the destructor of an object while another exception is being thrown.
- The program does not have a try...catch handler.
In this case, option 2 is the most likely. Running the program should result in something like:
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
Program received signal SIGABRT, Aborted.
This gives you the message of the exception (the what output).
#7 0x001de67f in operator new(unsigned int) () from /usr/lib/i386-linux-gnu/libstdc++.so.6
This line indicates that the exception was triggered when allocating memory (most likely a std::bad_alloc, indicating out-of-memory).
Therefore, I would check that you are not allocating large vectors that are running out of memory.
NOTE: You can add your own try...catch handler by writing something like:
try
{
// Your code here.
}
catch (const std::exception &e)
{
std::cout << "Error: " << e.what() << std::endl;
}
The vector implementations will increase the size of the vectors whenever they no longer have any room. This is typically done by doubling the space (2, 4, 8, 16, ...). This will get very large quickly, and you have 2 vectors growing to fit 100000 elements. Also note that while growing the vector, it needs to keep the old data around to copy into the new vector.
You can use the reserve method on maxArray and newArray to set the desired size before the loop. That is:
maxArray.reserve(ITERATIONS);
newArray.reserve(ITERATIONS);
This will also ensure cleaner performance as the vectors don't have to increase the internal data array to add the new elements.
I've tested your code and there is no SIGSEGV, maybe you should give out more information.
Here is my suggest:
The vector class has a member function called capacity(), maybe you should check this out.
