How can I allocate a massive boolean array that currently throws std::bad_alloc errors during allocation?

Question

I've seen several questions related to this, but I want verification that I'm having a similar problem. My code allocates a boolean array with a very large number of elements. This is my code, compiling on an x86_64 Linux machine:

#include <iostream>
#include <math.h>

using std::cout;
using std::endl;
using std::nothrow;

long problem3()
{
    long upper_bound = 600851475143;
    long max_prime_factor = 1;
    long max_possible_prime = (long) sqrt(upper_bound) + 1;
    bool * primes;
    primes = new (nothrow) bool[upper_bound];
    primes[0] = false; //segmentation fault occurs here
    primes[1] = false;
    for (long i = 2; i < upper_bound; i++)
       primes[i] = true;
    for (long number = 2; number < max_possible_prime; number++)
    {
        if (primes[number] == true)
        {
            if (upper_bound % number == 0)
            {
                max_prime_factor = number;
            }
            for (long j = number + number; j < upper_bound; j += number)
                primes[j] = false;
        }
        else { continue; }
    }
    return max_prime_factor;
}

int main ( int argc, char *argv[] )
{
    cout<<"Problem 3: "<<problem3()<<endl;
}

Building this code and running it as is gives a segmentation fault on this line:

primes[0] = false

If I remove the nothrow instruction to change this line:

primes = new (nothrow) bool[upper_bound];

to this:

primes = new bool[upper_bound];

I get an error message stating:

terminate called after throwing an instance of 'std::bad_alloc'

I think this means that the allocation is failing, presumably because of the size (based on similar questions and other referenced links.

The debugger in CodeBlocks shows that primes remains set to 0x0 even after its supposed to be allocated. Valgrind confirms this:

==15436== Command: ./main
==15436== 
==15436== Invalid write of size 1
==15436==    at 0x400A81: problem3() (main.cpp:54)
==15436==    by 0x400B59: main (main.cpp:77)
==15436==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==15436== 
==15436== 
==15436== Process terminating with default action of signal 11 (SIGSEGV)
==15436==  Access not within mapped region at address 0x0
==15436==    at 0x400A81: problem3() (main.cpp:54)
==15436==    by 0x400B59: main (main.cpp:77)
==15436==  If you believe this happened as a result of a stack
==15436==  overflow in your program's main thread (unlikely but
==15436==  possible), you can try to increase the size of the
==15436==  main thread stack using the --main-stacksize= flag.
==15436==  The main thread stack size used in this run was 8388608.
==15436== 
==15436== HEAP SUMMARY:
==15436==     in use at exit: 0 bytes in 0 blocks
==15436==   total heap usage: 1 allocs, 0 frees, 0 bytes allocated
==15436== 
==15436== All heap blocks were freed -- no leaks are possible
==15436== 
==15436== For counts of detected and suppressed errors, rerun with: -v
==15436== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 3 from 3)
Segmentation fault

Question: I know about std::vector, so should I use that to allocate this array? I'm open to trying a different algorithm as well, but I would like to know if there is a nuance of C++ I'm missing that will allow me to allocate such an array (even though it's absolutely massive and I understand that). I tried to debug this question as much as possible too, but if there is anything else I should have provided, let me know so I can use the tools the next time I run into trouble.

You should _always_ consider the `std::vector` approach before the raw alloc approach. Anyway, my guess is that `long` is 32 bits on your inplementation, and as such `600851475143` overflows, giving a bogus value that causes the allocation to fail. Try using `long long` if your implementation supports it. Also, make sure your implementations allows for a heap large enough. — Etienne de Martel, Jun 19 '12 at 02:26
An array that large is going to be about half a terabyte. In other words, you're going to need to change your algorithm. — Corbin, Jun 19 '12 at 02:30
For this type of problem, you may wish to take a probabilistic approach. See also: http://en.wikipedia.org/wiki/Integer_factorization#Factoring_algorithms — Mike Bailey, Jun 19 '12 at 02:37
@MikeBantegui That's what I was considering. I had old code for this sieve lying around, so I chose to modify it first. Probabilistic algorithms should be a good learning experience for C++ though. — Ricardo Altamirano, Jun 19 '12 at 02:38
@pythonscript: If you can implement it, Dixon's factorization is very nearly linear in input size for the prime factor you're working with. — Mike Bailey, Jun 19 '12 at 02:41
@MikeBantegui Sounds like a nice challenge. I always enjoy algorithms, even though I'm not the greatest at coding them. As long as the space complexity isn't an issue (since that's the major issue I'm facing in this question, it seems) it should be a nice item to code. — Ricardo Altamirano, Jun 19 '12 at 02:44
@pythonscript that is a massive amount of data you're allocating. The suggestions to use a different algorithm are most certainly the best, but out of curiosity, I wonder if a deque could manage it (provided your hard drive is large enough). Unlike vector, deques consist of multiple, often page-size blocks so you never have to have the entire sequence paged at a given time. While it'd probably still take ages and massive amounts of swap disk to do it, a deque might be able to pull this off without throwing bad_alloc. In any case, always prefer sequences like vector to raw arrays. — stinky472, Jun 19 '12 at 02:51
@stinky472 Thanks for the tip. I should have plenty of space on this machine (around 400 GB free) but I do agree that a different algorithm is probably the best idea. Gives me another small project to start. — Ricardo Altamirano, Jun 19 '12 at 02:53

score 2 · Accepted Answer · answered Jun 19 '12 at 03:01

An extremely simple algorithm you can use to factorize the (large) number you're working with is Pollard's Rho Algorithm.

I will leave the mathematical explanation out for brevity's sake, but you can find the details on the Wikipedia article.

unisgned long long GCD(unisgned long long x, unisgned long long y)
{
    while (y != 0)
    {
        unsigned long long t = b;
        b = a % b;
        a = t;
    }

    return a;
}

unsigned long long f(unsigned long long x, unsigned long long n)
{
    return (x * x + 1) % n;
}

unsigned long long PollardRho(unsigned long long n)
{
    unsigned long long x = 2, y = 2, d = 1;

    while (d == 1)
    {
        x = f(x);
        y = f(f(y));
        d = GCD(std::abs(x - y), n);
    }

    if (d == n)
        throw "Failure";
    return d;
}

unsigned long long MaxFactor(unsigned long long n)
{
    unsigned long long largest = 1;

    while (n != 1)
    {
        unsigned long long factor = PollardRho(n);
        largest = std::max(largest, factor);
        n /= factor;
    }

    return largest;
}

Note: I didn't actually test the C++ code. I prototyped it in Mathematica and it correctly returned the maximal prime factor as being 6857.

Note: You can use the same basic idea I have outlined here to get the largest prime factor. Instead of using the `PollardRho` algorithm, you can use trial division to divide out the largest prime factors along with the constraint that you should only consider up to `sqrt(n)` for prime factors. By dividing out prime factors, you vastly reduce your search space. — Mike Bailey, Jun 19 '12 at 13:02

score 1 · Answer 2 · answered Jun 19 '12 at 02:28

1

Use std::vector<bool> or std::bitset which are specifically made for this purpose with data density and fast operations in mind. In an regular array of bools every single element is allocated at least a byte, instead of a bit.

answered Jun 19 '12 at 02:28

zxcdw

1,629
1
10
18

6

Even if you could allocate 1 bit per number, you're looking at 70 GB worth of data. – Mike Bailey Jun 19 '12 at 02:30

score 0 · Answer 3 · answered Jun 19 '12 at 02:54

0

Assuming that 600851475143 is a composite number, its largest prime factor is less than or equal to sqrt(600851475143) or about 775146. Your sieve doesn't need to be any larger than that.

This problem (Project Euler #3) can also be solved with simple brute-forced factorization. That method only takes about .002 seconds on my desktop PC.

answered Jun 19 '12 at 02:54

Blastfurnace

18,411
56
55
70

Thanks for catching my revision too. I took the upper bound on the prime factor into account in part of the program but didn't post the most recent version. And yes, it's project euler. A nice little site in my opinion! – Ricardo Altamirano Jun 19 '12 at 02:57
I know brute force is sometimes the best way to solve a problem, but I always like the more creative algorithms (assuming I implement them correctly, unlike in this case). – Ricardo Altamirano Jun 19 '12 at 03:03

How can I allocate a massive boolean array that currently throws std::bad_alloc errors during allocation?

3 Answers3