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

Умножение двух больших чисел - C++

Восстановить пароль Регистрация
 
ВладиславСултан
0 / 0 / 0
Регистрация: 31.05.2016
Сообщений: 7
16.06.2016, 17:48     Умножение двух больших чисел #1
дано два 40 значных числа,нужно перемножить их
http://e-maxx.ru/algo/big_integer от сюда и других тем с данного форума код не подходит. Не понимаю принципа работы
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.06.2016, 17:48     Умножение двух больших чисел
Посмотрите здесь:

C++ Сложение двух больших чисел
Умножение больших чисел C++
Умножение двух чисел в столбик C++
Умножение двух чисел в двоичной системе счисления C++
C++ Умножение двух длинных чисел
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
notAll
176 / 65 / 16
Регистрация: 27.05.2016
Сообщений: 182
Завершенные тесты: 2
17.06.2016, 00:15     Умножение двух больших чисел #2
Есть одна очень простая библиотека Boost.Multiprecision. Использовать очень легко, понимать особого труда не составляет - просто подключить заголовок и использовать:
C++
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
 
namespace mp = boost::multiprecision;
 
int main()
{
    mp::cpp_int a{"1234567890123456789012345678901234567890"}, b{"4578564242121325421213524321021212121"};
 
    std::cout << "a * b = " << a * b << std::endl;
}
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,651
17.06.2016, 10:07     Умножение двух больших чисел #3
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
///////////////////////////////////////////////////////////////////////////////
//1.
///////////////////////////////////////////////////////////////////////////////
//дано два 40 значных числа,нужно перемножить их
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits>
#include <string>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
typedef std::string     T_str;
///////////////////////////////////////////////////////////////////////////////
template < typename TT_base_int >
class   T_big_int
{
    //-------------------------------------------------------------------------
    using   T_values    =   std::vector< TT_base_int >;
    //-------------------------------------------------------------------------
    constexpr   static  const   TT_base_int
    BASE_VAL_MAX        =   std::numeric_limits< TT_base_int >::max();
 
    constexpr   static  const   TT_base_int
    ORDER_OF_FACTOR     =   log( BASE_VAL_MAX ) / log(10) / 2;
 
    constexpr   static  const   TT_base_int
    FACTOR              =   pow( 10,    ORDER_OF_FACTOR );
    //-------------------------------------------------------------------------
    T_values    values_;
    //-------------------------------------------------------------------------
public:
    //-------------------------------------------------------------------------
    T_big_int( T_str    const   &   digits )
    {
        set_values( digits );
    }
    //-------------------------------------------------------------------------
    T_big_int( TT_base_int  num     =   0 )
    {
        add_to_ind
            (
                num,
                0
            );
    }
    //-------------------------------------------------------------------------
    T_big_int   &   operator*=( T_big_int   const   &   big_num )
    {
        T_big_int   res;
 
        for( size_t  i{}; i < values_.size(); ++i )
        {
            for( size_t  j{}; j < big_num.values_.size(); ++j )
            {
                res.add_to_ind
                    (
                            values_             [i]
                        *   big_num.values_     [j],
 
                        i + j
                    );
            }//for
        }//for
 
        std::swap   (
                        res,
                        *this
                    );
 
        return  *this;
    }
    //-------------------------------------------------------------------------
    T_str   to_string()                                                     const
    {
        T_str   res;
 
        for (
                auto
                it  =   values_.begin   ();
                it  !=  values_.end     ();
                ++it
            )
        {
            auto    elem_str    =   std::to_string( *it );
 
            while   (
                            elem_str.size()
                        <   ORDER_OF_FACTOR
                    )
            {
                elem_str    =   '0' +   elem_str;
            }
 
            res     =   elem_str    +   res;
        }//for
 
        while   (
                        res.size    ()  >   1
                    &&  res.front   ()  ==  '0'
                )
        {
            res.erase( 0, 1 );
        }
 
        return  res;
    }
    //-------------------------------------------------------------------------
private:
    //-------------------------------------------------------------------------
    void    add_to_ind
        (
            TT_base_int     num,
            size_t          ind
        )
    {
        if  (
                    ind + 1
                >   values_.size()
            )
        {
            values_.resize( ind + 1 );
        }
 
        values_[ ind ]  +=  num;
        auto    head    =   values_[ ind ]  /   FACTOR;
        values_[ ind ]  %=  FACTOR;
 
        if( head )
        {
            add_to_ind
                (
                    head,
                    ind + 1
                );
        }//if
    }
    //-------------------------------------------------------------------------
    void    set_values( T_str    digits )
    {
        while   (
                    digits.size()   >   ORDER_OF_FACTOR
                )
        {
            auto    new_digits_size     =       digits.size()
                                            -   ORDER_OF_FACTOR;
 
            auto    tail    =   digits.substr( new_digits_size                  );
            digits          =   digits.substr( 0,               new_digits_size );
 
            values_.push_back
                (
                    std::stoll( tail )
                );
        }//while
 
        values_.push_back
            (
                std::stoll( digits )
            );
    }
    //-------------------------------------------------------------------------
};
///////////////////////////////////////////////////////////////////////////////
template< typename  U >
std::ostream    &   operator<<
    (
        std::ostream            &   ostr,
        T_big_int< U >  const   &   big_int
    )
{
    ostr    <<  big_int.to_string();
    return  ostr;
}
///////////////////////////////////////////////////////////////////////////////
template< typename  U >
T_big_int< U >   operator*
    (
        T_big_int< U >  const   &   L,
        T_big_int< U >  const   &   R
    )
{
    return  T_big_int< U >(L)   *=  R;
}
///////////////////////////////////////////////////////////////////////////////
template
    <
        typename    T,
        typename    U
    >
T_big_int< T >   operator*
    (
        U                           L,
        T_big_int< T >  const   &   R
    )
{
    return      T_big_int< T >(L)
            *   R;
}
///////////////////////////////////////////////////////////////////////////////
template
    <
        typename    T,
        typename    U
    >
T_big_int< T >   operator*
    (
        T_big_int< T >  const   &   L,
        U                           R
    )
{
    return      L
            *   T_big_int< T >(R);
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::ios::sync_with_stdio(false);
 
    using   T_int   =   T_big_int< long long >;
 
    T_int   a   (
                    "70000000000000000000000000000000000000000000000000000000000"
                    "00000000000000000000000000000000000000000000000000000000000"
                    "00000000000000000000000000000000000000000000000000000000000"
                    "00000000000000000000000000000000000000000000000000000000000"
                    "00000000000000000000000000000000000000000000000000000000000"
                    "00000000000000000000000000000000000000000000000000000000000"
                );
 
    T_int   b   (
                    "80000000000000000000000000000000000000000000000000000000000"
                    "00000000000000000000000000000000000000000000000000000000000"
                    "00000000000000000000000000000000000000000000000000000000000"
                    "00000000000000000000000000000000000000000000000000000000000"
                    "00000000000000000000000000000000000000000000000000000000000"
                    "00000000000000000000000000000000000000000000000000000000000"
                );
 
    std::cout   <<  a   *   b
                <<  std::endl
                <<  std::endl;
 
    std::cout   <<  50  *   a
                <<  std::endl
                <<  std::endl;
 
    std::cout   <<  "50"    *   a
                <<  std::endl
                <<  std::endl;
 
    std::cout   <<  a   *   50
                <<  std::endl
                <<  std::endl;
 
    std::cout   <<  a   *   "50"
                <<  std::endl
                <<  std::endl;
 
    std::cout   <<  '!'     *   b
                <<  std::endl
                <<  std::endl;
 
    std::cout   <<  b   *   '!'
                <<  std::endl
                <<  std::endl;
 
    a   *=  a;
    a   *=  a;
    a   *=  a;
    a   *=  a;
 
    std::cout   <<  a
                <<  std::endl;
}
Ferrari F1
Заблокирован
295 / 281 / 61
Регистрация: 27.01.2015
Сообщений: 1,888
Записей в блоге: 1
Завершенные тесты: 1
17.06.2016, 13:21     Умножение двух больших чисел #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
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
#include <algorithm>
#include <windows.h>
 
#include <string>
using std::string;
 
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
 
const string& toMult(string& value1, string& value2);
string& toAdd(string& value1, string& value2);
string& multDigitWithZeros(const string& value1, const string& value2);
string& multOneDigit(const string& value1, const char& value2);
 
int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    string value1("470827"), value2("60013");
    cout << toMult(value1, value2) << endl;
    system("pause");
    return 0;
}
 
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;
}
Yandex
Объявления
17.06.2016, 13:21     Умножение двух больших чисел
Ответ Создать тему
Опции темы

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