StringTest not passing with own Math class

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

StringTest not passing with own Math class

resema
Hi there

My implementation of the Math class is passing all tests. The same for the String class, but only without my own Math class.

In case I'm using my own Math class for the String tests, it ends in a stack overflow in the Math.divide class. I guess that the division of -32767 by 10 causing the stack overflow due to the recursion in the Math class.

Does the proposed implementation of the Math division contains such a limitation?

Thanks,
resema
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: StringTest not passing with own Math class

cadet1620
Administrator
resema wrote
I guess that the division of -32767 by 10 causing the stack overflow due to the recursion in the Math class.

Does the proposed implementation of the Math division contains such a limitation?
Good guess. It does have issues witn signed integer overflow.

The recursive call doubles the divisor each call until the divisor (y) is greater than the dividend (x). Since the recursive algorithm is wrapped with sign handling code, for -32767/10, x = 32767 and y = 10. The recursive y's are:
 hex    dec
000A     10
0014     20
0028     40
0050     80
00A0    160
0140    320
0280    640
0500   1280
0A00   2560
1400   5120
2800  10240
5000  20480
A000 -24576
4000  16384
8000 -32768
0000      0
0000      0
Since y is never > 32767, recursion is infinite.

A quick solution is to add (y < 0) into the if at the top of the recursive divide function since a negative value here indicates that y >= 32768.

There are still issues with x or y = -32768.  See this article for more info on signed integer overflow and complete treatment of overflows in the division algorithm.

--Mark


 
Loading...