karatsuba multiplication, recursion problems

Question

I'm trying to implement multiplication of large numbers using karatsuba technique. I'm stuck in a seg fault which I'm not able to get around. The program seems to be always dropping out after 3 or 4 levels of recursion. sizeof(bint) returns 20000. My bint consists of an array of shorts.

friend bint operator+ (const bint& lhs, const bint& rhs)
{
    // adding two big integers
}

bint ksuba(const bint& X, const bint& Y, int n)    // n is always a power of 2
{
    if (n == 4)
        return smul(X, Y);    // naive way of multiplying numbers

    bint a1, b1, a2, b2;
    bint x, y, z;

    int half = n/2;

    for (int i=0; i<half; i++)
    {
        a1.data[SIZE - n + i + half] = X.data[SIZE - n + i];
        a2.data[SIZE - n + i + half] = X.data[SIZE - n + i + half];

        b1.data[SIZE - n + i + half] = Y.data[SIZE - n + i];
        b2.data[SIZE - n + i + half] = Y.data[SIZE - n + i + half];
    }

    a1.idx = SIZE - half;
    b1.idx = SIZE - half;
    a2.idx = SIZE - half;
    b2.idx = SIZE - half;

    x = ksuba(a1, b1, half);
    y = ksuba(a2, b2, half);
    z = ksuba((a1+a2), (b1+b2), n) - x - y;

    x.lshift(n);
    z.lshift(half);

    return x + y + z;
}

Using gdb gives the following error --

Program received signal SIGSEGV, Segmentation fault.
0x00000000004018c2 in bint::ksuba (this=<error reading variable: Cannot access memory at address 0x7fffff7ea3a0>, X=<error reading variable: Cannot access memory at address 0x7fffff7ea398>,    Y=<error reading variable: Cannot access memory at address 0x7fffff7ea390>, n=<error reading variable: Cannot access memory at address 0x7fffff7ea38c>) at big.cpp:593
593                 bint ksuba(const bint& X, const bint& Y, int n)

I tried reducing the number of bint variables I'm declaring. Specifically, I got rid of y by adding the result of ksuba(a2, b2, half) to x itself. But it's not solving the matters. Is there some way of knowing how much memory is being allocated at every step of recursion? Any help would be really appreciated.

Answer 1

At each level, you have 7 explicitly declared variables of type bint, and 2 more are implicitly allocated for the call to ksuba((a1+a2), (b1+b2), n). All those go into the stack. That's 180 KB. Stack usage may be larger if the program is built in debug mode, without optimizations.

180 KB does not seem enough to explain the crashing, since (assuming this is Linux) you should have 8 MB of stack by default and you shouldn't be running out after just 3 or 4 iterations. But, as Dmitri mentions, you can try to increase the stack size using the ulimit tool or by specifying it through Wl,--stack=xxxxx option when linking. Better yet, don't put bint's on the stack. Allocate them dynamically with new/delete and only keep pointers on the stack.