Tools: Updated OS/Math.vm file

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

Tools: Updated OS/Math.vm file

cadet1620
Administrator
Contributed by Mark Armbrust
1 July 2014
Copy this file to your nand2tetris/tools/OS directory.
  Math.vm

This file corrects bugs in Math.multiply() and Math.divide() when one or both of their arguments is -32768.

divide() has two bugs. The bad one is that x/-32768 causes it to overwrite all of memory including the screen with 0's!
Also, -32768/y, y≠-32768 always returns 0.

multiply()'s bug is extremely minor; all multiplies involving -32768 return 0. (The only non-overflowing multiply involving -32768 is -32768 x 1 = -32768.)


What Caused the Bugs?

The bugs are all related to the fact that the absolute value of -32768 cannot be represented as a 16-bit signed integer.

Remember that in 2's-complement, -x = (~x)+1.

-(-32768)= 1000 0000 0000 00002
= 0111 1111 1111 11112 + 1
= 1000 0000 0000 00002
= -32768

abs(x) can return a negative number!

Both multiply() and divide() handle negative arguments by determining the sign of the result and then using abs(x) and abs(y) in algorithms that were designed to handle only non-negative numbers.


A Note About Overflow

That multiplication can overflow is obvious since the magnitude of the result of multiplication must be greater than or equal to the magnitudes of the operands: 30,000 x 30,000 = 900,000,000 which is a 30-bit number. The multiply() function returns only the lower 16 bits of the result, which is the signed integer -5888.

It's less obvious that division can overflow. The magnitude of the result of integer division must be less than or equal to the magnitude of the dividend. The problem case is -32768 / -1 = +32768. +32768 is binary 1000 0000 0000 0000 which is the signed integer -32768.