Ошибка в алгоритме Карацубы для Длинной арифметики

Пытаюсь сделать библиотеку с длинными числами. И возникла проблема, которую я пытался уже неделю исправить. Проблема заключается в том, что до меня тупо не доходит где проблема в моем коде. А конкретней проблема в реализации алгоритма умножения Карацубы

Есть массив Bits, который хранит в себе коэффициенты разложения длинного числа в системе счисления 2^32.

    private uint[] Bits;
    private const Int64 Base = (long)UInt32.MaxValue + 1;

Сам метод умножения принимает массивы Bits 2-х экземпляров и выдает массив (результат умножения)

public uint[] KaratsubaMultiplication(uint[] x, uint[] y)
    {
        int maxLength = 0;
        if (x.Length > y.Length) maxLength = x.Length;
        else maxLength = y.Length;
        uint[] result = new uint[maxLength * 2];
        if (maxLength == 1)
        {
            ulong mul = (ulong)x[0] * (ulong)y[0];
            if (mul >= Base)
            {
                result[0] = (uint)mul;
                result[1] = (uint)(mul >> 32);
            }
            else result[0] = (uint)mul;
        }
        else
        {
            //a
            uint[] BitsX = ExtendArray(x, maxLength);
            //b
            uint[] BitsY = ExtendArray(y, maxLength);
            //а1 первая часть числа a (тк с конца массив у меня)
            uint[] a1 = TakeElements(BitsX, BitsX.Length / 2, BitsX.Length / 2);
            //a2 вторая часть числа a
            uint[] a2 = TakeElements(BitsX, BitsX.Length / 2);
            //b1 первая часть числа b
            uint[] b1 = TakeElements(BitsY, BitsY.Length / 2, BitsY.Length / 2);
            //b2 вторая часть числа b
            uint[] b2 = TakeElements(BitsY, BitsY.Length / 2);
            //Произведение первых частей чисел
            uint[] a1b1 = KaratsubaMultiplication(a1, b1);
            //Произведение вторых частей чисел
            uint[] a2b2 = KaratsubaMultiplication(a2, b2);
            //Сумма произведений первых и вторых частей
            uint[] a1b1Suma2b2 = Addition(a1b1, a2b2);
            // (a1+a2)(b1+b2) - (a1b1 + a2b2), то что перед - это вот эта переменная хах
            uint[] ab = KaratsubaMultiplication(Addition(a1, a2), Addition(b1, b2));
            ab = Substraction(ab, a1b1Suma2b2);
            result = Addition(Finalize(a1b1, BitsX.Length), Finalize(ab, BitsX.Length / 2));
            result = Addition(result, a2b2);
        }
        result = Normalize(result);
        return result;
    }

Метод вычитания:

public static uint[] Substraction(uint[] x, uint[] y)
    {
        if (x.Length > y.Length)
            y = NormalizeArrays(y, x.Length);
        else x = NormalizeArrays(x, y.Length);
        uint[] result = new uint[x.Length];
        ulong carry = 0;
        int i = 0;
        for (i = 0; i < x.Length; i++)
        {
            if (x[i] - carry < y[i])
            {
                result[i] = (uint)((ulong)Base + x[i] + carry - y[i]);
                carry = 1;
            }
            else
            {
                result[i] = (uint)(x[i] + carry - y[i]);
                carry = 0;
            }
        }
        result = Normalize(result);
        return result;
    }

Метод сложения:

public static uint[] Addition(uint[] x, uint[] y, long radix = Base)
    {
        if (x.Length > y.Length) y = NormalizeArrays(y, x.Length);
        else if (y.Length > x.Length) x = NormalizeArrays(x, y.Length);
        uint[] result = new uint[x.Length + y.Length];
        ulong carry = 0;
        int i = 0;
        if (radix == Base)
        {
            for (; i < x.Length; i++)
            {
                ulong sum = x[i] + y[i] + carry;
                result[i] = (uint)sum;
                carry = sum >> 32;
            }
        }
        else
        {
            for (; i < x.Length; i++)
            {
                ulong sum = x[i] + y[i] + carry;
                result[i] = (uint)(sum % (ulong)radix);
                carry = sum / (ulong)radix;
            }
        }
        if (carry != 0) result[i] = (uint)carry;
        result = Normalize(result);
        return result;
    }

Работаю в системе счисления 2^32. И в массиве Bits хранятся коэффициенты разложения длинного числа в обратном порядке

Все дополнительные методы для работы кода:

private static uint[] ExtendArray(uint[] array, int length)
    {
        uint[] temp = new uint[length + length % 2];
        Array.Copy(array, temp, array.Length);
        return temp;
    }
    public static uint[] TakeElements(uint[] array, int length, int startIndex = 0)
    {
        uint[] temp = new uint[length];
        Array.Copy(array, startIndex, temp, 0, length);
        return temp;
    }
/// <summary>
    /// Подстраивает массив меньшей длины к массиву с большей
    /// </summary>
    /// <param name="array"></param>
    /// <param name="length"></param>
    /// <returns></returns>
    private static uint[] NormalizeArrays(uint[] array, int length)
    {
        uint[] temp = new uint[length];
        Array.Copy(array, temp, array.Length);
        return temp;
    }
    /// <summary>
    /// Удаляет не лидирующие 0 в массиве
    /// </summary>
    /// <param name="value"></param>
    /// <returns></returns>
    private static uint[] Normalize(uint[] value)
    {
        for (int i = value.Length - 1; i >= 0; i--)
        {
            if (value[i] != 0)
            {
                uint[] temp = new uint[i + 1];
                Array.Copy(value, 0, temp, 0, i + 1);
                return temp;
            }
        }
        return new uint[] { 0 };
    }
    static uint[] Finalize(uint[] res, int n)
    {
        uint[] temp = new uint[res.Length + n];
        for (int i = 0; i < res.Length; i++)
            temp[i + n] = res[i];
        return temp;
    }

Проверял код на числах 635115234552377 и 423523523623. Которые были спарсены из строки.

Проверить код можно просто передав в метод умножения Карацубы 2 массива, {1240623673, 147874} и {2616728615, 98} это числа 635115234552377 и 423523523623

и получаю {14491652, 960651648, 835046072, 755855689}

я ожидаю увидеть 268986242044270826190301871, но получаю 59885057380827124403963171489844109316 эти числа уже в 10 системе счисления.

Видел очень много реализаций данного метода, но ни одна мне до конца не была понятна.

ДОПОЛНЕНИЕ:

в методе умножение карацубы под конец в метод Finalize я передал не prod1 а prod2 а в конце к результату добавил prod1 а не prod2. (Код в вопросе тоже изменил)

Такой ход привел меня к правильному ответу, и на радостях я решил умножить число 268986242044270826190301871 на само себя. Ожидал получить 72353598409099050336288860303289482073245694106100641, но получаю 72353598409098710053921939364826055592126409756992417. И все еще не понял в чем ошибка.

ДОПОЛНЕНИЕ:

Основываясь на статью в википедии

я изменил и подкорректировал метод. (Код в вопросе изменен)

Возникло пару вопросов. В википедии без умножения к результату добовляют a1b1 то есть произведение первых частей чисел.

Но правильный ответ я получу только если поменяю a1b1 с a2b2 и обратно. Но работает только для примера с 635115234552377 и 423523523623.

Если же я умножу число 268986242044270826190301871 само на себя и высчитаю произведение 2 способами ( то есть прибавлять буду сначала a1b1 а 2 способ a2b2), то в любом случае получу не правильный ответ.