### trouble with mulplication

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.

 ``12345678910111213141516`` `````` 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..
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,437th iteration.

Edit:
Almost forgot. Why are you doing this instead of X*Y?
Last edited on
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.

 ``1234567891011121314`` ``````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)) ; }``````

 ``12345678910111213141516171819202122`` ``````#include 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 ```
Last edited on
@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!
Can you explain this?

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

Why double ()() on struct type?
Thx
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;
Last edited on
I thank you, vlad. I did not know this function.

Topic archived. No new replies allowed.