基于byte[]的Karatsuba乘法器实现Bug排查求助

我正尝试实现一个不使用BigInteger类、用于计算两个等长byte数组乘积的Karatsuba算法。以下是我的代码，请求帮忙排查其中的Bug：

static public byte[] Karatsuba(byte[] X, byte[] Y, int N)
{
    if (N == 1)
    {
        int result = X[0] * Y[0];
        byte[] resArray = new byte[2] { (byte)(result % 10), (byte)(result / 10) };
        return resArray;
    }

    int half = N / 2;
    byte[] xLow, xHigh, yLow, yHigh;
    Split(X, half, out xLow, out xHigh);
    Split(Y, half, out yLow, out yHigh);

    byte[] z0 = Karatsuba(xLow, yLow, half);
    byte[] z2 = Karatsuba(xHigh, yHigh, half);
    byte[] z1;

    z1 = Karatsuba(Add(xLow, xHigh, half), Add(yLow, yHigh, half), half);
        
    z1 = Subtract(Subtract(z1, z0, half), z2, half);

    byte[] resultArray = new byte[2 * N];
    Array.Copy(z0, 0, resultArray, 0, z0.Length);
    Array.Copy(z1, 0, resultArray, half, z1.Length);
    Array.Copy(z2, 0, resultArray, 2 * half, z2.Length);

    return resultArray;
}

private static void Split(byte[] x, int half, out byte[] low, out byte[] high)
{
    low = new byte[half];
    high = new byte[half];
    Array.Copy(x, 0, low, 0, half);
    Array.Copy(x, half, high, 0, half);
}

private static byte[] Add(byte[] a, byte[] b, int length)
{
    byte[] result = new byte[length];
    byte carry = 0;

    for (int i = length - 1; i >= 0; i--)
    {
        byte sum = (byte)(a[i] + b[i] + carry);
        result[i] = (byte)(sum % 10);
        carry = (byte)(sum / 10);
    }

    return result;
}

private static byte[] Subtract(byte[] a, byte[] b, int length)
{
    int n = length;
    byte[] result = new byte[n];
    int carry = 0;

    for (int i = n - 1; i >= 0; i--)
    {
        int sub = a[i] - b[i]-carry;
        if (sub < 0)
        {
            sub += 10;
            carry = 1;
        }
        else
        {
            carry = 0;
        }

        result[i] = (byte)sub;
    }

    return result;
}

测试情况 #

• N = 4，X = 2185（对应byte数组[5,8,1,2]，低位在前），Y = 2185，输出结果为04416205，预期结果为04774225；
• 部分测试用例正常：N = 2，X = 11（对应byte数组[1,1]），Y = 22（对应byte数组[2,2]），输出结果0242与预期一致，且右侧首位数字总是符合预期。

问题分析与修复方案 #

1. 核心Bug点梳理 #

(1) 加减方法遍历方向错误

你的数组采用低位在低索引的存储方式（比如2185存在[5,8,1,2]中，索引0是个位），但Add和Subtract方法却从高位索引（length-1）开始计算，完全搞反了进位/借位的处理顺序，这是导致计算错误的核心原因。

(2) 加法未处理最终进位

两个length位的数相加可能产生最高位进位（比如99+99=198），原Add方法直接丢弃了这个进位，导致后续Karatsuba计算的输入长度缺失，结果偏差。

(3) 减法的长度参数错误

计算z1 = (xLow+xHigh)*(yLow+yHigh) - z0 - z2时，z1、z0、z2的长度都是2*half，但你传入half作为减法的长度参数，直接截断了高位数据，导致减法结果完全错误。

(4) 结果合并未处理进位

原代码只是将z0、z1、z2直接拷贝到对应位置，没有处理不同数位叠加产生的进位（比如z0的高位和z1的低位相加可能进位），最终结果的数位叠加逻辑失效。

2. 修复后的完整代码 #

static public byte[] Karatsuba(byte[] X, byte[] Y)
{
    // 统一输入长度，补0对齐
    int maxLen = Math.Max(X.Length, Y.Length);
    if (X.Length < maxLen) Array.Resize(ref X, maxLen);
    if (Y.Length < maxLen) Array.Resize(ref Y, maxLen);

    // 终止条件：单数位相乘
    if (maxLen == 1)
    {
        int result = X[0] * Y[0];
        byte[] resArray = result >= 10 ? new byte[2] { (byte)(result % 10), (byte)(result / 10) } : new byte[1] { (byte)result };
        return resArray;
    }

    int half = (maxLen + 1) / 2;
    byte[] xLow, xHigh, yLow, yHigh;
    Split(X, half, out xLow, out xHigh);
    Split(Y, half, out yLow, out yHigh);

    byte[] z0 = Karatsuba(xLow, yLow);
    byte[] z2 = Karatsuba(xHigh, yHigh);
    byte[] sumX = Add(xLow, xHigh);
    byte[] sumY = Add(yLow, yHigh);
    byte[] z1 = Karatsuba(sumX, sumY);
        
    z1 = Subtract(Subtract(z1, z0), z2);

    // 移位相加：z0不移位，z1左移half位，z2左移2*half位
    byte[] shiftedZ1 = ShiftLeft(z1, half);
    byte[] shiftedZ2 = ShiftLeft(z2, 2 * half);
    byte[] temp = AddArrays(z0, shiftedZ1);
    byte[] resultArray = AddArrays(temp, shiftedZ2);

    // 确保输出长度为2*原输入长度，补0对齐
    if (resultArray.Length < 2 * maxLen)
    {
        Array.Resize(ref resultArray, 2 * maxLen);
    }
    return resultArray;
}

private static void Split(byte[] x, int half, out byte[] low, out byte[] high)
{
    low = new byte[half];
    high = new byte[x.Length - half];
    Array.Copy(x, 0, low, 0, half);
    Array.Copy(x, half, high, 0, x.Length - half);
}

// 支持任意长度的数组加法，低位在前
private static byte[] Add(byte[] a, byte[] b)
{
    int maxLen = Math.Max(a.Length, b.Length);
    byte[] result = new byte[maxLen + 1];
    byte carry = 0;

    for (int i = 0; i < maxLen; i++)
    {
        byte digitA = i < a.Length ? a[i] : (byte)0;
        byte digitB = i < b.Length ? b[i] : (byte)0;
        int sum = digitA + digitB + carry;
        result[i] = (byte)(sum % 10);
        carry = (byte)(sum / 10);
    }

    if (carry > 0)
    {
        result[maxLen] = carry;
    }
    else
    {
        Array.Resize(ref result, maxLen);
    }
    return result;
}

// 支持任意长度的数组减法（确保a >= b，符合Karatsuba场景），低位在前
private static byte[] Subtract(byte[] a, byte[] b)
{
    byte[] result = new byte[a.Length];
    int borrow = 0;

    for (int i = 0; i < a.Length; i++)
    {
        byte digitA = a[i];
        byte digitB = i < b.Length ? b[i] : (byte)0;
        int sub = digitA - digitB - borrow;
        if (sub < 0)
        {
            sub += 10;
            borrow = 1;
        }
        else
        {
            borrow = 0;
        }
        result[i] = (byte)sub;
    }

    // 去掉高位多余的0
    int lastNonZero = result.Length - 1;
    while (lastNonZero > 0 && result[lastNonZero] == 0)
    {
        lastNonZero--;
    }
    Array.Resize(ref result, lastNonZero + 1);
    return result;
}

// 数组左移（低位补0，对应乘以10^shift）
private static byte[] ShiftLeft(byte[] arr, int shift)
{
    byte[] result = new byte[arr.Length + shift];
    Array.Copy(arr, 0, result, shift, arr.Length);
    return result;
}

// 多数组通用加法
private static byte[] AddArrays(byte[] a, byte[] b)
{
    int maxLen = Math.Max(a.Length, b.Length);
    byte[] result = new byte[maxLen + 1];
    byte carry = 0;

    for (int i = 0; i < maxLen; i++)
    {
        byte digitA = i < a.Length ? a[i] : (byte)0;
        byte digitB = i < b.Length ? b[i] : (byte)0;
        int sum = digitA + digitB + carry;
        result[i] = (byte)(sum % 10);
        carry = (byte)(sum / 10);
    }

    if (carry > 0)
    {
        result[maxLen] = carry;
    }
    else
    {
        Array.Resize(ref result, maxLen);
    }
    return result;
}

3. 修复说明 #

• 调整了Karatsuba方法的入参，不再强制传入长度，自动处理输入对齐；
• 修正了Add和Subtract的遍历方向，从低位（索引0）开始计算进位/借位；
• 新增了移位方法和通用数组加法，正确实现Karatsuba的结果合并逻辑；
• 处理了加法的最终进位和减法的高位冗余0，保证计算精度。

测试修复后的代码，N=4时输入2185×2185，将输出预期的04774225。

内容的提问来源于stack exchange，提问作者NarutoO