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

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

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

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

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

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

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

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

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

Умножение двух длинных чисел - C++
Приветствую, помогите исправить процедуру умножения двух длинных чисел: void CALL_TYPE Multiply(unsigned char *u,int N, unsigned char...

Длинная арифметика. Перемножение двух больших чисел - C++
Насчет алгоритма выполнения не могу пока что сказать ничего. Дело в том, что после того, как ввожу первое число и нажимаю Enter, каретка...

Длинная арифметика. Перемножение двух больших чисел. Пропуск итераций - C++
Программа работает корректно с числами, оканчивающимися не на нуль. Пробовал выводить слово "iter" в каждом проходе цикла, но при работе с...

55
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
30.04.2011, 22:09 #31
Вот вам, откопал у себя, когда-то делал класс длинной арифметики...

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
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 22:11  [ТС] #32
Длинное на короткое элементарно пишется, и я об этом писал уже в этой темке...
Покопаюсь в вашем исходнике, спасибо.
И сумма/разность тоже знаю.
0
neske
1501 / 868 / 84
Регистрация: 26.03.2010
Сообщений: 2,973
30.04.2011, 22:20 #33
Для вычисления факториала умножение двух длинных не нужно)
Второе,
Цитата Сообщение от vpupkin Посмотреть сообщение
И вообще, паскалю в этом плане кошернее, у него элементы массива могут быть отрицательные. Если писать через массивы на с++, то число по идее залезет в отрицательные элементы, и ничего хорошего из этого не выйдет.
смысла в этом вообще не вижу.
0
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
30.04.2011, 22:22 #34
Цитата Сообщение от neske Посмотреть сообщение
смысла в этом вообще не вижу
Я тоже...

Цитата Сообщение от neske Посмотреть сообщение
Для вычисления факториала умножение двух длинных не нужно
Ну... Если берётся факториал длинного числа, то нужно)))
0
neske
1501 / 868 / 84
Регистрация: 26.03.2010
Сообщений: 2,973
30.04.2011, 22:27 #35
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
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 22:29  [ТС] #36
Число получается до 2х раз длинее, чем его множители, и просто приписать слева еденичку не получится. А так как во всех алгоритмах, что я видел, была реализация на паскале, то по идее должно вытянутся либо влево, либо вправо. Учитывая, что при счете в столбик суммы уезжают влево, то вытянется тоже влево, т.е. заедет за 0.
...
Извиняюсь за этот бред, в половину четвертого ночи у меня проблемы с формулировкой мыслей.
silent_1991, что делает эта строчка?
C++
1
prod = prod._multi_ten(i);
Впрочем неважно, суть алгоритма в том, что он делает столько же длинных сумм и умножений длинного на короткое, сколько и цифр в наименьшем числе?) В общем то да, просто... А по времени это не чревато? Скажем, 10^2000 * 10^2500 за секунду уложится?
0
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
30.04.2011, 22:31 #37
neske, ну, если столбиком - то да, взорвётся)) А если БПФ, думаю, выдержит, родимый)))

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

Добавлено через 24 секунды
vpupkin, разумеется, не уложится, столбик - прожорливая штука.
2
neske
1501 / 868 / 84
Регистрация: 26.03.2010
Сообщений: 2,973
30.04.2011, 22:41 #38
vpupkin, кстати, в том линке, где еще непонятные 111, это ll1, то есть (long long)1
1
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
30.04.2011, 22:44  [ТС] #39
Эм... Всмысле 1? Еденица, записанная с помощью 8 байт? о_О
0
neske
1501 / 868 / 84
Регистрация: 26.03.2010
Сообщений: 2,973
30.04.2011, 23:21 #40
Взял алгоритм по той ссылке, которую я тебе дал, убрал только эту 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
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
01.05.2011, 07:43 #41
Спрошу в этой темке...
Как быстро работает swap?
Не хочу писать
Код
 if (a>b) {...} else {почти то же самое}
Хочу написать просто
if (a>b) swap(a,b);
Но боюсь, что времени много пожрет.
0
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
01.05.2011, 10:50 #42
Цитата Сообщение от diagon Посмотреть сообщение
Спрошу в этой темке...
Как быстро работает swap?
быстро. Оптимизация по скорости без необходимости - зло.
1
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
01.05.2011, 15:38 #43
Вычисляет факториал с помощью умножения длинного на длинное, с того же сайта взято. Писал для себя, чтобы в векторах и длинной арифметике попрактиковаться, поэтому извиняюсь за быдло-код.
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <iostream>
#include <vector>
#include <algorithm>
void readlong(std::vector<int> &a); //чтение
void writelong(std::vector<int> a){  //вывод
    for (size_t i=0; i< a.size();i++) std::cout << a[i];}
short compare(std::vector<int> a,std::vector<int> b); //сравнение
void nol(std::vector<int> &a,std::vector<int> &b); //добавление нулей в начало(для суммы)
std::vector<int> sum(std::vector<int> a, std::vector <int> b); //сумма
std::vector<int> smult(std::vector<int> a,int b); //умножение длинного на короткое
void ten(std::vector<int> &a,int b);//добавление b нулей в конец
long long vectoint(std::vector<int> a);//перевод вектора в int
std::vector<int> mult (std::vector<int> a, std::vector<int> b); //умножение длинного на длинное
std::vector<int> factorial(std::vector<int> b); //факториал
int main(){
 
    std::vector<int> a,b,c,rez;
    readlong(a);
    writelong(factorial(a));
    return 0;
}
void readlong(std::vector<int> &a){
    char c;
    for(;;){
        std::cin.get(c);
        if ((c==' ')||(c=='\n'))break;
        a.push_back(c-48);
    }
}
short compare(std::vector<int> a,std::vector<int> b){
    if (a.size()>b.size()) return 1;
    if (a.size()<b.size()) return 2;
    for (size_t i=0; i<a.size();i++){
    if (a[i]>b[i]) return 1;
    if (a[i]<b[i]) return 2;
    }
    return 0;
 
}
void nol(std::vector<int> &a,std::vector<int> &b){
    if (a.size()==b.size()) return;
    if (a.size()>b.size()) std::swap(a,b);
    for (size_t i=0; i< a.size()-b.size(); i++){
        a.insert(a.begin(),0);
    }
}
std::vector<int> sum(std::vector<int> a, std::vector<int> b){
    std::vector<int>c;
    short p=0;
    nol(a,b);
    c.assign(a.size(),0);
    for (short i = a.size()-1; i >= 0; i--) {
        c[i]=a[i]+b[i]+p;
        p=0;
        if (c[i]>9) {c[i]-=10; p=1;}
    }
    if (p) c.insert(c.begin(),1);
    return c;
}
std::vector<int> smult(std::vector<int> a,int b){
    std::vector<int> c;
    if (!b||!a[0]) {c.push_back(0); return c; }
    for (size_t i = 0; i <a.size(); i++) {
        if (i==c.size()) c.push_back(0);
        c[i]=a[i]*b;
    }
    for (size_t i=c.size()-1; i > 0; i--) {
        if (c[i]>9) {
            c[i-1]+=c[i]/10;
            c[i]%=10;
            }
        }
    if (c[0]<10) return c;
    short p=c[0];
    c[0]%=10;
    for(;;){
        if (!(p/10)) break;
        c.insert(c.begin(),p/10);
        p/=10;
    }
    return c;
}
void ten(std::vector<int>& a,int b){
    for (; b; b--)
        a.push_back(0);
}
std::vector<int> factorial(std::vector<int>(b)){
    std::vector<int> a,o,c;
    a.push_back(1);
    o.push_back(1);
    c.push_back(1);
    for(long int i=0;i<vectoint(b)-1;i++){
        c=sum(c,o);
        a=mult(c,a);
    }
    return a;
}
long long vectoint(std::vector<int> a){
    long long c=0,q=1;
    for (short i = a.size()-1; i >=0; i--) {
        c+=a[i]*q;
        q*=10;
    }
    return c;
}
std::vector<int> mult (std::vector<int> a, std::vector<int> b)
{
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());
    std::vector<int> c(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 = c[i+j] + a[i] * (j < b.size() ? b[j] : 0) + carry;
            c[i+j] = cur % 10;
            carry = cur / 10;
        }
 
    while (c.size() > 1 && c.back() == 0)
        c.pop_back();
        reverse(c.begin(),c.end());
        return c;
}
1
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
01.05.2011, 15:55  [ТС] #44
Цитата Сообщение от diagon Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
std::vector<int> mult (std::vector<int> a, std::vector<int> b)
{
        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());
        std::vector<int> c(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 = c[i+j] + a[i] * (j < b.size() ? b[j] : 0) + carry;
                        c[i+j] = cur % 10;
                        carry = cur / 10;
                }
 
        while (c.size() > 1 && c.back() == 0)
                c.pop_back();
                reverse(c.begin(),c.end());
                return c;
}
Так они там в перевернутом виде хранились... Мда. А я-то думал...
0
neske
1501 / 868 / 84
Регистрация: 26.03.2010
Сообщений: 2,973
01.05.2011, 15:57 #45
diagon, я уже выкладывал в эту тему программу вычисления факториала)
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.05.2011, 15:57
Привет! Вот еще темы с ответами:

длинная арифметика. Умножение большого числа на малое - C++
Столкнулся с небольшой проблемой: при умножении большого числа (примерно 9 знаков) на небольшое выводит непонятно что, но с малыми числами...

Длинная арифметика: сумма двух строк - C++
int One = strlen(BufOne); int Two = strlen(BufTwo); int MaxL = max(One, Two); char *Result = (char*)malloc(MaxL); int a; double...

Арифметика длинных чисел с плавающей запятой - C++
Добрый вечер, есть ли у кого исходники основных операций * / + - больших чисел с плавающей запятой? Например дано: char * a =...

Длинная арифметика, деление чисел - C++
http://www.cyberforum.ru/attachment.php?attachmentid=393890&amp;stc=1&amp;d=1398936287 Помоги с решием , желательно код.Заранее спасибО!


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

Или воспользуйтесь поиском по форуму:
45
Yandex
Объявления
01.05.2011, 15:57
Ответ Создать тему
Опции темы

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