Как реализовать сложение / умножение bignum с нуля в C++

Question

Я начал писать библиотеку bignum с вектором шорт для представления значения, функцией печати и поддержкой отрицательных чисел. Однако я не могу найти хороший способ реализовать длинное сложение, например:

 123
+123
----
 246

Последний код, который у меня есть, который не дает segfault, это:

void add(unsigned long long b)
    {   
        for(long long i=v.size()-1;i>=0;--i)
        {
            if((b+v[i])<10)
                v[i]+=b;
            else // Carry
                {
                    if(i==0) // 1st digit
                    {
                        v.push_front(1); // Can't be more than 1
                    }
                    else
                        v[i-1]++; // Increment digit to the left
                }

        }
    }

, но сложение с переносом неверно (10+1 - 21)

РЕДАКТИРОВАТЬ: Это реализовано как класс

Answer 1

Рассмотрим передачу 11 в функцию:
Если vector[i] >= 0, то b+vector[i] > 11, таким образом b+vector[i]<10 никогда не будет правдой.

Несколько других вещей:

• Вы используете vector а также vЯ уверен, что должен быть только один.

• i>0 должно быть i>=0иначе цикл пропускает первый элемент.

• Наличие каждого элемента, представляющего цифру, немного излишне. Вы можете иметь каждый элемент, представляющий 0-65535 (диапазон беззнакового короткого замыкания). Просто измените 10 на 65535 ниже. Или 0-10000 также может иметь смысл, так как тогда разбить на цифры будет проще.

• Разве функция не должна принимать параметр типа вашего класса BigNum?

• Цикл от первого до последнего элемента будет иметь больше смысла.

Лучше (не проверено) add функция может выглядеть так:

const int BASE = 10;
void add(unsigned long long b)
{
    for (int i = 0; b > 0 && i < v.size(); ++i)
    {
        unsigned long long val = b + v[i];
        b = val / BASE;
        v[i] = val % BASE;
    }
    // if adding more digits
    while (b > 0)
    {
        v.push_back(b % BASE);
        b /= BASE;
    }
}