2.75 Unsigned High Prod

★★★

Problem:

Suppose we want to compute the complete 2w-bit representation of $x\cdot y$, where both $x$ and $y$ are unsigned, on a machine for which data type unsigned is w bits. The low-order w bits of the product can be computed with the expression x*y, so we only require a procedure with prototype:

unsigned int unsigned_high_prod(unsigned x, unsigned y);

that computes the high-order w bits of $x\cdot y$ for unsigned variables.

We have access to a library function with prototype:

int signed_high_prod(int x, int y);

that computes the high-order w bits of $x\cdot y$ for the case where $x$ and $y$ are in two's-complement form. Write code calling this procedure to implement the function for unsigned arguments. Justify the correctness of your solution.

Hint: Look at the relationship between the signed product$x\cdot y$ and the unsigned product$x'\cdot y'$.

Code:

#include <stdio.h>
#include <assert.h>
#include <inttypes.h>

int signed_high_prod(int x, int y) {
    int64_t prod = (int64_t) x * y;
    return prod >> 32;
}

unsigned unsigned_high_prod(unsigned x, unsigned y) {
    int sign_x = x >> 31;
    int sign_y = y >> 31;
    int signed_prod = signed_high_prod(x, y);
    return signed_prod + sign_x * y + sign_y * x;
}

unsigned unsigned_high_prod_for_test(unsigned x, unsigned y) {
    uint64_t prod = (uint64_t)x * y;
    return prod >> 32;
}

int main() {
    unsigned x = 0x12345678;
    unsigned y = 0xFFFFFFFF;
    assert(unsigned_high_prod(x, y)==unsigned_high_prod_for_test(x, y));
    return 0;
}