Блог

Главная - Вопросы по программированию - Эффективный способ умножения двух чисел, хранящихся в векторах

Эффективный способ умножения двух чисел, хранящихся в векторах

#c

#c

Вопрос:

В настоящее время я пытаюсь найти метод умножения двух чисел, хранящихся в векторе. У меня есть функция сложения для произвольно больших чисел. Есть ли лучший метод, чем просто выполнять умножение столбцов между каждой цифрой и складывать их вместе в сумму? Псевдокод для того, что у меня есть ниже.

 vector<int> total;
int carry = 0; //int to store carrying value if needed

//initialize v1 and v2
for each element i of v1:
vector<int> temp;

    for each element j of v2:
          get v1[i] * v2[j] and compute how much carrying is needed
          push adjusted product to temp

    push carry to temp and reset carry
    add(temp, total)

Комментарии:

1. Ваш псевдокод настолько похож на C , что с таким же успехом вы могли только что написать C . Похоже, вы пытаетесь реализовать длительное умножение. Наиболее значительное ускорение, которое вы могли бы сделать прямо сейчас, — это использовать что-то вроде std::vector<uint64_t> , чтобы ваши «цифры» были 64-разрядными значениями вместо предположительно базового 10. Тогда вам просто нужно реализовать двоичное преобразование в десятичное, если вы хотите это вывести. Представьте, как быстро можно умножать целые числа на тысячи битов, когда вы можете выполнять фрагменты по 64 бита за раз. Ваш цикл O (N ^ 2) будет в 400 раз быстрее, если уменьшить 20 цифр до 1 значения.

2. Ознакомьтесь с алгоритмом Карацубы , он может уменьшить количество умножений, которые вам нужно выполнить. Объединение его с предложением @ paddy о переходе на 64-разрядную версию должно иметь значение, если ваши числа большие.

3. да, Карацуба, и просто вся статья Википедии обо всех из них была бы полезна для чтения OP. В принципе, существуют более эффективные алгоритмы умножения, чем тот, который вы изучаете в начальной школе: en.wikipedia.org/wiki/Multiplication_algorithm

Метки: ,