How do I find the value of w in this multiplication algorithm?

[garamor]

Hello! I just got started on project 12, the first thing that the video series went over was multiplication and they used this algorithm:

// Returns x*y, where x, y >= 0
multiply(x,y):
    sum = 0
    shiftedX = x
    for i = 0 ... w - 1 do
        if ((i'th bit of y) == 1)
            sum = sum + shiftedX
        shiftedX = shiftedX * 2      // shiftedX + shiftedX
    return sum

I understand the algorithm, the only part that is confusing to me is how we get the value of w and why we are subtracting one from it. Anyone think they can help me understand this?

[dolomiti7]

In the context of this algorithm "w" stands for the bit-width. So it would work for w=16 in the case of the Hack system. The loop goes from 0 to w-1, to ensure that you run through w iterations - one for every bit (e.g. bit 0 to bit 15 in this case).

An additional remark: The definition of the algorithm states x,y>=0. Positive numbers in two's complement representation will only use 15 bits. So with this limitation of x,y>=0, the algorithm would also work with w=15. In this case you have to convert negative operands first and adjust the result depending on the signs of the operands.

However, for multiplication of signed numbers, the algorithm would also work ignoring the sign of the operands and just run through all 16 bits (like an unsigned multiplication with w=16). The result will still be correct and with the correct sign.

[garamor]

Thanks, this has been quite helpful!