CODEWITHSUNDEEP
javaalgorithmbinarymultiplication
none
none

Reputation: 77

unsigned multiplication & sum algorithm

I'm trying to make an algorithm in java that makes an unsigned multiplication. This algorithm, then, make use of an unsigned sum. This is the code:

public int[] unsignedSum(int[] n1, int[] n2){
    int[] result = new int[48];
    int carry = 0;
    for(int x = 47; x >= 0; x--){
        if (n1[x]+n2[x]+carry == 1){
            result[x] = 1;
            carry = 0;
        }
        else if (n1[x]+n2[x]+carry == 2)
            carry = 1;
        else if (n1[x]+n2[x]+carry == 3)
            result[x] = 1;
    }
    return result;
}
public int[] unsignedMult(int[] n1, int[] n2){
    int[] result = new int[48];
    int[] N1 = new int[48];
    int[] N2 = new int[48];
    //fix the size to 48
    for (int x = 24; x < 48; x++){
        N1[x] = n1[x-24];
        N2[x] = n2[x-24];
    }
    for(int x = 47; x >= 0; x--){
        if (N2[x] == 1){
            int[] shiftedN1 = new int[48];
            for (int y = 0; y < x; y++)
                shiftedN1[y] = N1[y+48-x];
            result = unsignedSum(result, shiftedN1);
        }
    }
    return result;
}

Vectors n1 and n2 have size 24
any other vector have size 48
the problem is: it's eating the first number in some cases.
the multiplication should never overflow, but in this case, it does somehow.
1100000...(24bits) * 1100000(24bits).. should result in 10010000...(48 bits), but it's resulting in 00100000...(48 bits)

Upvotes: 0

Views: 553

Answers (1)

Misha
Misha

Reputation: 28173

Look for 2 off-by-one errors in

for (int y = 0; y < x; y++)
     shiftedN1[y] = N1[y+48-x];

What is exactly the off-by-one errors in the while loop?

You may want to run the above loop by hand with simple case of ....0001 * ....0001

Upvotes: 1

Related Questions