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

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

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

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

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

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

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

55
1552 / 918 / 193
Регистрация: 26.03.2010
Сообщений: 3,105
29.04.2011, 13:48
гугл, гугл.. по вашему это сложные алгоритмы? http://e-maxx.ru/algo/big_integer
1
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
29.04.2011, 13:52  [ТС]
Видел это, так и не смог заставить работать этот код. Пробовал также и без класса, base сделал равным 10-0 эффекта.
0
1552 / 918 / 193
Регистрация: 26.03.2010
Сообщений: 3,105
29.04.2011, 13:59
Это я когда-то писал, может вам поможет. Работа с вектором, но тут длинное на короткое умножается. Под свое задание заточите сами.

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
/*Входной файл INPUT.TXT в первой строке содержит числа A и B, разделенные пробелом. (1 <= A <= 9, 1 <= B <= 104)
В выходной файл OUTPUT.TXT выведите одно число – результат возведения в степень, без лидирующих нулей.*/
 
#include <iostream>
#include <vector>
#include <iomanip>
#define BASE 1000000000
#define LEN 9
 
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;
    }
}
1
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
29.04.2011, 14:03  [ТС]
Длинное на короткое я тоже писал, правда без векторов.
Банально умножил каждую цифру массива на b, затем прошелся циклом с конца и собрал остатки.
А вот как длинное на длинное-не представляю.
0
1552 / 918 / 193
Регистрация: 26.03.2010
Сообщений: 3,105
29.04.2011, 14:05
Возьмите мой код за основу, а алгоритм умножения с вышеупомянутого сайта.
0
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
29.04.2011, 14:13  [ТС]
Я предпочитаю разбираться в алгоритмах с помощью дебаггера, так более нагляднее=)
А в вышеупомянутом сайте меня смущает миллиардная система счисления а также вот этот код
C++
1
1ll
0
Эксперт С++
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
29.04.2011, 18:08
В чём сложность реализовать умножение столбиком? Школьный алгоритм, реализуется без каких-либо изменений.
0
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
29.04.2011, 18:15  [ТС]
Ну на бумажке-то просто, но программно, во-первых придется реализовывать еще и сравнение этих чисел, чтобы большее было вверху, а также суммы n слагаемых, где n-количество цифр в наименьшем числе.
Настолько не оптимальный алгоритм мне тоже не нужен, по идее программно это делается проще.
0
Эксперт С++
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
29.04.2011, 18:25
Цитата Сообщение от vpupkin Посмотреть сообщение
по идее программно это делается проще
Зря вы так думаете.Столбиком - самый простой способ. Дальше идут Карацуба и Фурье.
0
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
29.04.2011, 18:37  [ТС]
Ну даже я понимаю, что сравнение и длинную сумму делать необязательно, можно это как-то оптимизировать... Поэтому прошу выложить исходник данной функции, можно без векторов.
Наверняка завалялся у кого-нибудь... Заранее спасибо.
0
32 / 32 / 6
Регистрация: 24.02.2011
Сообщений: 126
29.04.2011, 18:52
А есть ограничения на длину перемножаемых чисел? А то можно результат хранить в 64-битном массиве, намного быстрее будет.
0
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
29.04.2011, 18:54  [ТС]
Есть, результат не более 6000 символов=)
А хранить по несколько цифр в 1 элементе массива дело, конечно, оптимизирующее, но обращаться к ним неудобно будет...
0
Эксперт С++
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
29.04.2011, 19:32
vpupkin, вас не поймёшь. Сначала вы просите простой и понятный алгоритм - вам советуют столбиком, вы говорите "ненене, слишком медленно". Вам говорят, что быстрее - сложнее, вы говорите "даже я понимаю, что можно оптимизировать". Понимаете - оптимизируйте. Ладно, вам говорят, что можно хранить число не поцыферно, а блоками, вы "ненене, сложно обращаться". Уважаемый, закон природы - за то, чтобы сделать одну вещь проще, нужно платить усложнением другой вещи.
1
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 20:52  [ТС]
Есть код на паскале
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:09
G++
comparision between signed and unsigned integer expression
C++
1
2
3
 for (int i = 0; i < vec.size () || carry; i++)
    {
        if (i == vec.size ()) vec.push_back (0);
0
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 21:13  [ТС]
Цитата Сообщение от kiborg_18 Посмотреть сообщение
G++
comparision between signed and unsigned integer expression
C++
1
2
3
 for (int i = 0; i < vec.size () || carry; i++)
    {
        if (i == vec.size ()) vec.push_back (0);
???
С реализацией в виде векторов я потом разбираться буду, сейчас хотя бы на массивах написать хочу, их отлаживать проще. Перевел с паскаля - не работает...
0
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
30.04.2011, 21:19
neske, В вашем коде компиллятор даёт ошибку на
C++
1
2
3
for (int i = 0; i < vec.size () || carry; i++)
    {
        if (i == vec.size ()) vec.push_back (0);
comparision between signed and unsigned integer expression
Что делать? не компиллируется g++
0
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 21:21  [ТС]
Суровый у вас компилятор однако... Предупреждение за ошибку считает
C++
1
2
3
for (unsigned int i = 0; i < vec.size () || carry; i++)
    {
        if (i == vec.size ()) vec.push_back (0);
Так должен скомпилировать
0
30.04.2011, 21:25

Не по теме:

vpupkin, может там педантик врублен...

1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
30.04.2011, 21:25
Помогаю со студенческими работами здесь

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android
8Observer8 26.01.2026
Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
Установка Android SDK, NDK, JDK, CMake и т.д.
8Observer8 25.01.2026
Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf
8Observer8 25.01.2026
Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly
8Observer8 24.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
моя боль
iceja 24.01.2026
Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .
Модель сукцессии микоризы
anaschu 24.01.2026
Решили писать научную статью с неким РОманом
http://iceja.net/ математические сервисы
iceja 20.01.2026
Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
http://iceja.net/ сервер решения полиномов
iceja 18.01.2026
Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru