ArrayIndexOutOfBoundsException：Karatsuba 实现中的 0

Question

我正在实施 Karatsuba 算法，运行遇到此异常。

一些相关代码（如果需要我可以 post 更多）：

来自主要：

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

来自 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));

从那里我将 r_ 数组加载到 r[] 以返回到 main。 Here is a sample input 用于加载A[]和B[]。我正在使用数组进行多项式乘法，值是系数。

我不是很熟悉这个异常，但据我了解，ArrayIndexOutOfBoundsException: 0 意味着我正在尝试使用索引 0 访问一个数组，而该索引没有'不存在于数组的边界内。

我的困惑是，对于 A[] 和 B[]，我验证了输入得到了正确的数字，所以它被初始化并且具有最大程度的值。对于 A_hi 和 B_hi，我初始化数组，并一个一个地加载值。我用这一行检查了哪些值被加载到 A_hi[] 和 B_hi[] 中：

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

Which led to this output –– 所以这些值正在按照我的意图加载。

那么我访问的是哪个未正确初始化的 0 数组？或者还有其他我不理解的问题？

Here is the full error list

Answer 1

您的代码容易执行越界数组访问。具体来说，考虑这个简化的变体：

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

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

数组A_hi有degree / 2个元素，你设置了degree - degree / 2个元素。但是，如果 degree 的值是奇数，则 degree - degree / 2 比 degree / 2 大 1，因此您在最后一次迭代时超出了数组边界。特别是，如果 degree == 1 则只有一次迭代，其中 i == 0 和 A_hi 的长度为零。这将产生您观察到的异常。

ArrayIndexOutOfBoundsException：Karatsuba 实现中的 0

ArrayIndexOutOfBoundsException: 0 in Karatsuba Implementation

java

karatsuba