CODEWITHSUNDEEP
javakaratsuba
DanBan
DanBan

Reputation: 21

ArrayIndexOutOfBoundsException: 0 in Karatsuba Implementation

I'm implementing a Karatsuba algorithm, and am running into this exception.

Some relevant code (I can post more if needed):

From main:

int degree = (input.nextInt() + 1);
int A[] = new int[degree];
int B[] = new int[degree];

for(int i = 0; i < degree; i++)
    A[i] = input.nextInt();
for(int i = 0; i < degree; i++)
    B[i] = input.nextInt();
product = karatsuba(A, B, degree); // LINE 22

From karatsuba:

static int[] karatsuba(int[] A, int[] B, int degree) {

    int[] A_hi = new int[degree / 2];
    int[] A_lo = new int[degree / 2];
    int[] B_hi = new int[degree / 2];
    int[] B_lo = new int[degree / 2];

    int[] m1 = new int[degree / 2];
    int[] m2 = new int[degree / 2];

    for(int i = (degree / 2); i < degree; i++) {
        A_hi[i - degree / 2] = A[I]; // LINE 50
        B_hi[i - degree / 2] = B[i];
        System.out.println(A_hi[i - degree / 2] + " " + A[i] + "   " + B_hi[i - degree / 2] + " " + B[i]);
    }

    for(int i = 0; i < (degree / 2); i++) {
        A_lo[i] = A[i];
        B_lo[i] = B[i];
        m1[i] = A_lo[i] + A_hi[i];
        m2[i] = B_lo[i] + B_hi[i];
    }  

    int[] r = new int[(degree * 2) - 1];
    int[] r_m = karatsuba(m1, m2, (degree / 2)); // LINE 63
    int[] r_lo = karatsuba(A_lo, B_lo, (degree / 2));
    int[] r_hi = karatsuba(A_hi, B_hi, (degree / 2));

From there I load the r_ arrays into r[] for returning to main. Here is a sample input that is used to load A[] and B[]. I'm using arrays for polynomial multiplication, the values being coefficients.

I'm not very familiar with this exception, but from what I understand, ArrayIndexOutOfBoundsException: 0 means I'm trying to access an array using index 0 when that index doesn't exist in the bounds of the array.

My confusion is, for A[] and B[], I verified that input was getting the correct numbers, so it's initialized and has values up to degree. And for A_hi and B_hi, I initialize the arrays, and load values one by one. I checked to see what values were being loaded into A_hi[] and B_hi[] with this line:

System.out.println(A_hi[i - degree / 2] + " " + A[i] + "   " + B_hi[i - degree / 2] + " " + B[i]);

Which led to this output –– so the values are being loaded how I intend.

So which array am I accessing with 0 that isn't properly initialized? Or is there another problem that I'm not understanding?

Here is the full error list

Upvotes: 0

Views: 90

Answers (1)

John Bollinger
John Bollinger

Reputation: 180048

Your code is prone to performing an out-of-bounds array access. Specifically, consider this simplified variation:

int[] A_hi = new int[degree / 2];

for(int i = (degree / 2); i < degree; i++) {
    A_hi[i - degree / 2] = 1;
}

Array A_hi has degree / 2 elements, and you set degree - degree / 2 elements. But if the value of degree is odd then degree - degree / 2 is one greater than degree / 2, so you overrun the array bounds on the last iteration. In particular, if degree == 1 then there is only one iteration, with i == 0, and A_hi has length zero. That will produce exactly the exception you observe.

Upvotes: 2

Related Questions