Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.51/198: Рейтинг темы: голосов - 198, средняя оценка - 4.51
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31

Длинная арифметика. Умножение двух длинных чисел.

29.04.2011, 13:44. Показов 39637. Ответов 55
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Есть 2 числа, храняющиеся в int векторах, нужна функция, которая возвращает их произведение также в виде вектора.
Либо простой и понятно описанный алгоритм, по которому можно такое сделать.
Заранее спасибо.
P.S. в гугл отправлять не надо-разбираться со сложными алгоритмами вроде БПФ у меня нет ни времени, ни желания.
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
29.04.2011, 13:44
Ответы с готовыми решениями:

Длинная арифметика: умножение двух длинных чисел
Всем привет! Снова к Вам за помощью. Алгоритм умножения двух длинных чисел: void...

Длинная арифметика. Сложение длинных чисел
Здравствуйте! Впервые за все время изучения C++ решил реализовать длинную арифметику, используя строки. К сожалению, программа прошла...

Длинная арифметика. Сложение длинных чисел
Добрый день, Киберфорум! Изучаю длинную арифметику и нашел вот такой простейший пример сложения длинных чисел "в столбик". Не...

55
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 21:30  [ТС]
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от vpupkin Посмотреть сообщение
Есть код на паскале
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Procedure Multiplication(A, B : DlChislo; Var C : DlChislo);
 Var I, J : Integer; P : Digit; VspRez : 0..99;
  Begin
    Zero(C);//Обнуление массива C
    For I := 1 To Dlina(A) Do {Цикл по количеству цифр
                               в первом числе}
     Begin
        P := 0; {Первоначально перенос равен нулю}
        For J := 1 To Dlina(B) Do {Цикл по количеству цифр
                                   во втором числе}
         Begin
           VspRez := A[I] * B[J] + P + C[I + J - 1];
           C[I + J - 1] := VspRez Mod 10; {Очередное значение цифры в
                                           разряде I + J - 1}
           P := VspRez Div 10 {Перенос в следующий разряд}
         End;
       C[I + J] := P {последний перенос может быть отличен от нуля,
                      запишем его в пока ещё свободный разряд}
     End
  End;
Перевел, как смог(паскаля не знаю) на с++
В чем ошибка?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
int main(){
    int a[]={1,2,3},b[]={4,5,6},c[5]={0},i,j,x,p;
    for (i = 0; i < 3; i++) {
        p=0;
        for (j = 0; j < 3; j++) {
            x=a[i]*b[j]+p+c[i+j];
            c[i+j]=x%10;
            p=x/10;
        }
    c[i+j+1]=p;
    }
    for (i = 0; i < 6; i++) {
    std::cout << c[i];
    }
    return 0;
}
И все-таки, может кто-нибудь помочь? Очень нужно. Заранее спасибо.
0
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
30.04.2011, 21:34
Фигня какая-то ввёл 5 5, он мне 3125 выдаёт...
0
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 21:35  [ТС]
Ты бы почитал комментарии вверху кода программы для начала, она возводит число a в степень b.
5 в 5й степени равно 3125.
1
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
30.04.2011, 21:42
тогда почему на 100 в 10 выдаётся фигня какая-то со всеми числами котррые есть на земле?
0
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 21:51  [ТС]
Ну число там немаленькое получается, но в проге видимо баг...
0
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
30.04.2011, 21:53
2 в 64 верно вычислил, а вот 100 в 10... да это ладно 10 в 100 ваще фигня, три строчки командной строки тирешками и всем числовым полем забиты)))
0
1552 / 918 / 193
Регистрация: 26.03.2010
Сообщений: 3,105
30.04.2011, 21:55
kiborg_18, вообще, там и ограничения на вводимые данные написаны.
Измените основание, и будет вам счастье.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <vector>
#include <iomanip>
#define BASE 1000000
#define LEN 6
 
void power (std::vector <int> &, const int);
 
int main()
{
    std::vector <int> num;
    int var, pow;
 
    std::cin >> var >> pow;
    num.push_back (var);
 
    for (int i = 0; i < pow - 1; i++)
        power (num, var);
 
    std::cout << num.back ();
    for (int i = num.size () - 2; i >= 0; i--)
        std::cout << std::setfill ('0') << std::setw (LEN) << num[i];
 
    return 0;
}
 
void power (std::vector <int> &vec, const int var)
{
    int carry = 0;
    for (int i = 0; i < vec.size () || carry; i++)
    {
        if (i == vec.size ()) vec.push_back (0);
        carry += vec[i] * var;
        vec[i] = carry % BASE;
        carry /= BASE;
    }
}

Не по теме:

Можете баловаться )

0
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 22:03  [ТС]
С факториалом баловатся удобнее будет, 29!=8841761993739701954543616000000
Но для его реализации нужно будет использовать алгоритм умножения длинного числа на длинное, и таким образом мы из оффтопа возвращаемся к теме.
Если это умножение в столбик такое простое, то почему нигде нету его реализаций на с++?
Обещаю, что если мне дадут реализацию этого алгоритма, то через полчаса выложу код, который будет выводить факториал. Сможете играть сколько влезет - просто вбивайте число размером в пару тысяч и сидите с открытым ртом.
0
Эксперт С++
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
30.04.2011, 22:06
vpupkin, мать моя... Вы что же, не в состоянии написать умножение столбиком? Алгоритм я, например, помню с начальной школы, а если бы и не помнил - загуглил бы, на первой странице точно был бы алгоритм. А дальше дело техники...
0
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 22:08  [ТС]
Я гуглю второй день-реализации только на паскале, которого я не знаю. Пытался перевести-не пашет.
И вообще, паскалю в этом плане кошернее, у него элементы массива могут быть отрицательные. Если писать через массивы на с++, то число по идее залезет в отрицательные элементы, и ничего хорошего из этого не выйдет.
0
Эксперт С++
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
30.04.2011, 22:09
Вот вам, откопал у себя, когда-то делал класс длинной арифметики...

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Verylong operator*(const Verylong &left, const Verylong &right)
{
    if (left == Verylong::zero || right == Verylong::zero)
        return Verylong::zero;
 
    Verylong result;
    Verylong prod;
 
    unsigned digit;
 
    for (size_t i = 0; i < right._verylong.size(); ++i)
    {
        digit = right._verylong[i] - '0';
 
        prod = left * digit;
        prod = prod._multi_ten(i);
 
        result += prod;
    }
 
    result._sign = Verylong::pos;
 
    if (left._sign != right._sign)
        result._sign = Verylong::neg;
 
    return result;
}
Добавлено через 35 секунд
Надеюсь, умножение длинного на короткое вы написать в состоянии?..

Ну и сумму двух длинных.
1
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 22:11  [ТС]
Длинное на короткое элементарно пишется, и я об этом писал уже в этой темке...
Покопаюсь в вашем исходнике, спасибо.
И сумма/разность тоже знаю.
0
1552 / 918 / 193
Регистрация: 26.03.2010
Сообщений: 3,105
30.04.2011, 22:20
Для вычисления факториала умножение двух длинных не нужно)
Второе,
Цитата Сообщение от vpupkin Посмотреть сообщение
И вообще, паскалю в этом плане кошернее, у него элементы массива могут быть отрицательные. Если писать через массивы на с++, то число по идее залезет в отрицательные элементы, и ничего хорошего из этого не выйдет.
смысла в этом вообще не вижу.
0
Эксперт С++
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
30.04.2011, 22:22
Цитата Сообщение от neske Посмотреть сообщение
смысла в этом вообще не вижу
Я тоже...

Цитата Сообщение от neske Посмотреть сообщение
Для вычисления факториала умножение двух длинных не нужно
Ну... Если берётся факториал длинного числа, то нужно)))
0
1552 / 918 / 193
Регистрация: 26.03.2010
Сообщений: 3,105
30.04.2011, 22:27
silent_1991, у меня комп взорвется, если я буду вычислять 879837492373874923 в факториале )

Просто привели пример с 29!, и про реализацию сказали, я и возразил.

!
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// output : var!
 
#include <iostream>
#include <vector>
#include <iomanip>
#define BASE 1000000
#define LEN 6
 
void power (std::vector <int> &, const int);
 
int main()
{
    std::vector <int> num;
    int var;
 
    std::cin >> var;
    num.push_back (1);
 
    for (int i = 2; i <=var  ; i++)
        power (num, i);
 
    std::cout << num.back ();
    for (int i = num.size () - 2; i >= 0; i--)
        std::cout << std::setfill ('0') << std::setw (LEN) << num[i];
 
    return 0;
}
 
void power (std::vector <int> &vec, const int var)
{
    int carry = 0;
    for (int i = 0; i < vec.size () || carry; i++)
    {
        if (i == vec.size ()) vec.push_back (0);
        carry += vec[i] * var;
        vec[i] = carry % BASE;
        carry /= BASE;
    }
}
0
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 22:29  [ТС]
Число получается до 2х раз длинее, чем его множители, и просто приписать слева еденичку не получится. А так как во всех алгоритмах, что я видел, была реализация на паскале, то по идее должно вытянутся либо влево, либо вправо. Учитывая, что при счете в столбик суммы уезжают влево, то вытянется тоже влево, т.е. заедет за 0.
...
Извиняюсь за этот бред, в половину четвертого ночи у меня проблемы с формулировкой мыслей.
silent_1991, что делает эта строчка?
C++
1
prod = prod._multi_ten(i);
Впрочем неважно, суть алгоритма в том, что он делает столько же длинных сумм и умножений длинного на короткое, сколько и цифр в наименьшем числе?) В общем то да, просто... А по времени это не чревато? Скажем, 10^2000 * 10^2500 за секунду уложится?
0
Эксперт С++
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
30.04.2011, 22:31
neske, ну, если столбиком - то да, взорвётся)) А если БПФ, думаю, выдержит, родимый)))

Добавлено через 46 секунд
vpupkin, умножает длинное на 10 ^ i (простым приписыванием нулей в конец).

Добавлено через 24 секунды
vpupkin, разумеется, не уложится, столбик - прожорливая штука.
2
1552 / 918 / 193
Регистрация: 26.03.2010
Сообщений: 3,105
30.04.2011, 22:41
vpupkin, кстати, в том линке, где еще непонятные 111, это ll1, то есть (long long)1
1
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 22:44  [ТС]
Эм... Всмысле 1? Еденица, записанная с помощью 8 байт? о_О
0
1552 / 918 / 193
Регистрация: 26.03.2010
Сообщений: 3,105
30.04.2011, 23:21
Взял алгоритм по той ссылке, которую я тебе дал, убрал только эту ll1.
Могли бы и вы так попробовать.
+ Я тут взял основание 10, для простоты примера.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <vector>
#include <iomanip>
#include <string>
#include <cstdlib>
#define BASE 10
#define LEN 1
 
typedef std::vector <int> type;
 
void readlong (type &);
void mult (type &, type &, type &);
 
int main()
{
    type a, b, rez;
 
    std::cout << "First long number: ";
    readlong (a);
    std::cout << "Second long number: ";
    readlong (b);
 
    mult (a, b, rez);
 
    std::cout << rez.back ();
    for (int i = rez.size () - 2; i >= 0; i--)
        std::cout << rez[i];
 
    return 0;
}
 
void readlong (type &vec)
{
    std::string str;
    std::cin >> str;
 
    for (int i = str.size (); i > 0; i--)
        vec.push_back (atoi (str.substr (i - LEN, LEN).c_str()));
}
 
void mult (type &a, type &b, type &rez)
{
    rez.resize (a.size() + b.size());
    for (int i = 0; i < a.size(); ++i)
        for (int j = 0, carry = 0; j < b.size() || carry; ++j)
        {
            long long cur = rez[i+j] + a[i] * (j < b.size() ? b[j] : 0) + carry;
            rez[i+j] = cur % BASE;
            carry = cur / BASE;
        }
 
    while (rez.size() > 1 && rez.back() == 0)
        rez.pop_back();
}
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
30.04.2011, 23:21

Длинная арифметика(вычитание длинных целых чисел)
Добрый вечер! Очень нужна помощь. Мне нужно написать программы для сложения больших целых чисел(разрядности около 200), вычитания и что-то...

Длинная арифметика: реализовать операцию сложения длинных чисел
я пыталась сложить два больших числа но при запуске после ввода всё крошится #include &lt;bits/stdc++.h&gt; using...

Реализовать оператор сравнения в классе длинных чисел (длинная арифметика)
Здравствуйте, дорогие форумчане. Недавно назрел вопрос, как бы сделать сравнение чисел длинной арифметики в дальнейшем коде? Сравнение...

Длинная арифметика: сложение и умножение чисел
Нужно реализовать сложение и умножение больших чисел. Есть идея, необходима помощь в реализации на C++. Собственно, идеи такие... ...

Сложение двух чисел (длинная арифметика)
Нужно реализовать длинную арифметику (сложение двух больших чисел), но на экран выводятся не понятные символы. Я подозреваю, что a =...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Новые блоги и статьи
Поиск всех путей на ориентированном графе. Linux
dcc0 02.07.2026
Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .
Сам себя обучал rest api
anaschu 02.07.2026
Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .
rest api anylogic - выполнение модели на своём русском сайте
anaschu 02.07.2026
Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .
Где деньги лежат
kumehtar 02.07.2026
Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .
Krabik для WoW 3.3.5a, многоязычный
AmbA 02.07.2026
Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .
Алиса нашла кучу ошибок компиляции и запуска в проекте, который без проблем компилировался и запускался)))
anaschu 30.06.2026
Я пока посмеюся, но завтра проверю. А вообще интерсно. Дал алисе файл, в котором точно нет ошибок компиляции и запуска, и попросил их найти. Нашла кучу))) Критические ошибки, мешающие компиляции и. . .
сукцессия 16. Общий обзор, в основном что бы другие ии поняли
anaschu 29.06.2026
# Передаточный документ: модель микоризной сукцессии (для нового чата) Этот документ предназначен для того, чтобы новый чат Claude мог продолжить работу без необходимости заново разбираться в. . .
сукцессия 15 неявная схема
anaschu 29.06.2026
Алиса Калибровка параметров симбиотической модели: технический обзор Содержание: Введение Постановка проблемы Технические аспекты реализации Процесс внедрения изменений
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru