1

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

Есть массив 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), то в любом случае получу не правильный ответ.

11
  • вы не описали ни саму проблему, ни способ, как её воспроизвести.
    – tym32167
    23 авг 2019 в 12:35
  • Алгоритм не правильно решает. Я же написал проверял на 2-х числах и ответ очевидно не правильный. А название говорит о том что ошибка в коде. 23 авг 2019 в 12:57
  • 3
    давайте я попробую по другому пояснить. Вот смотрите, пришел я поглядеть на вашу проблему. У меня времени мало, я впустую его стараюсь не тратить. Смотрю на ваш вопрос, и я не понимаю значения фразы Алгоритм не правильно решает Что решает? Какие входные данные принимает, каккой ответ выдает и какой должен выдать? - Я уже на этом этапе теряю интерес к вопросу. Но ок, допустим я даю ещё один шанс, я хочу скопировать ваш код и запустить и увидеть вашу проблему. Я копирую набор ваших функций и ничего не просиходит. Получается, после 5 минут работы я всё ещё не знаю даже в чем проблема.
    – tym32167
    23 авг 2019 в 13:04
  • а сидеть, разбираться в том, что вы и где имели ввиду, и как надо ваш код использовать и гадать где он не работает - этого никто не будет делать. Ваша задача - максимально облегчить читателю работу. Подробнее можете про это почитать тут и тут. Это не гарантирует, что вы получите ответ, но сильно увеличивает ваши шансы.
    – tym32167
    23 авг 2019 в 13:07
  • Да, но задавая вопрос я все таки надеюсь, что мне ответ даст человек разбирающийся в этой скажем так сфере. Ну или мне придется с самого начала все расписывать, что да как работает. А тут ну по моему мнению все понятно. Алгоритм Карацубы это алгоритм умножения 2 чисел. В моем случае это массивы и возвращает так же массив. Все же в коде видно. Просто если я сейчас всю библиотеку которая уже есть сюда напишу у читателя будет интерес разбираться во всем? Я самое важное вынес. Но спасибо за совет постараюсь дополнить вопрос чем нибудь. 23 авг 2019 в 13:38

1 ответ 1

1

Я решил проблему. Для начала заменил метод вычитания.

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

Так же метод умножения изменил и подкоректировал

public uint[] KaratsubaMultiplication(uint[] x, uint[] y, long radix = Base)
    {
        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 (radix == Base)
            {
                //if(mul > 10)
                if (mul > Base)
                {
                    result[0] = (uint)mul;
                    result[1] = (uint)(mul >> 32);
                    //result[0] = (uint)mul % 10;
                    //result[1] = (uint)mul / 10;
                }
                else result[0] = (uint)mul;
            }
            else
            {
                result[0] = (uint)(mul % (ulong)radix);
                result[1] = (uint)(mul / (ulong)radix);
            }
        }
        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, radix);

            //Произведение вторых частей чисел
            uint[] a2b2 = KaratsubaMultiplication(a2, b2, radix);

            //Сумма произведений первых и вторых частей
            uint[] a1b1Suma2b2 = Addition(a1b1, a2b2, radix);

            // (a1+a2)(b1+b2) - (a1b1 + a2b2), то что перед - это вот эта переменная хах
            uint[] ab = KaratsubaMultiplication(Addition(a1, a2, radix), Addition(b1, b2, radix), radix);

            ab = Substraction(ab, a1b1Suma2b2, radix);

            result = Addition(Finalize(a1b1, BitsX.Length), Finalize(ab, BitsX.Length / 2), radix);
            result = Addition(result, a2b2, radix);
        }
        result = Normalize(result);
        return result;
    }

И самое бесячая ошибка в коде. Это например ulong sum = x[i] + y[i] + carry; тк x[i] и y[i] это uint, то на сколько я понял и результат выдает в uint а потом уже к ulong приводит. И если будет переполнение то sum будет не правильной. Так что я в везде в таких моментах (в сложении и вычитании) например x[i] привожу к ulong.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.