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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 154, средняя оценка - 4.95
vpupkin
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
29.04.2011, 13:44     Длинная арифметика. Умножение двух длинных чисел. #1
Есть 2 числа, храняющиеся в int векторах, нужна функция, которая возвращает их произведение также в виде вектора.
Либо простой и понятно описанный алгоритм, по которому можно такое сделать.
Заранее спасибо.
P.S. в гугл отправлять не надо-разбираться со сложными алгоритмами вроде БПФ у меня нет ни времени, ни желания.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
01.05.2011, 07:43     Длинная арифметика. Умножение двух длинных чисел. #41
Спрошу в этой темке...
Как быстро работает swap?
Не хочу писать
Код
 if (a>b) {...} else {почти то же самое}
Хочу написать просто
if (a>b) swap(a,b);
Но боюсь, что времени много пожрет.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
01.05.2011, 10:50     Длинная арифметика. Умножение двух длинных чисел. #42
Цитата Сообщение от diagon Посмотреть сообщение
Спрошу в этой темке...
Как быстро работает swap?
быстро. Оптимизация по скорости без необходимости - зло.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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;
}
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;
}
Так они там в перевернутом виде хранились... Мда. А я-то думал...
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,693
01.05.2011, 15:57     Длинная арифметика. Умножение двух длинных чисел. #45
diagon, я уже выкладывал в эту тему программу вычисления факториала)
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
01.05.2011, 16:01     Длинная арифметика. Умножение двух длинных чисел. #46
У вас это не в 130 строк сделано
Да и у меня он вычисляется как обычный, и есть полезная для ТСа готовая функция умножения.
Вообще хотел рекурсивное вычисление факториала сделать, но как это сделать с помощью векторов не додумался.
neske
01.05.2011, 16:09
  #47

Не по теме:

Ну просто у вас сделано не совсем рационально, много лишних действий.
Да и умножение двух длинных я тоже выкладывал)

silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
02.05.2011, 10:27     Длинная арифметика. Умножение двух длинных чисел. #48
vpupkin, у меня, кстати, тоже в перевёрнутом виде... Совсем забыл предупредить...
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,693
02.05.2011, 11:27     Длинная арифметика. Умножение двух длинных чисел. #49
silent_1991, дак а без перевернутого вида там хрен и реализуешь) разряды добавлять, сдвигать.. надо это))
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
02.05.2011, 11:37     Длинная арифметика. Умножение двух длинных чисел. #50
neske, но предупредить всё же следовало, а то сходу ведь и не поймёшь)))
Програмер_80лвл
15 / 15 / 1
Регистрация: 17.10.2012
Сообщений: 96
Записей в блоге: 1
11.04.2013, 00:00     Длинная арифметика. Умножение двух длинных чисел. #51
Цитата Сообщение от silent_1991 Посмотреть сообщение
мать моя... Вы что же, не в состоянии написать умножение столбиком? Алгоритм я, например, помню с начальной школы, а если бы и не помнил - загуглил бы, на первой странице точно был бы алгоритм. А дальше дело техники...
Так Почему бы тебе не написать ему пример от 0 до конца ?*
а? или ты слова на ветер бросаеш ?
Вот Тут читал Факторниал Нужен я вот старый код для факториал выщитует любой факториал но будет оч долго щитать после 1000 но впринципе мне хватало...
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
char *My_Factorial(int f)
{
    char *name;
    char C[4],A[10000],B[10000],D[10000];
    char E[]="123456789";
    int i,j,k,l,m,n,o,p,q,r,s,t;
    for(i=0;i<9999;i++)
    {
        A[i]='0';
        B[i]='0';
        D[i]='0';
    }
    A[9998]='1';
    A[9999]='\0';
    B[9999]='\0';
    D[9999]='\0';
    //f -> scanf
    for(i=1;i<=f;i++)
    {
        itoa(i,C,10);
        k=strlen(C);
        for(j=k;j>0;j--)
        {
            n=(C[j-1]-48);
            s=(abs(j-k));
            for(l=9998;l>=3;l--)
            {
                m=A[l]-48;
                o=B[l-s]-48;
                p=n*m+o;
                r=p%10;
                q=(int)(p-r)/10;
                if(p<10)
                {
                    r=p;
                    q=0;
                }
                B[l-s]=r+48;
                B[l-s-1]=q+48;
            }
            for(l=9999;l>0;l--)
            {
                m=B[l-1]-48;
                o=D[l-1]-48;
                p=m+o;
                r=p%10;
                q=(int)(p-r)/10;
                if(p<10){r=p;q=0;}
                D[l-1]=r+48;
                D[l-2]+=q;
            }
            for(l=0;l<9999;l++)B[l]='0';
        }
        strcpy(A,D);
        for(l=0;l<9999;l++)D[l]='0';
    }
    int xz=strlen(A);
    name=new char[xz];
    name[0]=NULL;
    name=strpbrk(A,E);
    name[0]=NULL;
    return name;
}
удачи
metaluga145
243 / 244 / 20
Регистрация: 08.04.2013
Сообщений: 927
11.04.2013, 00:07     Длинная арифметика. Умножение двух длинных чисел. #52
Может я, конечно, не сильно в тему буду. Но как написать длинную арифметику для любых действительных чисел с экономией места, то есть в один int помещать не 1 цифру, а 8(кажется 8 или 7 должно влезть)? Как это все правильно и оптимально оформить?
silent_1991
11.04.2013, 08:25
  #53

Не по теме:

Цитата Сообщение от Програмер_80лвл Посмотреть сообщение
Так Почему бы тебе не написать ему пример от 0 до конца ?*
А мне оно надо?

Croessmah
11.04.2013, 09:26
  #54

Не по теме:

Програмер_80лвл, Вы обладаете удивительной способностью отвечать на темы(это не единственная тема), в которые никто не заглядывал уже несколько лет.

Somebody
11.04.2013, 09:48
  #55

Не по теме:

Цитата Сообщение от Croessmah Посмотреть сообщение
Програмер_80лвл, Вы обладаете удивительной способностью отвечать на темы(это не единственная тема), в которые никто не заглядывал уже несколько лет.
Программер прокачался уже до 81лвл, и ему надо 100 сообщений для смены ника.

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.04.2016, 21:14     Длинная арифметика. Умножение двух длинных чисел.
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Ferrari F1
Заблокирован
295 / 281 / 62
Регистрация: 27.01.2015
Сообщений: 1,893
Записей в блоге: 1
Завершенные тесты: 1
27.04.2016, 21:14     Длинная арифметика. Умножение двух длинных чисел. #56
На всякий случай (умножение длинного числа на длинное), вдруг кому-либо понадобится...
Проверки на корректность ввода нет, работает лишь с натуральными числами.
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
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
 
#include <string>
using std::string;
 
#include <algorithm>
 
#include <windows.h>
 
string& multOneDigit(const string& value1, const char& value2)
{
    static string result;
    result = "";
    unsigned digit(value2 - '0');
    switch (digit)
    {
    case 0:
        return result = "0";
        break;
    case 1:
        return result = value1;
        break;
    }
    unsigned temp(0);
    for (unsigned i(0); value1[i]; ++i)
    {
        temp += (value1[i] - '0') * digit;
        result.push_back(temp % 10 + '0');
        temp /= 10;
    }
    if (temp)
        result.push_back(temp % 10 + '0');
    return result;
}
 
string& multDigitWithZeros(const string& value1, const string& value2)
{
    static string result;
    result = multOneDigit(value1, value2[0]);
    if (value2.length() == 1)
        return result;
    return result = string(value2.begin() + 1, value2.end()) + result;
}
 
string& toAdd(string& value1, string& value2)
{
    static string result;
    result = "";
    unsigned i(value1.length()), j(value2.length());
    if (i < j)
        for (; i < j; ++i)
            value1.push_back('0');
    else if (j < i)
        for (; j < i; ++j)
            value2.push_back('0');
    unsigned temp(0);
    for (i = 0; i < j; ++i)
    {
        temp += value1[i] + value2[i] - 2 * '0';
        result.push_back(temp % 10 + '0');
        temp /= 10;
    }
    if (temp)
        result.push_back(temp % 10 + '0');
    return result;
}
 
const string& toMult(string& value1, string& value2)
{
    static string result;
    result = "0";
    if (value1.length() < value2.length())
        swap(value1, value2);
    reverse(value1.begin(), value1.end()),
        reverse(value2.begin(), value2.end());
    for (unsigned i(0), count(value2.length()); i < count; ++i)
    {
        string temp(&value2[i], 1);
        for (unsigned j(0); j < i; ++j)
            temp.push_back('0');
        result = toAdd(multDigitWithZeros(value1, temp), result);
    }
    reverse(result.begin(), result.end());
    return result;
}
 
int main(void)
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    string value1("470827"), value2("60013");
    cout << toMult(value1, value2) << endl;
    system("pause");
    return 0;
}
Yandex
Объявления
27.04.2016, 21:14     Длинная арифметика. Умножение двух длинных чисел.
Ответ Создать тему
Опции темы

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