Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 154, средняя оценка - 4.95
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
#1

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

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

Есть 2 числа, храняющиеся в int векторах, нужна функция, которая возвращает их произведение также в виде вектора.
Либо простой и понятно описанный алгоритм, по которому можно такое сделать.
Заранее спасибо.
P.S. в гугл отправлять не надо-разбираться со сложными алгоритмами вроде БПФ у меня нет ни времени, ни желания.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.04.2011, 13:44     Длинная арифметика. Умножение двух длинных чисел.
Посмотрите здесь:

Арифметика длинных чисел с плавающей запятой C++
C++ Умножение длинных чисел
длинная арифметика. Умножение большого числа на малое C++
C++ Длинная арифметика. Перемножение двух больших чисел
C++ Длинная арифметика. Перемножение двух больших чисел. Пропуск итераций
C++ Умножение двух длинных чисел
C++ Длинная арифметика, деление чисел
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
neske
1463 / 830 / 69
Регистрация: 26.03.2010
Сообщений: 2,830
29.04.2011, 13:48     Длинная арифметика. Умножение двух длинных чисел. #2
гугл, гугл.. по вашему это сложные алгоритмы? http://e-maxx.ru/algo/big_integer
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
29.04.2011, 13:52  [ТС]     Длинная арифметика. Умножение двух длинных чисел. #3
Видел это, так и не смог заставить работать этот код. Пробовал также и без класса, base сделал равным 10-0 эффекта.
neske
1463 / 830 / 69
Регистрация: 26.03.2010
Сообщений: 2,830
29.04.2011, 13:59     Длинная арифметика. Умножение двух длинных чисел. #4
Это я когда-то писал, может вам поможет. Работа с вектором, но тут длинное на короткое умножается. Под свое задание заточите сами.

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;
    }
}
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
29.04.2011, 14:03  [ТС]     Длинная арифметика. Умножение двух длинных чисел. #5
Длинное на короткое я тоже писал, правда без векторов.
Банально умножил каждую цифру массива на b, затем прошелся циклом с конца и собрал остатки.
А вот как длинное на длинное-не представляю.
neske
1463 / 830 / 69
Регистрация: 26.03.2010
Сообщений: 2,830
29.04.2011, 14:05     Длинная арифметика. Умножение двух длинных чисел. #6
Возьмите мой код за основу, а алгоритм умножения с вышеупомянутого сайта.
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
29.04.2011, 14:13  [ТС]     Длинная арифметика. Умножение двух длинных чисел. #7
Я предпочитаю разбираться в алгоритмах с помощью дебаггера, так более нагляднее=)
А в вышеупомянутом сайте меня смущает миллиардная система счисления а также вот этот код
C++
1
1ll
silent_1991
Эксперт С++
4951 / 3027 / 149
Регистрация: 11.11.2009
Сообщений: 7,026
Завершенные тесты: 1
29.04.2011, 18:08     Длинная арифметика. Умножение двух длинных чисел. #8
В чём сложность реализовать умножение столбиком? Школьный алгоритм, реализуется без каких-либо изменений.
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
29.04.2011, 18:15  [ТС]     Длинная арифметика. Умножение двух длинных чисел. #9
Ну на бумажке-то просто, но программно, во-первых придется реализовывать еще и сравнение этих чисел, чтобы большее было вверху, а также суммы n слагаемых, где n-количество цифр в наименьшем числе.
Настолько не оптимальный алгоритм мне тоже не нужен, по идее программно это делается проще.
silent_1991
Эксперт С++
4951 / 3027 / 149
Регистрация: 11.11.2009
Сообщений: 7,026
Завершенные тесты: 1
29.04.2011, 18:25     Длинная арифметика. Умножение двух длинных чисел. #10
Цитата Сообщение от vpupkin Посмотреть сообщение
по идее программно это делается проще
Зря вы так думаете.Столбиком - самый простой способ. Дальше идут Карацуба и Фурье.
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
29.04.2011, 18:37  [ТС]     Длинная арифметика. Умножение двух длинных чисел. #11
Ну даже я понимаю, что сравнение и длинную сумму делать необязательно, можно это как-то оптимизировать... Поэтому прошу выложить исходник данной функции, можно без векторов.
Наверняка завалялся у кого-нибудь... Заранее спасибо.
eXXXXXXXXXXX
30 / 30 / 3
Регистрация: 24.02.2011
Сообщений: 126
29.04.2011, 18:52     Длинная арифметика. Умножение двух длинных чисел. #12
А есть ограничения на длину перемножаемых чисел? А то можно результат хранить в 64-битном массиве, намного быстрее будет.
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
29.04.2011, 18:54  [ТС]     Длинная арифметика. Умножение двух длинных чисел. #13
Есть, результат не более 6000 символов=)
А хранить по несколько цифр в 1 элементе массива дело, конечно, оптимизирующее, но обращаться к ним неудобно будет...
silent_1991
Эксперт С++
4951 / 3027 / 149
Регистрация: 11.11.2009
Сообщений: 7,026
Завершенные тесты: 1
29.04.2011, 19:32     Длинная арифметика. Умножение двух длинных чисел. #14
vpupkin, вас не поймёшь. Сначала вы просите простой и понятный алгоритм - вам советуют столбиком, вы говорите "ненене, слишком медленно". Вам говорят, что быстрее - сложнее, вы говорите "даже я понимаю, что можно оптимизировать". Понимаете - оптимизируйте. Ладно, вам говорят, что можно хранить число не поцыферно, а блоками, вы "ненене, сложно обращаться". Уважаемый, закон природы - за то, чтобы сделать одну вещь проще, нужно платить усложнением другой вещи.
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 20:52  [ТС]     Длинная арифметика. Умножение двух длинных чисел. #15
Есть код на паскале
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;
}
kiborg_18
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
30.04.2011, 21:09     Длинная арифметика. Умножение двух длинных чисел. #16
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);
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 21:13  [ТС]     Длинная арифметика. Умножение двух длинных чисел. #17
Цитата Сообщение от 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);
???
С реализацией в виде векторов я потом разбираться буду, сейчас хотя бы на массивах написать хочу, их отлаживать проще. Перевел с паскаля - не работает...
kiborg_18
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
30.04.2011, 21:19     Длинная арифметика. Умножение двух длинных чисел. #18
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++
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 21:21  [ТС]     Длинная арифметика. Умножение двух длинных чисел. #19
Суровый у вас компилятор однако... Предупреждение за ошибку считает
C++
1
2
3
for (unsigned int i = 0; i < vec.size () || carry; i++)
    {
        if (i == vec.size ()) vec.push_back (0);
Так должен скомпилировать
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.04.2011, 21:25     Длинная арифметика. Умножение двух длинных чисел.
Еще ссылки по теме:

C++ Длинная арифметика: умножение двух длинных чисел
Длинная арифметика: сумма двух строк C++
Длинная арифметика, сумма чисел C++
C++ Длинная арифметика. Сложение чисел
C++ Реализовать оператор сравнения в классе длинных чисел (длинная арифметика)

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

Или воспользуйтесь поиском по форуму:
silent_1991
30.04.2011, 21:25     Длинная арифметика. Умножение двух длинных чисел.
  #20

Не по теме:

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

Yandex
Объявления
30.04.2011, 21:25     Длинная арифметика. Умножение двух длинных чисел.
Ответ Создать тему
Опции темы

Текущее время: 14:08. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru