trouble with mulplication

[scthread]

I am doing another recursive function - actually have the code working - but one of my required test sets is throwing an error??? The actual result should fit as an integer, i made it an unsigned long to leave plenty of room... but I keep getting the following error:

Unhandled exception at 0x00391e69 in MultiplicationRecursion.exe: 0xC00000FD: Stack overflow.

  int multiData(unsigned long long  X, unsigned long long  Y)
{

	unsigned long long prod=X;

	if (Y==1)
	{
		return prod;
	}
	else
	{
		return X + multiData(X,Y-1);
	}


}

using 12345 & 90009 for input
i did the calculation on my calculator... should = 1,111,161,105.

is this a memory issue... i cannot see why it works for most things, and not for others especially when the end result is less than the max size of the data type..

[Daleth]

Maybe 90,009 recursion iterations are too many for the stack. Replacing 90,009 with smaller numbers works fine. I even tried changing your return type to unsigned long long, but still ended up with segmentation faults with a five-digit second parameter. When I run your program, there is a segmentation fault at the 43,437^th iteration.

Edit:
Almost forgot. Why are you doing this instead of X*Y?

[cire]

One of the obvious things you can do to minimize the number of recursive calls is to make sure X is the big number and Y is the smaller one.

typedef unsigned long long int_type ;

int_type recursiveMultiply(int_type a, int_type b)
{
    if ( b == 1 )
        return a ;
    else
        return a + recursiveMultiply(a,b-1) ;
}

int_type multiData(int_type x, int_type y)
{
    return recursiveMultiply(std::max(x,y), std::min(x,y)) ;  
}

[vlad from moscow]

#include <iostream>

int main()
{
	struct Product
	{
		long long operator ()( int x, int y ) const
		{
			return 
			( y ==  0 ?  0 : 
			( y ==  1 ?  x :
			( y == -1 ? -x :
			( operator ()( x, y / 2 ) + operator ()( x, y - y / 2 ) ) ) ) );
		}
	};

	std::cout << Product()(  2,  3 ) << std::endl;
	std::cout << Product()( -2,  3 ) << std::endl;
	std::cout << Product()( -2, -3 ) << std::endl;
	std::cout << Product()( 12345, 90009 ) << std::endl; 
	std::cout << std::endl;
}

The output

6
-6
6
1111161105

[scthread]

@Daleth - it is the part of the assignment to do recursive function instead of easy way... and it was suggested to use addition...

@vlad - i like your thinking of cutting it in half and adding it together! I would have never thought to do that.

@cire - good point - will make sure to do that too so I am not adding 2 to its self 6 thousand times...

thank you all for your help!

[ar2007]

@vlad:
Can you explain this?

	long long operator ()( int x, int y ) const

Why double ()() on struct type?
Thx

[vlad from moscow]

operator () is a function name of so-called function call operator as for example operator + or operator << are also corresponding function names. The second pair of parentheses serves to specify arguments for the function. For example

operator ()( 2, 3 );
operator +( x, y );
operator <<( std::cout, std::string( "Hello World" ) );

So for example instead of

std::cout << std::string( "Hello World" ) << std::endl;

you can write

std::operator <<( std::cout, std::string( "Hello World" ) ) << std::endl;

[ar2007]

I thank you, vlad. I did not know this function.