Концептуальная проблема умножения BigInt C ++

Question

Я собираю небольшую библиотеку BigInt на C ++ для использования в моем языке программирования.

Структура выглядит следующим образом:

short digits[ 1000 ];
int   len;

У меня есть функция, которая преобразует строкув bigint, разделив его на отдельные символы и поместив их в digits.

Все цифры в цифрах перевернуты, поэтому число 123 будет выглядеть следующим образом:

digits[0]=3 digits[1]=3 digits[2]=1

Мне уже удалось закодировать функцию добавив , котораяработает отлично.

Работает примерно так:

overflow = 0
for i ++ until length of both numbers exceeded:
  add numberA[ i ] to numberB[ i ]
  add overflow to the result
  set overflow to 0
  if the result is bigger than 10:
    substract 10 from the result
    overflow = 1
  put the result into numberReturn[ i ]

(Переполнение - это в данном случае то, что происходит, когда я добавляю 1 к 9: вычленяем 10 из 10, добавляем 1 к переполнению, переполняемдобавляется к следующей цифре)

Итак, подумайте о том, как хранятся два числа, например:

   0 | 1 | 2
   ---------
A  2   -   -
B  0   0   1 

Вышеприведенное представляет digits из bigints 2 (A) и 100(В).- означает неинициализированные цифры, к ним нет доступа.

Таким образом, добавление указанного числа работает нормально: начните с 0, добавьте 2 + 0, перейдите к 1, добавьте 0, перейдите к 2, добавьте 1

Но:

Когда я хочу выполнить умножение с вышеупомянутой структурой, моя программа заканчивает тем, что делает следующее:

Начинается с 0, умножается на 2с 0 (eek), перейдите к 1, ...

Так что очевидно, что для умножения я должен получить такой порядок:

   0 | 1 | 2
   ---------
A  -   -   2
B  0   0   1 

Тогда все будетбыть ясным: начать с 0, умножить 0 на 0, перейти к 1, умножить 0 на 0, перейти к 2, умножить 1 на 2

• Как мне получитьdigits в правильную форму для умножения?
• Я не хочу делать перемещение или переворачивание массива - мне нужна производительность!

Answer 1

Ваш пример в вопросе, на мой взгляд, чрезмерно инженерный. Ваш подход в конечном итоге будет даже медленнее, чем обычное длинное умножение, из-за количества сдвигов умножения и сложений. Не ограничивайте себя работой с одной базовой цифрой за раз, когда вы можете умножить примерно на 9 за раз !. Конвертируйте строку base10 в greatval, и затем сделайте с ней операции. Не выполнять операции непосредственно со строкой. Вы сойдете с ума. Вот некоторый код, который демонстрирует сложение и умножение. Измените M, чтобы использовать больший тип. Вы также можете использовать std :: vector, но тогда вы пропустите некоторые оптимизации.

#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <cstdio>
#include <iomanip>

#ifdef _DEBUG
#include <assert.h>
#define ASSERT(x) assert(x)
#else
#define ASSERT(x)
#endif

namespace Arithmetic
{
    const int M = 64;
    const int B = (M-1)*32;

    struct Flags
    {
        Flags() : C(false),Z(false),V(false),N(false){}
        void Clear()
        {
            C = false;
            Z = false;
            V = false;
            N = false;
        }
        bool C,Z,V,N;
    };

    static unsigned int hvAdd(unsigned int a, unsigned int b, Flags& f)
    {
        unsigned int c;
        f.Clear();
        //b = -(signed)b;
        c = a + b;

        f.N = (c >> 31UL) & 0x1;
        f.C = (c < a) && (c < b);
        f.Z = !c;
        f.V = (((signed)a < (signed)b) != f.N);

        return c;
    }

    static unsigned int hvSub(unsigned int a, unsigned int b, Flags& f)
    {
        unsigned int c;
        f.Clear();
        c = a - b;

        //f.N = ((signed)c < 0);
        f.N = (c >> 31UL) & 0x1;
        f.C = (c < a) && (c < b);
        f.Z = !c;
        f.V = (((signed)a < (signed)b) != f.N);

        return c;
    }


    struct HugeVal
    {
        HugeVal()
        {
            std::fill(part, part + M, 0);
        }
        HugeVal(const HugeVal& h)
        {
            std::copy(h.part, h.part + M, part);
        }
        HugeVal(const std::string& str)
        {
            Flags f;
            unsigned int tmp = 0;

            std::fill(part, part + M, 0);

            for(unsigned int i=0; i < str.length(); ++i){
                unsigned int digit = (unsigned int)str[i] - 48UL;
                unsigned int carry_last = 0;
                unsigned int carry_next = 0;
                for(int i=0; i<M; ++i){
                    tmp = part[i]; //the value *before* the carry add
                    part[i] = hvAdd(part[i], carry_last, f);
                    carry_last = 0;
                    if(f.C)
                        ++carry_last;
                    for(int j=1; j<10; ++j){
                        part[i] = hvAdd(part[i], tmp, f);
                        if(f.C)
                            ++carry_last;
                    }
                }
                part[0] = hvAdd(part[0], digit, f);
                int index = 1;
                while(f.C && index < M){
                    part[index] = hvAdd(part[index], 1, f);
                    ++index;
                }
            }
        }
        /*
        HugeVal operator= (const HugeVal& h)
        {
            *this = HugeVal(h);
        }
        */
        HugeVal operator+ (const HugeVal& h) const
        {
            HugeVal tmp;
            Flags f;
            int index = 0;
            unsigned int carry_last = 0;
            for(int j=0; j<M; ++j){
                if(carry_last){
                    tmp.part[j] = hvAdd(tmp.part[j], carry_last, f);
                    carry_last = 0;
                }
                tmp.part[j] = hvAdd(tmp.part[j], part[j], f);
                if(f.C)
                    ++carry_last;
                tmp.part[j] = hvAdd(tmp.part[j], h.part[j], f);
                if(f.C)
                    ++carry_last;
            }
            return tmp;
        }
        HugeVal operator* (const HugeVal& h) const
        {
            HugeVal tmp;

            for(int j=0; j<M; ++j){
                unsigned int carry_next = 0;
                for(int i=0;i<M; ++i){

                    Flags f;

                    unsigned int accum1 = 0;
                    unsigned int accum2 = 0;
                    unsigned int accum3 = 0;
                    unsigned int accum4 = 0;

                    /* Split into 16-bit values */
                    unsigned int j_LO = part[j]&0xFFFF;
                    unsigned int j_HI = part[j]>>16;
                    unsigned int i_LO = h.part[i]&0xFFFF;
                    unsigned int i_HI = h.part[i]>>16;

                    size_t index = i+j;
                    size_t index2 = index+1;

                    /* These multiplications are safe now. Can't overflow */
                    accum1 = j_LO * i_LO;
                    accum2 = j_LO * i_HI;
                    accum3 = j_HI * i_LO;
                    accum4 = j_HI * i_HI;


                    if(carry_next){ //carry from last iteration
                        accum1 = hvAdd(accum1, carry_next, f); //add to LSB
                        carry_next = 0;
                        if(f.C) //LSB produced carry
                            ++carry_next;
                    }

                    /* Add the lower 16-bit parts of accum2 and accum3 to accum1 */
                    accum1 = hvAdd(accum1, (accum2 << 16), f);
                    if(f.C)
                        ++carry_next;
                    accum1 = hvAdd(accum1, (accum3 << 16), f);
                    if(f.C)
                        ++carry_next;



                    if(carry_next){ //carry from LSB
                        accum4 = hvAdd(accum4, carry_next, f); //add to MSB
                        carry_next = 0;
                        ASSERT(f.C == false);
                    }

                    /* Add the higher 16-bit parts of accum2 and accum3 to accum4 */
                    /* Can't overflow */
                    accum4 = hvAdd(accum4, (accum2 >> 16), f);
                    ASSERT(f.C == false);
                    accum4 = hvAdd(accum4, (accum3 >> 16), f);
                    ASSERT(f.C == false);
                    if(index < M){
                        tmp.part[index] = hvAdd(tmp.part[index], accum1, f);
                        if(f.C)
                            ++carry_next;
                    }
                    carry_next += accum4;
                }
            }
            return tmp;
        }
        void Print() const
        {
            for(int i=(M-1); i>=0; --i){

                printf("%.8X", part[i]);
            }
            printf("\n");
        }
        unsigned int part[M];
    };

}


int main(int argc, char* argv[])
{

    std::string a1("273847238974823947823941");
    std::string a2("324230432432895745949");

    Arithmetic::HugeVal a = a1;
    Arithmetic::HugeVal b = a2;

    Arithmetic::HugeVal d = a + b;
    Arithmetic::HugeVal e = a * b;

    a.Print();
    b.Print();
    d.Print();
    e.Print();
    system("pause");
}

Answer 2

1. Почему вы используете short для хранения цифр в [0..9] a char будет достаточно
2. Вы неправильно думаете о умножении. В случае умножения вам необходим двойной цикл for, который умножает B на каждую цифру в A и суммирует их со смещением с правильной степенью десяти.

РЕДАКТИРОВАТЬ: Поскольку некоторые анонимные проголосовали без комментария, это в основном алгоритм умножения:

bigint prod = 0
for i in A
    prod += B * A[i] * (10 ^ i)

Умножение B на A[i] выполняется дополнительным циклом for, где вы также отслеживаете перенос. (10 ^ i) достигается путем смещения индексов назначения, поскольку bigint находится в базе 10.

Answer 3

Андреас прав, что вам нужно умножить одно число на каждую цифру другого и соответствующим образом суммировать результаты. Я думаю, лучше умножить более длинное число на цифры более короткого. Если вы сохраняете десятичные цифры в вашем массиве, действительно будет достаточно char, но если вам нужна производительность, возможно, вам следует рассмотреть больший тип. Я не знаю, какая у вас платформа, но в случае x86, например, вы можете использовать 32-битные числа и аппаратную поддержку для получения 64-битного результата 32-битного умножения.

Answer 4

Я создаю небольшую библиотеку BigInt на C ++ для использования в моем языке программирования.

Почему? Существует несколько превосходных существующих библиотек bigint (например, gmp , tommath ), которые вы можете просто использовать без необходимости писать свои собственные с нуля. Создание собственного - большая работа, и результат вряд ли будет таким же хорошим с точки зрения производительности. (В частности, написание быстрого кода для выполнения умножения и деления намного сложнее, чем кажется на первый взгляд.)