Implementing the bit(x,j) function for Math.multiply

[rgravina]

I'm just starting with the OS, and for Math.multiply it's suggested to implement a bit(x, j) function which returns true if the j-th bit of the integer x is 1. To help with this, it's convenient to create an array with the powers of two from 0 to 15 in the init function.

However, the Jack compiler gives me an "Integer constant too big" error for 2^15. If I recall correctly, Hack/Jack can store signed numbers 15-bit long. It seems that 2^15 would be 1000 0000 0000 0000 which would explain the error (the first bit in an A-instruction is 0), whereas  2^15-1 (32767) would be represented as 0111 1111 1111 1111 and this doesn't give a compiler error.

I'm wondering if I'm doing something wrong, or should work around it somehow?

class Math {
    static Array twoToThe;

    function void init() {
        let twoToThe = Array.new(16);
        let twoToThe[0] = 1;
        let twoToThe[1] = 2;
        let twoToThe[2] = 4;
        // etc..
        let twoToThe[14] = 16384;
        let twoToThe[15] = 32768;  // error: Integer constant too big
        return;
    }
}

[cadet1620]

Your analysis is spot on.

The asymmetric nature of 2-s complement integers is often annoying, and the maximum negative integer, -32768 for 16-bit numbers, is often a source of bugs. I remember a system hang in a fielded product that I tracked down to a loop that couldn't hit its exit because abs(x) was returning a negative number! (Apply the 2's complement negation rule to 1000...0000)

The Jack compiler doesn't optimize constants so you can use 32767+1. The Hack computer won't notice the signed integer overflow.

Being a lazy programmer who doesn't like typing lots of numbers, I implemented this in a loop using

    let pow2[i] = n;
    let n = n+n;

--Mark

[rgravina]

> Your analysis is spot on.

Thanks :)

> Being a lazy programmer who doesn't like typing lots of numbers, I implemented this in a loop using ...

It hadn't occurred to me to implement it using variables and a loop, so that the constant 32768 doesn't need to be written. Thanks!

For values >= 2^14 (16384) and < 2^15 (32768), the 15th bit is always 1... so maybe there's no need to store (and check) for the 16th bit. In other words, the book says to "define a fixed static array of length 16", but it could actually be 15 elements long, I think?

[cadet1620]

rgravina wrote

For values >= 2^14 (16384) and < 2^15 (32768), the 15th bit is always 1... so maybe there's no need to store (and check) for the 16th bit. In other words, the book says to "define a fixed static array of length 16", but it could actually be 15 elements long, I think?

The algorithm presented in the book is 16-bit unsigned multiplication, so you do need 2^15. The nice thing about multiplication is that low-order 16 bits of signed and unsigned multiplication are identical, so you can use the simpler unsigned multiplication algorithm if you don't care about the upper 16 bits of the result.

--Mark

[jrd]

I'm still having problems correctly implementing the bit (x,j) function.

Conceptually, my approach was to convert int x into a binary number using a loop routine, storing each bit into an 16-bit array called test[16].  Similar to how twoToThe[16] array was created, but instead using 1's/0's.

After that routine has concluded, I then test the int j'th bit of my test[16] array to see if it's a 1 value - and then return true/false appropriately.

However, am not getting proper results.

Would you recommend this approach conceptually (I'm also concerned about processing time), or is there another intended approach?

Any thoughts/guidance here?

Thx.

- JRD

[cadet1620]

Look at a typical x value
    0010 1110 1010 0001
What you want to know if bit j is set.  Say j = 5.

Bit-wise logical operations AND and OR can be used to set, reset and test bits. This is a very important aspect of bit-wise AND and OR.

For example to set bit 3 in a value, you can OR that value with 0000 0000 1000.

You can test bit 5 by ANDing with 0000 0000 0010 0000 (this is called bit masking); the result will be either 0000 0000 0000 0000 or 0000 0000 0000 0010 0000.

Hint: what's the integer value of the bit mask 0000 0000 0010 0000?

--Mark

[jrd]

Mark:

Thank you for the helpful insight.  One last question pls.

Having debugged my Math.jack class many times, it is now processing correctly.  

However, oddly, my sqrt function seems to work fine on all values except for an input of 32767.  

In my unit testing, r[9] is returning a value of 255, instead of required 181.

Note that I've implemented the sqrt function according to the algorithm presented in the book and it is working properly for all other test cases.

I'm wondering if there is something in the way that an input value of 32767 needs to be expressed, in order to get the compiler working properly?  Note that I've tried to convert an input value of 32767 to either 32766 + 1 or ~32676 (pursuant to another post that I've found).  Still, no luck and still returning 255, instead of 181.

Any last thoughts?

Thanks.

- JRD

[cadet1620]

I don't have any immediate thoughts and I running out the door.

Feel free to email your Math.jack and I'll take a look at it tonight or tomorrow.

--Mark

[cadet1620]

The problem that you are running into is a "signed integer overflow."

For clarity, I've split the long if statement in your code into two lines.

    let xx = Math.multiply((y + twoToThe[j]), (y + twoToThe[j]));
    if ( (xx < x) | (xx = x) )
        {

When you pass a value greater than or equal to 16384 into your square root function, (y+2^j)^2 can be > 32767 so it is too large to fit in a signed integer so the result is a negative number.

j   x    y  (y+2^j)^2    
7 16384   0 16384
6 16384 128 36864 (-28672)

There are two ways to fix your code.

Redesign your algorithm so that it does not cause multiplication overflows.  (This can be quite difficult.)

Handle the overflows when they occur.  (Much easier.)

You can handle this overflow by checking if the result of the multiply is negative.  If it is, then you know that (y+2^j)^2 > x and y should not be adjusted.

    let xx = Math.multiply((y + twoToThe[j]), (y + twoToThe[j]));
    if (xx < 0) {
        // overflow occurred, xx > x so do nothing
    } else {
        if ( (xx < x) | (xx = x) )
            {

Signed integer overflow is beyond the scope of the n2t course, but if you want to read more about it, I wrote this article that analyses the n2t division algorithm.

--Mark

[jrd]

Thank you, Mark.

That did the trick!

As usual, your insight very helpful and I read the additional article on signed integers that you supplied link for.  That, too, was a big assistance in understanding the issue.

Always appreciate your prompt feedback.

Best,

- JRD