CODEWITHSUNDEEP
c++
Giuseppe
Giuseppe

Reputation: 492

How to fix this exception?

I'm having problems again with my Euclid's algorithm problem. I'm running this on MS Visual Studio as a console application. When I run it, it says "process is terminated due stack overflow exception."

I've recently posted another question about this algorithm, but now I've got this problem and it's the first time I've seen it. I'm a beginner programmer.

int algoritmoeuclides(int a,int b)
{
if (a%b==0)
return b;
return algoritmoeuclides(b,a%b);
}

std::pair<int, int>division(int dividendo,int divisor)
{
    int resultado=0;
    int residuo=0;
    residuo=dividendo%divisor;
    resultado=dividendo/divisor;
    return std::pair<int, int>(residuo,resultado);
}

std::pair<int, int>EuclidesExtendido(int a,int b)
{
    int q,r,s,t;
    if (b == 0)
    return std::pair<int, int>(1, 0);
    else
        {
        std::pair<int, int>(q, r) = division(a, b);
        std::pair<int, int>(s, t) = EuclidesExtendido(b, r);
        }
        return std::pair<int, int>(t, s - q * t);
}

int main(array<System::String ^> ^args)
{
int a=525;
int b=231;
int s,t;
std::pair<int, int>(s, t)=EuclidesExtendido(a,b);
printf("%d",algoritmoeuclides(a,b));
printf("s=%d  t=%d",s,t);

getch();
}

Upvotes: 0

Views: 164

Answers (3)

Jonathan Leffler
Jonathan Leffler

Reputation: 753455

When I compile the code with GNU g++, having commented out the getch(), changed the definition of main() to the simpler int main() (since the code doesn't use any arguments), and added the <cstdio> and <utility> headers, I get the extensive warnings:

euc.cpp: In function ‘int main()’:
euc.cpp:43:1: warning: ‘s’ is used uninitialized in this function [-Wuninitialized]
euc.cpp: In function ‘std::pair<int, int> EuclidesExtendido(int, int)’:
euc.cpp:23:5: warning: ‘r’ may be used uninitialized in this function [-Wuninitialized]
euc.cpp:28:60: warning: ‘r’ may be used uninitialized in this function [-Wuninitialized]
euc.cpp:30:44: warning: ‘q’ may be used uninitialized in this function [-Wuninitialized]
euc.cpp:30:44: warning: ‘t’ may be used uninitialized in this function [-Wuninitialized]
euc.cpp:30:44: warning: ‘s’ may be used uninitialized in this function [-Wuninitialized]
euc.cpp: In function ‘int main()’:
euc.cpp:40:29: warning: ‘s’ is used uninitialized in this function [-Wuninitialized]
euc.cpp:40:29: warning: ‘t’ is used uninitialized in this function [-Wuninitialized]

You should turn up the warning level on MS Visual Studio so you see such warnings and can fix them before submitting questions here. Given that you are using uninitialized variables, you are getting quasi-random values to play with, which is probably driving your system into the recursion far deeper than you expected, leading to the stack overflow.

This code compiles and runs without self-evident problems on Mac OS X. It produces the answer:

21
s=-1  t=64

I'm not sure if that's what you're expecting. The 21 is the greatest common denominator of 231 (11x7x3) and 525 (7x5x5x3). I suspect the -1 is not correct (and therefore the 64 is probably wrong too).

#include <cstdio>
#include <utility>

int algoritmoeuclides(int a, int b)
{
    if (a % b == 0)
        return b;
    return algoritmoeuclides(b, a % b);
}

std::pair<int, int>division(int dividendo, int divisor)
{
    int residuo = dividendo % divisor;
    int resultado = dividendo / divisor;
    return std::pair<int, int>(residuo, resultado);
}

std::pair<int, int>EuclidesExtendido(int a, int b)
{
    if (b == 0)
        return std::pair<int, int>(1, 0);
    else
    {
        std::pair<int, int>q = division(a, b);
        std::pair<int, int>s = EuclidesExtendido(b, q.second);
        return std::pair<int, int>(s.second, s.first - q.first * s.second);
    }
}

int main()
{
    int a = 525;
    int b = 231;
    std::pair<int, int>p = EuclidesExtendido(a, b);
    printf("%d\n", algoritmoeuclides(a, b));
    printf("s=%d  t=%d\n", p.first, p.second);
}

Upvotes: 1

xDD
xDD

Reputation: 3453

Assuming you are fine with using some C++11 library features, instead of std::pair<int, int>(s, t) you want std::tie(s, t) from the <tuple> header which creates a pair of references that can be assigned to.

Upvotes: 0

jedwards
jedwards

Reputation: 30200

You're collecting the return value of your functions incorrectly.

Despite having two values, a pair is a single object. So

std::pair<int, int>(q, r) = division(a, b);

Should be something like:

std::pair<int, int> qr = division(a, b);

And then you could get q and r individually with:

int q = qr.first;
int r = qr.second;

You would need to make this sort of change everywhere that you have similar errors.

Upvotes: 4

Related Questions